Partial multicovering and the \(d\)-consecutive ones property

DOI10.1016/j.disopt.2011.05.004zbMath1235.90129OpenAlexW1989815994MaRDI QIDQ408373

Dror Rawitz, Shimon (Moni) Shahar

Publication date: 5 April 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2011.05.004

zbMATH Keywords

approximation algorithms\(d\)-interval stabbingpartial multicoveringprize collecting multicovering

Mathematics Subject Classification ID

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

Related Items

Local ratio method on partial set multi-cover, Approximation algorithm for partial positive influence problem in social network

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved performance of the greedy algorithm for partial cover
• A unified approach to approximating partial covering problems
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• Rounding to an integral program
• Approximation algorithms for hitting objects with straight lines
• Improved complexity bounds for location problems on the real line
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• On approximation of the submodular set cover problem
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• On targeting Markov segments
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Handbook of Approximation Algorithms and Metaheuristics
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• Approximation algorithms for partial covering problems
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Scheduling Split Intervals
• On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems