License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.396
URN: urn:nbn:de:0030-drops-53149
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5314/
Go to the corresponding LIPIcs Volume Portal

Manurangsi, Pasin ; Moshkovitz, Dana

Approximating Dense Max 2-CSPs

pdf-format:
24.pdf (0.5 MB)

Abstract

In this paper, we present a polynomial-time algorithm that approximates sufficiently high-value Max 2-CSPs on sufficiently dense graphs to within O(N^epsilon) approximation ratio for any constant epsilon > 0. Using this algorithm, we also achieve similar results for free games, projection games on sufficiently dense random graphs, and the Densest k-Subgraph problem with sufficiently dense optimal solution. Note, however, that algorithms with similar guarantees to the last algorithm were in fact discovered prior to our work by Feige et al. and Suzuki and Tokuyama.

In addition, our idea for the above algorithms yields the following by-product: a quasi-polynomial time approximation scheme (QPTAS) for satisfiable dense Max 2-CSPs with better running time than the known algorithms.

BibTeX - Entry

@InProceedings{manurangsi_et_al:LIPIcs:2015:5314,
  author =	{Pasin Manurangsi and Dana Moshkovitz},
  title =	{{Approximating Dense Max 2-CSPs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{396--415},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5314},
  URN =		{urn:nbn:de:0030-drops-53149},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.396},
  annote =	{Keywords: Max 2-CSP, Dense Graphs, Densest k-Subgraph, QPTAS, Free Games, Projection Games}
}

Keywords: Max 2-CSP, Dense Graphs, Densest k-Subgraph, QPTAS, Free Games, Projection Games
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI