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

Yuichi Yoshida; Yuan Zhou

doi:10.1145/2554797.2554836

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 proceeding › Conference 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 language	English (US)
Title of host publication	ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
Publisher	Association for Computing Machinery,
Pages	423-437
Number of pages	15
ISBN (Print)	9781450322430
DOIs	https://doi.org/10.1145/2554797.2554836
State	Published - Jan 1 2014
Externally published	Yes
Event	2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States Duration: Jan 12 2014 → Jan 14 2014

Publication series

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

Other

Other	2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
Country	United States
City	Princeton, NJ
Period	1/12/14 → 1/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

Access to Document

10.1145/2554797.2554836

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

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 proceeding › Conference 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 = jan,

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,

T2 - 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014

Y2 - 12 January 2014 through 14 January 2014

ER -