Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Integrality Gap:
TR00-021 | 19th April 2000
Uriel Feige, Marek Karpinski, Michael Langberg

Improved Approximation of MAX-CUT on Graphs of Bounded Degree

We analyze the addition of a simple local improvement step to various known
randomized approximation algorithms.
Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently
known for the Max Cut problem on general graphs~\cite{GW95}.
We consider a semidefinite relaxation of the Max Cut problem,
round it using the ... more >>>

TR06-098 | 17th August 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

We study semidefinite programming relaxations of Vertex Cover arising from
repeated applications of the LS+ ``lift-and-project'' method of Lovasz and
Schrijver starting from the standard linear programming relaxation.

Goemans and Kleinberg prove that after one round of LS+ the integrality
gap remains arbitrarily close to 2. Charikar proves an integrality ... more >>>

TR06-132 | 17th October 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut

Revisions: 1

We study linear programming relaxations of Vertex Cover and Max Cut
arising from repeated applications of the ``lift-and-project''
method of Lovasz and Schrijver starting from the standard linear
programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that
the integrality gap remains at least $2-\epsilon$ after
$\Omega_\epsilon(\log n)$ ... more >>>

TR13-071 | 8th May 2013
Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket

Inapproximability of Minimum Vertex Cover on $k$-uniform $k$-partite Hypergraphs

We study the problem of computing the minimum vertex cover on $k$-uniform $k$-partite hypergraphs when the $k$-partition is given. On bipartite graphs ($k=2$), the minimum vertex cover can be computed in polynomial time. For $k \ge 3$, this problem is known to be NP-hard. For general $k$, the problem was ... more >>>

TR16-017 | 24th December 2015
Georgios Stamoulis

Limitations of Linear Programming Techniques for Bounded Color Matchings

Given a weighted graph $G = (V,E,w)$, with weight function $w: E \rightarrow \mathbb{Q^+}$, a \textit{matching} $M$ is a set of pairwise non-adjacent edges. In the optimization setting, one seeks to find a matching of \textit{maximum} weight. In the \textit{multi-criteria} (or \textit{multi-budgeted}) setting, we are also given $\ell$ length functions ... more >>>

TR16-079 | 2nd May 2016
Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli

Sum-of-squares hierarchy lower bounds for symmetric formulations

We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of ``well-behaved'' univariate polynomial inequalities.

We illustrate the technique on ... more >>>

TR16-116 | 26th July 2016
Subhash Khot, Rishi Saket

Approximating CSPs using LP Relaxation

This paper studies how well the standard LP relaxation approximates a $k$-ary constraint satisfaction problem (CSP) on label set $[L]$. We show that, assuming the Unique Games Conjecture, it achieves an approximation within $O(k^3\cdot \log L)$ of the optimal approximation factor. In particular we prove the following hardness result: let ... more >>>

TR20-136 | 11th September 2020
Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

Explicit and structured sum of squares lower bounds from high dimensional expanders

We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time.
Our construction is based on the high-dimensional expanders devised by Lubotzky, ... more >>>

ISSN 1433-8092 | Imprint