Three-dimensional axial assignment problems with decomposable cost coefficients

被引：45

作者：

Burkard, RE

Rudolf, R

Woeginger, GJ

机构：

[1] Institut für Mathematik B, TU Graz, A-8010 Graz

来源：

DISCRETE APPLIED MATHEMATICS | 1996年 / 65卷 / 1-3期

关键词：

three-dimensional assignment problems; decomposable cost coefficients; complexity; special cases; heuristics;

D O I：

10.1016/0166-218X(95)00031-L

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given three n-element sequences a(i), b(i) and c(i) of nonnegative real numbers, the aim is to find two permutations phi and psi such that the sum Sigma(i=1)(n) = a(i)b(phi(i))c(psi(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.

引用

页码：123 / 139

页数：17