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 -