Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Maximizing Polynomials Subject to Assignment Constraints
verfasst von : Konstantin Makarychev, Maxim Sviridenko
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the
q
-adic assignment problem. We first give an
O
(
n
(
q
− 1)/2
)-approximation algorithm for the Koopmans–Beckman version of the problem improving upon the result of Barvinok. Then, we introduce a new family of instances satisfying “tensor triangle inequalities” and give a constant factor approximation algorithm for them. We show that many classical optimization problems can be modeled by
q
-adic assignment problems from this family. Finally, we give several integrality gap examples for the natural LP relaxations of the problem.