TY - GEN
T1 - Encouraging cooperation in sharing supermodular costs
AU - Schulz, Andreas S.
AU - Uhan, Nelson A.
PY - 2007
Y1 - 2007
N2 - We study the computational complexity and algorithmic aspects of computing the least core value of supermodular cost cooperative games, and uncover some structural properties of the least core of these games. We provide motivation for studying these games by showing that a particular class of optimization problems has supermodular optimal costs. This class includes a variety of problems in combinatorial optimization, especially in machine scheduling. We show that computing the least core value of supermodular cost cooperative games is NP-hard, and design approximation algorithms based on oracles that approximately determine maximally violated constraints. We apply our results to schedule planning games, or cooperative games where the costs arise from the minimum sum of weighted completion times on a single machine. By improving upon some of the results for general supermodular cost cooperative games, we are able to give an explicit formula for an element of the least core of schedule planning games, and design a fully polynomial time approximation scheme for computing the least core value of these games.
AB - We study the computational complexity and algorithmic aspects of computing the least core value of supermodular cost cooperative games, and uncover some structural properties of the least core of these games. We provide motivation for studying these games by showing that a particular class of optimization problems has supermodular optimal costs. This class includes a variety of problems in combinatorial optimization, especially in machine scheduling. We show that computing the least core value of supermodular cost cooperative games is NP-hard, and design approximation algorithms based on oracles that approximately determine maximally violated constraints. We apply our results to schedule planning games, or cooperative games where the costs arise from the minimum sum of weighted completion times on a single machine. By improving upon some of the results for general supermodular cost cooperative games, we are able to give an explicit formula for an element of the least core of schedule planning games, and design a fully polynomial time approximation scheme for computing the least core value of these games.
UR - http://www.scopus.com/inward/record.url?scp=38049083882&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-74208-1_20
DO - 10.1007/978-3-540-74208-1_20
M3 - Conference contribution
AN - SCOPUS:38049083882
SN - 9783540742074
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 271
EP - 285
BT - Approximation, Randomization, and Combinatorial Optimization
PB - Springer Verlag
T2 - 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007
Y2 - 20 August 2007 through 22 August 2007
ER -