On complexity, representation and approximation of integral multicommodity flows

On complexity, representation and approximation of integral multicommodity flows

0.00 Avg rating0 Votes
Article ID: iaor20012929
Country: Netherlands
Volume: 99
Issue: 1/3
Start Page Number: 183
End Page Number: 208
Publication Date: Feb 2000
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: programming: integer
Abstract:

The paper has two parts. In the algorithmic part integer inequality systems of packing types and their application to integral multicommodity flow problems are considered. We give 1−ϵ approximation algorithms using the randomized rounding/derandomization scheme provided that the components of the right-hand side vector (resp. the capacities) are in Ω(ϵ-2logm) where m is the number of constraints (resp. the number of edges). In the complexity-theoretic part it is shown that the approximable instances above build hard problems. Extending a result of Garg et al., the non-approximability of the maximum integral multicommodity flow problem for trees with a large capacity function c ∈ Ω(log m), is proved. Furthermore, for every fixed non-negative integer K the problem with the specified demand function rK is NP-hard even if c is any function polynomially bounded in n and if the problem with demand function rK is fractionally solvable. For fractionally solvable multicommodity flow problems with nonplanar union of supply and demand graph the integrality gap is unbounded, while in the planar case Korach and Penn could fix it to 1. Finally, an interesting relation between discrepancies of set systems and integral multicommodity flows with specified demands is discussed.

Reviews

Required fields are marked *. Your email address will not be published.