Computer Science – Data Structures and Algorithms
Scientific paper
2002-05-18
IEEE Symposium on Foundations of Computer Science (2001)
Computer Science
Data Structures and Algorithms
Scientific paper
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. This paper gives approximation algorithms for the general class of problems. The sequential algorithm is a simple greedy algorithm that can be implemented to find an epsilon-approximate solution in O(epsilon^-2 log m) linear-time iterations. The parallel algorithm does comparable work but finishes in polylogarithmic time. 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 Michael Luby and Noam Nisan (1993) and Naveen Garg and Jochen Konemann (1998).
No associations
LandOfFree
Sequential and Parallel Algorithms for Mixed Packing and Covering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Sequential and Parallel Algorithms for Mixed Packing and Covering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sequential and Parallel Algorithms for Mixed Packing and Covering will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-599151