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

Electronic data

Links

Text available via DOI:

View graph of relations

New techniques for cost sharing in combinatorial optimization games

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
<mark>Journal publication date</mark>2010
<mark>Journal</mark>Mathematical Programming
Issue number1-2
Volume124
Number of pages26
Pages (from-to)93-118
Publication StatusPublished
<mark>Original language</mark>English

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.