Maximizing polynomials subject to assignment constraints

Konstantin Makarychev, Maxim Sviridenko

Research output: Contribution to journalArticlepeer-review

Abstract

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 showthat 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.

Original languageEnglish (US)
Article number54
JournalACM Transactions on Algorithms
Volume13
Issue number4
DOIs
StatePublished - Nov 1 2017

Keywords

  • Approximation algorithms
  • Quadratic assignment problem

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Maximizing polynomials subject to assignment constraints'. Together they form a unique fingerprint.

Cite this