Sequential and parallel algorithms for mixed packing and covering

Neal Young
Akamai Technologies and MIT


Mixed packing and covering problems are problems that can be
formulated as linear programs using only non-negative
coefficients. Examples include multicommodity network flow,
the Held-Karp lower bound on TSP, fractional relaxations of
set cover, bin-packing, knapsack, scheduling problems,
minimum-weight triangulation, etc.  I'll describe
approximation algorithms for the general class of problems.
I'll focus on a sequential algorithm that can be implemented
to run in O(epsilon^-2 log n) linear-time iterations.

For epsilon = O(1), these algorithms are currently the fastest
known for the general problem.  The results generalize
previous work on pure packing and covering (the special case
when the constraints are all ``less-than'' or all
``greater-than'') by Luby and Nisan [1993], Garg and Könemann
[1998], and Lisa Fleischer [1999].