Faster and simpler approximation algorithms for mixed packing and covering problems

DOI10.1016/J.TCS.2007.02.064MaRDI QIDQ884474zbMATH OpenOpenAlexFDO

Authors 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 algorithmlogarithmic potentialLagrangian decompositionlinear and convex programmingpacking and covering problem

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• An Approximation Algorithm for the General Mixed Packing and Covering Problem
• scientific article; zbMATH DE number 2163022
• Approximation Algorithm for the Mixed Fractional Packing and Covering Problem
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 2163027

Cites work

• scientific article; zbMATH DE number 4095196 (Why is no real title available?)
• scientific article; zbMATH DE number 1086924 (Why is no real title available?)
• scientific article; zbMATH DE number 1754632 (Why is no real title available?)
• scientific article; zbMATH DE number 910872 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• A fast approximation scheme for fractional covering problems with variable upper bounds
• An Approximation Algorithm for the General Mixed Packing and Covering Problem
• 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
• Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications
• Computing and Combinatorics
• Coordination Complexity of Parallel Price-Directive Decomposition
• Experimental and Efficient Algorithms
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
• Implementation of Approximation Algorithms for the Max-Min Resource Sharing Problem
• Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
• On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes

Cited in

(15)

• Approximation and Online Algorithms
• Approximation Algorithm for the Mixed Fractional Packing and Covering Problem
• Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
• Unified acceleration method for packing and covering problems via diameter reduction
• Approximation algorithms for general packing problems and their application to the multicast congestion problem
• Black-box acceleration of monotone convex program solvers
• scientific article; zbMATH DE number 2163022 (Why is no real title available?)
• Cover and pack inequalities for (mixed) integer programming
• An Approximation Algorithm for the General Mixed Packing and Covering Problem
• Pseudo-polynomial time algorithms for combinatorial food mixture packing problems
• Faster fixed-parameter tractable algorithms for matching and packing problems
• scientific article; zbMATH DE number 2163027 (Why is no real title available?)
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
• Packing trees in communication networks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q884474)