Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems

Yuichi Yoshida, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider approximation schemes for the maximum constraint satisfaction problems and the maximum assignment problems. Though they are NP-Hard in general, if the instance is "dense" or "locally dense", then they are known to have approximation schemes that run in polynomial time or quasi-polynomial time. In this paper, we give a unified method of showing these approximation schemes based on the Sherali-Adams linear programming relaxation hierarchy. We also use our linear programming-based framework to show new algorithmic results on the optimization version of the hypergraph isomorphism problem.

Original languageEnglish (US)
Title of host publicationITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery,
Pages423-437
Number of pages15
ISBN (Print)9781450322430
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States
Duration: Jan 12 2014Jan 14 2014

Publication series

NameITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

Other

Other2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
CountryUnited States
CityPrinceton, NJ
Period1/12/141/14/14

Keywords

  • Approximation schemes
  • Assignment problems
  • Constraint satisfaction problems
  • Dense instances
  • Locally-dense instances
  • Sherali-Adams hierarchy

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems'. Together they form a unique fingerprint.

  • Cite this

    Yoshida, Y., & Zhou, Y. (2014). Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems. In ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science (pp. 423-437). (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science). Association for Computing Machinery,. https://doi.org/10.1145/2554797.2554836