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 | |
| 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 |
Fingerprint
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
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
}
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 -