Document Open Access Logo

Approximating Dense Max 2-CSPs

Authors Pasin Manurangsi, Dana Moshkovitz

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.396.pdf
  • Filesize: 0.51 MB
  • 20 pages

Document Identifiers

Author Details

Pasin Manurangsi
Dana Moshkovitz

Cite As Get BibTex

Pasin Manurangsi and Dana Moshkovitz. Approximating Dense Max 2-CSPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 396-415, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.396

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.

Subject Classification

Keywords
  • Max 2-CSP
  • Dense Graphs
  • Densest k-Subgraph
  • QPTAS
  • Free Games
  • Projection Games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Aaronson, R. Impagliazzo, and D. Moshkovitz. AM with multiple Merlins. In Computational Complexity (CCC), 2014 IEEE 29th Conference on, pages 44-55, June 2014. Google Scholar
  2. N. Alon, W. F. de la Vega, R. Kannan, and M. Karpinski. Random sampling and approximation of max-CSPs. J. Comput. Syst. Sci., 67(2):212-243, September 2003. Google Scholar
  3. S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. In Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC'95, pages 284-293, New York, NY, USA, 1995. ACM. Google Scholar
  4. B. Barak, M. Hardt, T. Holenstein, and D. Steurer. Subsampling mathematical relaxations and average-case complexity. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'11, pages 512-531. SIAM, 2011. Google Scholar
  5. B. Barak, A. Rao, R. Raz, R. Rosen, and R. Shaltiel. Strong parallel repetition theorem for free projection games. In Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM'09, pages 352-365, Berlin, Heidelberg, 2009. Springer-Verlag. Google Scholar
  6. M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs, and nonapproximability - towards tight results. SIAM Journal on Computing, 27(3):804-915, 1998. Google Scholar
  7. A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and A. Vijayaraghavan. Detecting high log-densities: An O(n^1/4) approximation for densest k-subgraph. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC'10, pages 201-210, New York, NY, USA, 2010. ACM. Google Scholar
  8. F. G.S.L. Brandao and A. W. Harrow. Quantum de finetti theorems under local measurements with applications. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC'13, pages 861-870, New York, NY, USA, 2013. ACM. Google Scholar
  9. M. Braverman, Y. K. Ko, and O. Weinstein. Approximating the best nash equilibrium in n^o(log n)-time breaks the exponential time hypothesis. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 970-982. SIAM, 2015. Google Scholar
  10. M. Charikar, M. Hajiaghayi, and H. Karloff. Improved approximation algorithms for label cover problems. In ESA, pages 23-34, 2009. Google Scholar
  11. U. Feige, D. Peleg, and G. Kortsarz. The dense k-subgraph problem. Algorithmica, 29(3):410-421, 2001. Google Scholar
  12. J. Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. Google Scholar
  13. S. Khot. Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS'04, pages 136-145, Washington, DC, USA, 2004. IEEE Computer Society. Google Scholar
  14. P. Manurangsi and D. Moshkovitz. Improved approximation algorithms for projection games. In Algorithms – ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 683-694. Springer Berlin Heidelberg, 2013. Google Scholar
  15. D. Moshkovitz. The projection games conjecture and the NP-hardness of ln n-approximating set-cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, volume 7408, pages 276-287, 2012. Google Scholar
  16. R. Raz. A parallel repetition theorem. In SIAM Journal on Computing, volume 27, pages 763-803, 1998. Google Scholar
  17. R. Shaltiel. Derandomized parallel repetition theorems for free games. Comput. Complex., 22(3):565-594, September 2013. Google Scholar
  18. A. Suzuki and T. Tokuyama. Dense subgraph problems with output-density conditions. In Xiaotie Deng and Ding-Zhu Du, editors, Algorithms and Computation, volume 3827 of Lecture Notes in Computer Science, pages 266-276. Springer Berlin Heidelberg, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact