TY - GEN A1 - Brenner, Janina A1 - Schäfer, Guido T1 - Cost Sharing Methods for Makespan and Completion Time Scheduling N2 - Roughgarden and Sundararajan recently introduced an alternative measure of efficiency for cost sharing mechanisms. We study cost sharing methods for combinatorial optimization problems using this novel efficiency measure, with a particular focus on scheduling problems. While we prove a lower bound of $\Omega(\log n)$ for a very general class of problems, we give a best possible cost sharing method for minimum makespan scheduling. Finally, we show that no budget balanced cost sharing methods for completion or flow time objectives exist. KW - game theory KW - mechanism design KW - cost sharing mechanisms KW - combinatorial optimization KW - scheduling problems Y1 - 2006 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/360 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-3608 ER -