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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

2 Citaten (Scopus)

2 Downloads (Pure)

Samenvatting

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?"

Originele taal-2	Engels
Pagina's (van-tot)	282-284
Tijdschrift	Mathematical Social Sciences
Volume	57
Nummer van het tijdschrift	2
DOI's	https://doi.org/10.1016/j.mathsocsci.2008.11.005
Status	Gepubliceerd - 2009

Toegang tot document

10.1016/j.mathsocsci.2008.11.005

Citeer dit

@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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit