Name
Abstract | ||
|---|---|---|
We consider the problem of sharing the cost of scheduling n jobs on m parallel machines among a set of agents. In our setting, each agent owns exactly one job and the cost is given by the makespan of the computed assignment. We focus on @a-budget-balanced cross-monotonic cost-sharing methods since they guarantee the two substantial mechanism properties @a-budget-balance and group-strategyproofness and provide fair cost-shares. For identical jobs on related machines and for arbitrary jobs on identical machines, we give (m+1)/(2m)-budget-balanced cross-monotonic cost-sharing methods and show that this is the best approximation possible. As our major result, we prove that the approximation factor for cross-monotonic cost-sharing methods is unbounded for arbitrary jobs and related machines. We therefore develop a cost-sharing method in the (m+1)/(2m)-core, a weaker but also fair solution concept. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.jda.2009.02.001 | CIAC |
Keywords | DocType | Volume |
solution concept | Journal | 7 |
Issue | ISSN | ISBN |
3 | Journal of Discrete Algorithms | 3-540-34375-X |
Citations | PageRank | References |
11 | 0.58 | 28 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yvonne Bleischwitz | 1 | 28 | 2.59 |
| Burkhard Monien | 2 | 2199 | 279.35 |