Home > Research > Publications & Outputs > New techniques for cost sharing in combinatoria...

Research

Electronic data

Links

Text available via DOI:

Keywords

View graph of relations

New techniques for cost sharing in combinatorial optimization games

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

New techniques for cost sharing in combinatorial optimization games. / Caprara, A; Letchford, A N.
In: Mathematical Programming, Vol. 124, No. 1-2, 2010, p. 93-118.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Caprara, A & Letchford, AN 2010, 'New techniques for cost sharing in combinatorial optimization games', Mathematical Programming, vol. 124, no. 1-2, pp. 93-118. https://doi.org/10.1007/s10107-010-0357-7

APA

Caprara, A., & Letchford, A. N. (2010). New techniques for cost sharing in combinatorial optimization games. Mathematical Programming, 124(1-2), 93-118. https://doi.org/10.1007/s10107-010-0357-7

Vancouver

Caprara A, Letchford AN. New techniques for cost sharing in combinatorial optimization games. Mathematical Programming. 2010;124(1-2):93-118. doi: 10.1007/s10107-010-0357-7

Author

Caprara, A ; Letchford, A N. / New techniques for cost sharing in combinatorial optimization games. In: Mathematical Programming. 2010 ; Vol. 124, No. 1-2. pp. 93-118.

Bibtex

@article{4140c996affc4f9ca5c0032136d5fd51,
title = "New techniques for cost sharing in combinatorial optimization games",
abstract = "Combinatorial optimization games form an important subclass of cooperative games. In recent years, increased attention has been given to the issue of finding good cost shares for such games. In this paper, we define a very general class of games, called integer minimization games, which includes the combinatorial optimization games in the literature as special cases. We then present new techniques, based on row and column generation, for computing good cost shares for these games. To illustrate the power of these techniques, we apply them to traveling salesman and vehicle routing games. Our results generalize and unify several results in the literature. The main underlying idea is that suitable valid inequalities for the associated combinatorial optimization problems can be used to derive improved cost shares.",
keywords = "cooperative games, cost shares, combinatorial optimisation games, traveling salesman game",
author = "A Caprara and Letchford, {A N}",
year = "2010",
doi = "10.1007/s10107-010-0357-7",
language = "English",
volume = "124",
pages = "93--118",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "1-2",

}

RIS

TY - JOUR

T1 - New techniques for cost sharing in combinatorial optimization games

AU - Caprara, A

AU - Letchford, A N

PY - 2010

Y1 - 2010

N2 - Combinatorial optimization games form an important subclass of cooperative games. In recent years, increased attention has been given to the issue of finding good cost shares for such games. In this paper, we define a very general class of games, called integer minimization games, which includes the combinatorial optimization games in the literature as special cases. We then present new techniques, based on row and column generation, for computing good cost shares for these games. To illustrate the power of these techniques, we apply them to traveling salesman and vehicle routing games. Our results generalize and unify several results in the literature. The main underlying idea is that suitable valid inequalities for the associated combinatorial optimization problems can be used to derive improved cost shares.

AB - Combinatorial optimization games form an important subclass of cooperative games. In recent years, increased attention has been given to the issue of finding good cost shares for such games. In this paper, we define a very general class of games, called integer minimization games, which includes the combinatorial optimization games in the literature as special cases. We then present new techniques, based on row and column generation, for computing good cost shares for these games. To illustrate the power of these techniques, we apply them to traveling salesman and vehicle routing games. Our results generalize and unify several results in the literature. The main underlying idea is that suitable valid inequalities for the associated combinatorial optimization problems can be used to derive improved cost shares.

KW - cooperative games

KW - cost shares

KW - combinatorial optimisation games

KW - traveling salesman game

U2 - 10.1007/s10107-010-0357-7

DO - 10.1007/s10107-010-0357-7

M3 - Journal article

VL - 124

SP - 93

EP - 118

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -