Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs

摘要: In the edge(vertex)-disjoint path problem we are given a graph $G$ and set ${\cal T}$ of connection requests. Every request in is vertex pair $(s_i,t_i),$ $1 \leq i K.$ The objective to connect maximum number pairs via paths. edge-disjoint can be generalized multiple-source unsplittable flow where $i$ has demand $\rho_i$ every edge $e$ capacity $u_e.$ All these problems NP-hard have multitude applications areas such as routing, scheduling bin packing. Given hardness problem, study polynomial-time approximation algorithms. this context, $\rho$-approximation algorithm able route at least $1/\rho$ fraction Although edge- vertex-disjoint problems, more recently generalization, been extensively studied, they remain notoriously hard approximate with bounded performance guarantee. For example, even for simple no $o(\sqrt{|E|})$-approximation known. Moreover some best existing ratios obtained through sophisticated non-standard randomized rounding schemes. paper introduce techniques which yield algorithms wide range disjoint-path problems. general weights on commodities, our lead first obtain an ratio that matches, within logarithmic factors, $O(\sqrt{|E|})$ problem. addition result improved bounds several simplify unify derivation many results. We use two basic techniques. First, propose greedy paths second, framework based packing integer programs flow. A program form maximize $c^{T}\cdot x,$ subject $Ax b,$ $A,b,c \geq 0.$ As part tools develop class programs, believe independent interest.