A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs
arXiv:0801.1987 · doi:10.1007/s00453-013-9771-6
Abstract
We give an approximation algorithm for packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm computes feasible primal and dual solutions whose costs are within a factor of 1+eps of the optimal cost in time O((r+c)log(n)/eps^2 + n).
corrected version of FOCS 2007 paper: 10.1109/FOCS.2007.62. Accepted to Algorithmica, 2013
References in corpus (2)
Cited by in corpus (10)
- On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms
- Practical Bounds on Optimal Caching with Variable Object Sizes
- Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction
- Faster Parallel Solver for Positive Linear Programs via Dynamically-Bucketed Selective Coordinate Descent
- Functions with average smoothness: structure, algorithms, and learning
- Nearly Linear-Work Algorithms for Mixed Packing/Covering and Facility-Location Linear Programs
- Using Optimization to Solve Positive LPs Faster in Parallel
- Comparison-Based Indexing From First Principles
- Faster Primal-Dual Convergence for Min-Max Resource Sharing and Stronger Bounds via Local Weak Duality
- Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial