### 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 |

### Keywords

- Approximation schemes
- Assignment problems
- Constraint satisfaction problems
- Dense instances
- Locally-dense instances
- Sherali-Adams hierarchy

### ASJC Scopus subject areas

- Computational Theory and Mathematics

## 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