A Unified Approach to Approximating Partial Covering Problems

DOI10.1007/11841036_43MaRDI QIDQ5449551zbMATH OpenOpenAlexFDO

Authors Jochen Könemann, Ojas Parekh, Danny Segev

Publication date 11 March 2008

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

Full work available at URL https://doi.org/10.1007/11841036_43

Mathematics Subject Classification ID

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

Recommendations

• A unified approach to approximating partial covering problems
• Approximation algorithms for partial covering problems
• scientific article; zbMATH DE number 1754596
• Approximation algorithm for the partial set multi-cover problem
• On partial covering for geometric set systems

Cited in

(18)

• One for the price of two: a unified approach for approximating covering problems
• A PTAS for the cardinality constrained covering with unit balls
• The maximum vertex coverage problem on bipartite graphs
• An approximation algorithm for \(P\)-prize-collecting set cover problem
• From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
• scientific article; zbMATH DE number 5773533 (Why is no real title available?)
• On Lagrangian Relaxation and Subset Selection Problems
• scientific article; zbMATH DE number 1754596 (Why is no real title available?)
• Compact oblivious routing
• On uniform covering, adaptive random search and raspberries
• A unified approach to approximating partial covering problems
• Implicit branching and parameterized partial cover problems
• Prototype selection for interpretable classification
• Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
• Partial multicuts in trees
• A GRASP algorithm to solve the unicost set covering problem
• Approximation algorithms for partially covering with edges
• On the positive-negative partial set cover problem

This page was built for publication: A Unified Approach to Approximating Partial Covering Problems

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