path-constrained network flows
| dc.contributor.advisor | Skutella, Martin | |
| dc.contributor.author | Martens, Maren | |
| dc.contributor.referee | Eisenbrand, Friedrich | |
| dc.date.accepted | 2007-04-19 | |
| dc.date.accessioned | 2007-04-25T11:12:16Z | |
| dc.date.available | 2007-04-25T11:12:16Z | |
| dc.date.issued | 2007-04-25T11:12:16Z | |
| dc.description.abstract | This thesis focuses on approximation algorithms and complexity assessments concerning network flows. It deals with various network flow problems with path restrictions. These restrictions cover the number of paths that are used to route commodities as well as the amount of flow that is routed along a single path or the path's length. Concerning the first restriction we study the unsplittable flow problem-a generalization of the NP-hard edge-disjoint paths problem. Given a network with commodities that must be routed from their sources to their sinks, the unsplittable flow problem forbids each commodity to use more than one path. For this problem we prove a new lower bound on the performance guarantee of randomized rounding which so far belongs to the best approximation algorithms known for this problem. Further, we present an interesting relation between unsplittable flows and classical (splittable) multicommodity flows in the case that all commodities share a common source: Each single source multicommodity flow can be represented as a convex combination of unsplittable flows of congestion at most 2. Further, we combine different path restrictions from the ones mentioned above. In the k-splittable flow problem with path capacities, we study the NP-hard problem that each commodity may be sent along a limited number of paths while the flow value of each path is bounded. This yields a generalization of the unsplittable flow problem, but we show how one can obtain the same asymptotic approximation ratios. For the length-bounded k-splittable flow problem, we consider the single commodity case and develop a constant factor approximation algorithm. A crucial characteristic of network flows occurring in real-world applications is flow variation over time and the fact that flow does not travel instantaneously through a network but requires a certain amount of time to travel through each arc. Both characteristics are captured by "flows over time" which specify a flow rate for each arc and each point in time. We consider the quickest single commodity k-splittable flow problem and give a constant factor approximation algorithm for it. So far only results for k-splittable flows as well as for length-bounded flows and flows over time have been known, but nothing was known for combinations of them. Bounding the flow value of each path is also interesting in the classical maximum s-t-flow problem. We study the case that each path may carry at most one unit of flow and prove that this restriction makes the maximum s-t-flow problem strongly NP-hard. In contrast to the classical maximum s-t-flow problem, the fractional and the integral problem diverge strongly with the new restriction. For the integral problem, we even prove APX-hardness. We develop an FPTAS for the fractional problem and an O(log m)-approximation algorithm for the integral one. (Here, m is the number of arcs in the network under consideration.) Similar results emerge for the multicommodity case. For the objective to find a maximum integral multicommodity flow our asymptotic approximation ratio of O(m^{0.5}) is proven to be best possible, unless P = NP. | en |
| dc.identifier.uri | http://hdl.handle.net/2003/24272 | |
| dc.identifier.uri | http://dx.doi.org/10.17877/DE290R-503 | |
| dc.identifier.urn | urn:nbn:de:hbz:290-2003/24272-2 | |
| dc.language.iso | en | de |
| dc.subject | discrete optimization | en |
| dc.subject | network flows | en |
| dc.subject | approximation algorithms | en |
| dc.subject.ddc | 510 | |
| dc.title | path-constrained network flows | en |
| dc.type | Text | de |
| dc.type.publicationtype | doctoralThesis | de |
| dcterms.accessRights | open access |