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

*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

**Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems.** / Yoshida, Yuichi; Zhou, Yuan.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science.*ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science, Association for Computing Machinery, pp. 423-437, 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014, Princeton, NJ, United States, 1/12/14. https://doi.org/10.1145/2554797.2554836

}

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 -