We prove that Minimum vertex cover on 4-regular hyper-graphs (or in other words, hitting set where all sets have size exactly 4), is hard to approximate within 2 - \epsilon. We also prove that the maximization version, in which we are allowed to pick B = pn elements in an ... more >>>

Using known results regarding PCP, we present simple proofs of the inapproximability of vertex cover for hypergraphs. Specifically, we show that (1) Approximating the size of the minimum vertex cover in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard. (2) Approximating the size of the minimum vertex cover in ... more >>>

We show Minimum Vertex Cover NP-hard to approximate to within a factor of 1.3606. This improves on the previously known factor of 7/6. more >>>

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is to find a minimum subset of vertices that ``hits'' every edge. We show that for every integer $k \geq 5$, E$k$-Vertex-Cover is NP-hard to approximate within a factor of $(k-3-\epsilon)$, for an arbitrarily small constant $\epsilon > 0$. This almost matches the ... more >>>

We reduce the approximation factor for Vertex Cover to $2-\Theta(1/\sqrt{logn})$ (instead of the previous $2-\Theta(loglogn/logn})$, obtained by Bar-Yehuda and Even, and by Monien and Speckenmeyer in 1985. The improvement of the vanishing factor comes as an application of the recent results of Arora, Rao, and Vazirani that improved the approximation ... more >>>

more >>>

We consider the problem of estimating the size, $VC(G)$, of a minimum vertex cover of a graph $G$, in sublinear time, by querying the incidence relation of the graph. We say that an algorithm is an $(\alpha,\eps)$-approximation algorithm if it outputs with high probability an estimate $\widehat{VC}$ such that $VC(G) ... more >>>

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

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1). more >>>

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small ... more >>>