Sequential and Parallel Algorithms for Mixed Packing and Covering

Abstract

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).

References in corpus (1)

• On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms

Cited by in corpus (30)

• A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs
• On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms
• Local Computation: Lower and Upper Bounds
• Distributed Assignment with Limited Communication for Multi-Robot Multi-Target Tracking
• Demand Prediction and Placement Optimization for Electric Vehicle Charging Stations
• Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming
• An optimal local approximation algorithm for max-min linear programs
• Parallel approximation of min-max problems
• Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
• Tight Bounds for Approximate Carathéodory and Beyond
• A parallel approximation algorithm for mixed packing and covering semidefinite programs
• Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction
• On-Line End-to-End Congestion Control
• Faster Parallel Solver for Positive Linear Programs via Dynamically-Bucketed Selective Coordinate Descent
• Better Algorithms for Individually Fair $k$-Clustering
• Nearly Linear-Work Algorithms for Mixed Packing/Covering and Facility-Location Linear Programs
• Near-Optimal Distributed Maximum Flow
• Using Optimization to Solve Positive LPs Faster in Parallel
• Polynomial-Space Approximation of No-Signaling Provers
• A Parallelizable Acceleration Framework for Packing Linear Programs
• Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints
• Non-Signaling Proofs with $O(\sqrt{\log n})$ Provers are in PSPACE
• Parallel approximation of non-interactive zero-sum quantum games
• Interactive proofs with competing teams of no-signaling provers
• Improved Convergence for ${\ell }_{\infty }$ and ${\ell }_1$ Regression via Iteratively Reweighted Least Squares
• Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems
• Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design
• Parallel Approximation Algorithms for Facility-Location Problems
• Vertex Sparsifiers and Abstract Rounding Algorithms
• On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets