Noname manuscript No. (will be inserted by the editor) Approximation Schemes via Sherali-Adams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems

the date of receipt and acceptance should be inserted later Abstract We consider approximation schemes for the maximum constraint satis-faction 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