Maximizing polynomials subject to assignment constraints

Konstantin Makarychev*, Maxim Sviridenko

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
Number of pages11
EditionPART 1
StatePublished - Jul 11 2011
Event38th International Colloquium on Automata, Languages and Programming, ICALP 2011 - Zurich, Switzerland
Duration: Jul 4 2011Jul 8 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6755 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other38th International Colloquium on Automata, Languages and Programming, ICALP 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this