Faster and simpler approximation algorithms for mixed packing and covering problems

DOI10.1016/j.tcs.2007.02.064zbMath1115.68172OpenAlexW2155224464MaRDI 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

zbMATH Keywords

optimizationapproximation algorithmLagrangian decompositionlogarithmic potentiallinear and convex programmingpacking and covering problem

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items (4)

A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs ⋮ Approximation algorithms for general packing problems and their application to the multicast congestion problem ⋮ On randomized fictitious play for approximating saddle points over convex sets ⋮ Packing trees in communication networks

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Faster and simpler approximation algorithms for mixed packing and covering problems