Approximation algorithms for partial covering problems. Extended abstract

DOI10.1007/3-540-48224-5_19MaRDI QIDQ4535021zbMATH OpenFDO

Authors Samir Khuller, Aravind Srinivasan, R. B. Gandhi

Publication date 12 June 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2076/20760225, http://hdl.handle.net/1903/1129

zbMATH Keywords

approximation algorithmspartial coveringprimal-dual methodsrandomized roundingset coververtex cover

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Approximation algorithms for partial covering problems
• A unified approach to approximating partial covering problems
• A Unified Approach to Approximating Partial Covering Problems
• An approximation algorithm for the total covering problem
• Approximation algorithm for the partial set multi-cover problem
• Approximation algorithms for partially covering with edges
• An approximation algorithm for the partial covering 0-1 integer program
• Subexponential algorithms for partial cover problems
• Subexponential algorithms for partial cover problems
• Approximation algorithm for partial set multicover versus full set multicover

Cited in

(28)

• Computing small partial coverings
• On combinatorial approximation of covering 0-1 integer programs and partial set cover
• On approximation of the submodular set cover problem
• One for the price of two: a unified approach for approximating covering problems
• Parallel approximation for partial set cover
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Decision tree classification with bounded number of errors
• Using homogeneous weights for approximating the partial cover problem
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality
• Approximation algorithms for union and intersection covering problems
• Improved performance of the greedy algorithm for partial cover
• Implicit branching and parameterized partial cover problems (extended abstract)
• scientific article; zbMATH DE number 5773533 (Why is no real title available?)
• An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• scientific article; zbMATH DE number 1305393 (Why is no real title available?)
• One for the price of two: A unified approach for approximating covering problems
• Improved approximation algorithms for the partial vertex cover problem
• Approximation algorithms for partial covering problems
• On partial covering for geometric set systems
• A Unified Approach to Approximating Partial Covering Problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Approximation algorithms for minimum weight partial connected set cover problem
• A unified approach to approximating partial covering problems
• On approximating partial scenario set cover
• On the multi-radius cover problem

This page was built for publication: Approximation algorithms for partial covering problems. Extended abstract

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