Given three n-element sequences ai, bi and ci of nonnegative real numbers, the aim is to find two permutations f and ¿ such that the sum ¿ni = 1 aibf(i)C¿(i) is minimized (maximized, respectively). We show that the maximization version of this problem can be solved in polynomial time, whereas we present an NP-completeness proof for the minimization version. We identify several special cases of the minimization problem which can be solved in polynomial time, and suggest a local search heuristic for the general case.
|Number of pages||173|
|Journal||Discrete Applied Mathematics|
|Publication status||Published - 1996|