Submitted manuscript, 212 KB, PDF document
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
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 -