Three-dimensional axial assignment problems with decomposable cost coefficients

R.E. Burkard; R. Rudolf; G.J. Woeginger

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

Three-dimensional axial assignment problems with decomposable cost coefficients

R.E. Burkard, R. Rudolf, G.J. Woeginger

Research output: Contribution to journal › Article › Academic › peer-review

44 Citations (Scopus)

1 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	123-139
Number of pages	173
Journal	Discrete Applied Mathematics
Volume	65
Issue number	1-3
DOIs	https://doi.org/10.1016/0166-218X(95)00031-L
Publication status	Published - 1996

Access to Document

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

Cite this

@article{e6bf92428d7648ddb5ed68211c9b4417,

title = "Three-dimensional axial assignment problems with decomposable cost coefficients",

abstract = "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.",

author = "R.E. Burkard and R. Rudolf and G.J. Woeginger",

year = "1996",

doi = "10.1016/0166-218X(95)00031-L",

language = "English",

volume = "65",

pages = "123--139",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Three-dimensional axial assignment problems with decomposable cost coefficients

AU - Burkard, R.E.

AU - Rudolf, R.

AU - Woeginger, G.J.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

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

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

M3 - Article

SN - 0166-218X

VL - 65

SP - 123

EP - 139

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

Three-dimensional axial assignment problems with decomposable cost coefficients

Abstract

Access to Document

Fingerprint

Cite this