Primal-dual approximation algorithms for a packing-covering pair of problems

DOI10.1051/RO:2002005MaRDI QIDQ3148377zbMATH OpenOpenAlexFDO

Authors Sofia Kovaleva, Frits C. R. Spieksma

Publication date 28 November 2002

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=RO_2002__36_1_53_0, http://www.numdam.org/item?id=RO_2002__36_1_53_0/, https://eudml.org/doc/105261

zbMATH Keywords

approximation algorithmsintervalspacking-coveringprimal-dual

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 2081015
• Approximation algorithms for covering/packing integer programs
• scientific article; zbMATH DE number 1263280
• On the approximability of an interval scheduling problem
• The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems

Cites work

• A unified approach to approximating resource allocation and scheduling
• Approximating the throughput of multiple machines in real-time scheduling
• Approximation algorithms for NP-hard problems.
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2080249 (Why is no real title available?)
• Multi-phase algorithms for throughput maximization for real-time scheduling
• On the approximability of an interval scheduling problem
• Primal-dual approximation algorithms for integral flow and multicut in trees

Cited in

(9)

• On approximating four covering and packing problems
• On orthogonally guarding orthogonal polygons with bounded treewidth
• From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
• On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
• scientific article; zbMATH DE number 1138448 (Why is no real title available?)
• scientific article; zbMATH DE number 2081015 (Why is no real title available?)
• scientific article; zbMATH DE number 7040611 (Why is no real title available?)
• Approximation algorithms for maximum weight k-coverings of graphs by packings
• Paired approximation problems and incompatible inapproximabilities

This page was built for publication: Primal-dual approximation algorithms for a packing-covering pair of problems

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