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

DOI10.1051/ro:2002005zbMath1027.90107OpenAlexW2163145578MaRDI QIDQ3148377

Frits C. R. Spieksma, Sofia Kovaleva

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

zbMATH Keywords

intervalsapproximation algorithmsprimal-dualpacking-covering

Mathematics Subject Classification ID

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

Related Items (1)

On orthogonally guarding orthogonal polygons with bounded treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Multi-phase algorithms for throughput maximization for real-time scheduling
• On the approximability of an interval scheduling problem
• Approximating the Throughput of Multiple Machines in Real-Time Scheduling
• A unified approach to approximating resource allocation and scheduling

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