Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Maximizing polynomials subject to assignment constraints
Makarychev K., Sviridenko M. ACM Transactions on Algorithms13 (4):1-15,2017.Type:Article
Date Reviewed: Jul 13 2018

This paper considers “the q-adic assignment problem.” Fix a number q (originally q=2), and suppose we are given, for some number n, a 2q-dimensional array of costs cu,v where u and v are q-tuples of indices (from one to n). If π is a permutation of the indices 1,...,n, write π(u) for the q-tuple π(u1),...,π(uq), that is, the same permutation is applied to each component. Then the problem is to find the permutation π minimizing ∑ucu,π(u), where the sum is taken over all nq possible q-tuples u. The original version of this problem--“first defined by Koopmans and Beckman” [2]--is when cu,v decomposes as cu,v=wudv; thus we have 2nq cost elements rather than n2q, which is what the authors mean by “Koopmans-Beckman.”

Despite the importance, no good exact algorithms are known, and apparently q=4,n=14 is insoluble in practice.

What, then, about approximation algorithms? The news is not good here either. The authors have previously shown that (under very plausible complexity assumptions) a poly-logarithmic approximation algorithm is impossible, even for q=2 [2]. The best general algorithm for the Koopmans-Beckman variant is one with performance guarantee εnq/2 and running time nO(q/ε) for any ε>0 [1]. For the special case q=2, Makarychev et al. provide an algorithm with performance guarantee O(√n) [2]. The main result of this paper is an Oq(n(q-1)/2)-approximation algorithm for the Koopmans-Beckman variant, thus improving slightly on [1] and matching [2] in the case q=2.

This is a pretty technical paper, but should be of interest to those (for example, in very-large-scale integration (VLSI)) solving these problems for q>2.

Reviewer:  J. H. Davenport Review #: CR146147 (1809-0518)
1) Barvinok, A. Estimating L norms by L2k norms for functions on orbits. Found. Comput. Math. 2, 4(2002), 393–412.
2) Makarychev, K.; Manokaran, R.; Sviridenko, M. Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm. ACM Trans. Algorithms 10, 4(2014), 1–18.
Bookmark and Share
  Featured Reviewer  
 
Algorithm Design And Analysis (G.4 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Algorithm Design And Analysis": Date
Numerical recipes
Sprott J., Cambridge University Press, New York, NY, 1991. Type: Book (9780521406895)
Dec 1 1992
An interactive calculus theorem-prover for continuity properties
Suppes P., Takahashi S. Journal of Symbolic Computation 7(6): 573-590, 1989. Type: Article
Aug 1 1990
The numerical methods programming projects book
Grandine T., Oxford University Press, Inc., New York, NY, 1990. Type: Book (9789780198533870)
Mar 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy