Sharing supermodular costs

Andreas S. Schulz, Nelson A. Uhan

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

16 Zitate (Scopus)

Abstract

We study cooperative games with supermodular costs. We show that supermodular costs arise in a variety of situations; in particular, we show that the problem of minimizing a linear function over a supermodular polyhedron-a problem that often arises in combinatorial optimization-has supermodular optimal costs. In addition, we examine the computational complexity of the least core and least core value of supermodular cost cooperative game s. We show that the problem of computing the least core value of these game s is strongly NP-hard and, in fact, is in approximable within a factor strictly less than 17/16 unless P = NP. For a particular class of supermodular cost cooperative games that arises from a scheduling problem, we show that the Shapley value-which, in this case, is computable in polynomial time-is in the least core, while computing the least core value is NP-hard.

OriginalspracheEnglisch
Seiten (von - bis)1051-1056
Seitenumfang6
FachzeitschriftOperations Research
Jahrgang58
Ausgabenummer4 PART 2
DOIs
PublikationsstatusVeröffentlicht - Juli 2010
Extern publiziertJa

Fingerprint

Untersuchen Sie die Forschungsthemen von „Sharing supermodular costs“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren