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

Fingerprint

Constraint satisfaction problems
Linear programming
Polynomials

Keywords

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

ASJC Scopus subject areas

  • Computational Theory and Mathematics

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

Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems. / Yoshida, Yuichi; Zhou, Yuan.

ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, 2014. p. 423-437 (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).

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

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. ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science, Association for Computing Machinery, pp. 423-437, 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014, Princeton, NJ, United States, 1/12/14. https://doi.org/10.1145/2554797.2554836
Yoshida Y, Zhou Y. 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. Association for Computing Machinery,. 2014. p. 423-437. (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science). https://doi.org/10.1145/2554797.2554836
Yoshida, Yuichi ; Zhou, Yuan. / Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems. ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, 2014. pp. 423-437 (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).
@inproceedings{8462ae2ba28e424985122be73ac43e87,
title = "Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems",
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.",
keywords = "Approximation schemes, Assignment problems, Constraint satisfaction problems, Dense instances, Locally-dense instances, Sherali-Adams hierarchy",
author = "Yuichi Yoshida and Yuan Zhou",
year = "2014",
month = "1",
day = "1",
doi = "10.1145/2554797.2554836",
language = "English (US)",
isbn = "9781450322430",
series = "ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science",
publisher = "Association for Computing Machinery,",
pages = "423--437",
booktitle = "ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science",

}

TY - GEN

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

AU - Yoshida, Yuichi

AU - Zhou, Yuan

PY - 2014/1/1

Y1 - 2014/1/1

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

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

KW - Approximation schemes

KW - Assignment problems

KW - Constraint satisfaction problems

KW - Dense instances

KW - Locally-dense instances

KW - Sherali-Adams hierarchy

UR - http://www.scopus.com/inward/record.url?scp=84893309293&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893309293&partnerID=8YFLogxK

U2 - 10.1145/2554797.2554836

DO - 10.1145/2554797.2554836

M3 - Conference contribution

AN - SCOPUS:84893309293

SN - 9781450322430

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

SP - 423

EP - 437

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

PB - Association for Computing Machinery,

ER -