We describe sequential and parallel algorithms that approximately solve linear programs with no negative coefficients (a.k.a. mixed packing and covering problems). For explicitly given problems, our fastest sequential algorithm returns a solution satisfying all constraints within a 1 ± ǫ factor in O(md log(m)/ǫ 2 ) time, where m is the number of constraints and d is the maximum number of constraints any variable appears in. The main contribution is that the algorithms solve mixed packing and covering problems (in contrast to pure packing or pure covering problems, which have only "≤" or only "≥" inequalities, but not both) and run in time independent of the so-called width of the problem.
Young REF developed a parallel (1 + )-approximation algorithm for mixed packing-covering problems, which obtains a solution that satisfies all constraints within a (1 ± ) factor in a poly-logarithmic number of rounds.
Sequential and Parallel Algorithms for Mixed Packing and Covering
IEEE Symposium on Foundations of Computer Science (2001)
Mathematics Computer Science