Faster and simpler approximation algorithms for mixed packing and covering problems
From MaRDI portal
Publication:884474
DOI10.1016/j.tcs.2007.02.064zbMath1115.68172MaRDI QIDQ884474
Florian Diedrich, Klaus Jansen
Publication date: 6 June 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.064
optimization; approximation algorithm; Lagrangian decomposition; logarithmic potential; linear and convex programming; packing and covering problem
68W25: Approximation algorithms
Related Items
On randomized fictitious play for approximating saddle points over convex sets, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Packing trees in communication networks, A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An approximation algorithm for the general max-min resource sharing problem
- Approximate Max-Min Resource Sharing for Structured Concave Optimization
- Approximation Algorithm for the Mixed Fractional Packing and Covering Problem
- Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
- An Approximation Algorithm for the General Mixed Packing and Covering Problem
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
- Computing and Combinatorics
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Coordination Complexity of Parallel Price-Directive Decomposition
- Implementation of Approximation Algorithms for the Max-Min Resource Sharing Problem
- Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications
- Experimental and Efficient Algorithms
- On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes
