Refine
Year of publication
- 2006 (2)
Language
- English (2)
Keywords
- branch-and-cut (1)
- combinatorial optimization (1)
- cost sharing mechanisms (1)
- game theory (1)
- heuristics (1)
- integer programming (1)
- mechanism design (1)
- multi-layer network design (1)
- scheduling problems (1)
Application Area
- B (2)
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.
This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree.