Uriel Feige, Marek Karpinski, Michael Langberg

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 >>>

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

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 >>>

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

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 >>>

Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket

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 >>>

Georgios Stamoulis

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 >>>

Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli

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 >>>

Subhash Khot, Rishi Saket

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 >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

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 >>>