The complexity of computing the Muirhead-Dalton distance

V.G. Deineko; B. Klinz; G.J. Woeginger

doi:10.1016/j.mathsocsci.2008.11.005

The complexity of computing the Muirhead-Dalton distance

V.G. Deineko, B. Klinz, G.J. Woeginger

Combinatorial Optimization

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

2 Citations (Scopus)

2 Downloads (Pure)

Abstract

We show that the following problem is NP-hard, and hence computationally intractable: "Given a vector y that Lorenz-dominates a vector x, what is the smallest number of Muirhead–Dalton transfers that transform x into y?"

Original language	English
Pages (from-to)	282-284
Journal	Mathematical Social Sciences
Volume	57
Issue number	2
DOIs	https://doi.org/10.1016/j.mathsocsci.2008.11.005
Publication status	Published - 2009

Access to Document

10.1016/j.mathsocsci.2008.11.005

Cite this

@article{899053be916841309c91eb57669b10c1,

title = "The complexity of computing the Muirhead-Dalton distance",

abstract = "We show that the following problem is NP-hard, and hence computationally intractable: {"}Given a vector y that Lorenz-dominates a vector x, what is the smallest number of Muirhead–Dalton transfers that transform x into y?{"}",

author = "V.G. Deineko and B. Klinz and G.J. Woeginger",

year = "2009",

doi = "10.1016/j.mathsocsci.2008.11.005",

language = "English",

volume = "57",

pages = "282--284",

journal = "Mathematical Social Sciences",

issn = "0165-4896",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - The complexity of computing the Muirhead-Dalton distance

AU - Deineko, V.G.

AU - Klinz, B.

AU - Woeginger, G.J.

PY - 2009

Y1 - 2009

N2 - We show that the following problem is NP-hard, and hence computationally intractable: "Given a vector y that Lorenz-dominates a vector x, what is the smallest number of Muirhead–Dalton transfers that transform x into y?"

AB - We show that the following problem is NP-hard, and hence computationally intractable: "Given a vector y that Lorenz-dominates a vector x, what is the smallest number of Muirhead–Dalton transfers that transform x into y?"

U2 - 10.1016/j.mathsocsci.2008.11.005

DO - 10.1016/j.mathsocsci.2008.11.005

M3 - Article

SN - 0165-4896

VL - 57

SP - 282

EP - 284

JO - Mathematical Social Sciences

JF - Mathematical Social Sciences

IS - 2

ER -

The complexity of computing the Muirhead-Dalton distance

Abstract

Access to Document

Fingerprint

Cite this