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 c_u,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 π(u₁),...,π(u_q), that is, the same permutation is applied to each component. Then the problem is to find the permutation π minimizing ∑_uc_u,π(u), where the sum is taken over all n^q possible q-tuples u. The original version of this problem--“first defined by Koopmans and Beckman” [2]--is when c_u,v decomposes as c_u,v=w_ud_v; thus we have 2n^q cost elements rather than n^2q, 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 εn^q/2 and running time n^O(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 O_q(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.