TY - JOUR

T1 - Geometric versions of the three-dimensional assignment problem under general norms

AU - Custic, A.

AU - Klinz, B.

AU - Woeginger, G.J.

PY - 2015

Y1 - 2015

N2 - We discuss the computational complexity of special cases of the three-dimensional (axial) assignment problem where the elements are points in a Cartesian space and where the cost coefficients are the perimeters of the corresponding triangles measured according to a certain norm. (All our results also carry over to the corresponding special cases of the three-dimensional matching problem.)
The minimization version is NP-hard for every norm, even if the underlying Cartesian space is 2-dimensional. The maximization version is polynomially solvable, if the dimension of the Cartesian space is fixed and if the considered norm has a polyhedral unit ball. If the dimension of the Cartesian space is part of the input, the maximization version is NP-hard for every Lp norm; in particular the problem is NP-hard for the Manhattan norm L1 and the Maximum norm L8 which both have polyhedral unit balls.
Keywords: Combinatorial optimization; Computational complexity; 3-dimensional assignment problem; 3-dimensional matching problem; Polyhedral norm

AB - We discuss the computational complexity of special cases of the three-dimensional (axial) assignment problem where the elements are points in a Cartesian space and where the cost coefficients are the perimeters of the corresponding triangles measured according to a certain norm. (All our results also carry over to the corresponding special cases of the three-dimensional matching problem.)
The minimization version is NP-hard for every norm, even if the underlying Cartesian space is 2-dimensional. The maximization version is polynomially solvable, if the dimension of the Cartesian space is fixed and if the considered norm has a polyhedral unit ball. If the dimension of the Cartesian space is part of the input, the maximization version is NP-hard for every Lp norm; in particular the problem is NP-hard for the Manhattan norm L1 and the Maximum norm L8 which both have polyhedral unit balls.
Keywords: Combinatorial optimization; Computational complexity; 3-dimensional assignment problem; 3-dimensional matching problem; Polyhedral norm

U2 - 10.1016/j.disopt.2015.07.002

DO - 10.1016/j.disopt.2015.07.002

M3 - Article

VL - 18

SP - 38

EP - 55

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

ER -