On complexity, representation and approximation of integral multicommodity flows Original Research Article

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 Ω(ε−2 log m) 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. (Algorithmica 18 (1997) 3–20), 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 specified demand function r−K is NP-hard even if c is any function polynomially bounded in n and if the problem with demand function r 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 (Technical Report, Computer Science Department, Israel Institute of Technology, Haifa, 1989) could fix it to 1. Finally, an interesting relation between discrepancies of set systems and integral multicommodity flows with specified demands is discussed.