TY - GEN

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

AU - Yoshida, Yuichi

AU - Zhou, Yuan

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

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 -