Maximizing polynomials subject to assignment constraints

Konstantin Makarychev, Maxim Sviridenko

Research output: Contribution to journalArticlepeer-review


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
Issue number4
StatePublished - Nov 1 2017


  • Approximation algorithms
  • Quadratic assignment problem

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


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

Cite this