68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) [See also 68Q15]
Refine
Language
- English (2)
Keywords
- Discrete flows over time (1)
- approximation (1)
- combinatorial optimization (1)
- complexity (1)
- cost sharing mechanisms (1)
- game theory (1)
- mechanism design (1)
- routing (1)
- scheduling problems (1)
Application Area
- B (2)
We consider quickest flows within a new model that is based on transportation applications. In contrast to other models, it is forbidden to store flow in nodes and to cross nodes with more than one flow unit simultaneously. We work on undirected graphs. Grid graphs are of special interest because they typically arise in practice. Our model allows to close edges temporarily by time windows, and considers waiting on edges.
We solve several quickest s,t–flow problems without time windows polynomially. We prove that time windows make these problems NP–hard and even not approximable. In a multicommodity environment, all quickest flow variants are shown to be NP–hard even in grid graphs with uniform edge transit times. An alternative proof shows NP-hardness already for a small number of commodities in the case that waiting is not allowed and transit times are edge–specific. Finally, we propose two approximation algorithms in the case that time windows do not occur.
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.