| Autor: |
Erlebach, Thomas, Persinao, Giuseppe, Koch, Ronald, Skutella, Martin, Spenke, Ines |
| Zdroj: |
Approximation & Online Algorithms (9783540322078); 2006, p244-257, 14p |
| Abstrakt: |
Given a graph with a source and a sink node, the NP-hard maximum k-splittable flow (MkSF) problem is to find a flow of maximum value with a flow decomposition using at most k paths [6]. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values on these paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Our main contributions are as follows: - We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal MkSF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed , the computed set of alternatives contains a packing used by a (1-ε)-approximate solution. The latter result is based on the observation that (1-ε)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. - Based on (i), we prove that, for constant k, the MkSF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it. - Finally, we provide a comprehensive overview of the complexity and approximability landscape of MkSF for different values of k. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
