Three-dimensional axial assignment problems with decomposable cost coefficients

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

    Research output: Contribution to journalArticleAcademicpeer-review

    42 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 languageEnglish
    Pages (from-to)123-139
    Number of pages173
    JournalDiscrete Applied Mathematics
    Volume65
    Issue number1-3
    DOIs
    Publication statusPublished - 1996

    Fingerprint

    Dive into the research topics of 'Three-dimensional axial assignment problems with decomposable cost coefficients'. Together they form a unique fingerprint.

    Cite this