2 papers
cs.DS2005
Correlation Clustering with a Fixed Number of Clusters
Ioannis Giotis, Venkatesan Guruswami
We continue the investigation of problems concerning correlation clustering or clustering with qualitative information, which is a clustering formulation that has been studied rece…
cs.CC2003
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
Irit Dinur, Venkatesan Guruswami, Subhash Khot +1
Given a -uniform hyper-graph, the E-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP constr…