On capacitated set cover problems

DOI10.1007/978-3-642-22935-0_4MaRDI QIDQ3088080zbMATH OpenOpenAlexFDO

Authors N. Bansal, Ravishankar Krishnaswamy, Barna Saha

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22935-0_4

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Covering Problems with Hard Capacities
• Set cover revisited: hypergraph cover with hard capacities
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• On approximation of the submodular set cover problem
• scientific article; zbMATH DE number 2119748

Cites work

• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• A unified approach to approximating resource allocation and scheduling
• Almost optimal set covers in finite VC-dimension
• Approximating covering integer programs with multiplicity constraints
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On column-restricted and priority covering integer programs
• On the approximability of some network design problems
• Weighted geometric set cover via quasi-uniform sampling

Cited in

(8)

• scientific article; zbMATH DE number 4106856 (Why is no real title available?)
• Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• On capacitated covering with unit balls
• scientific article; zbMATH DE number 3912199 (Why is no real title available?)
• Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time
• Fixed-parameter algorithms for unsplittable flow cover
• Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time

This page was built for publication: On capacitated set cover problems

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