On interval and circular-arc covering problems

DOI10.1007/S10479-018-3025-6MaRDI QIDQ2327673zbMATH OpenOpenAlexWikidataFDO

Authors Reuven Cohen, Mira Gonen

Publication date 15 October 2019

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-018-3025-6

zbMATH Keywords

optimizationdynamic programmingcovering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On nonlinear multi-covering problems
• The conditional covering problem on unweighted interval graphs
• scientific article; zbMATH DE number 1555975
• \(k\) best cuts for circular-arc graphs
• On a circle-cover minimization problem

Cites work

• scientific article; zbMATH DE number 4099049 (Why is no real title available?)
• scientific article; zbMATH DE number 177560 (Why is no real title available?)
• scientific article; zbMATH DE number 1263202 (Why is no real title available?)
• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 6472586 (Why is no real title available?)
• A heuristic for the p-center problem in graphs
• A threshold of ln n for approximating set cover
• Algorithmic construction of sets for k -restrictions
• Algorithms for the set covering problem
• Almost optimal set covers in finite VC-dimension
• Circular-arc graph coloring: On chords and circuits in the meeting graph
• Clustering heuristics for set covering
• Clustering to minimize the maximum intercluster distance
• Covering Points by Unit Disks of Fixed Location
• Covering a set of points in multidimensional space
• Easy and hard bottleneck location problems
• Efficient algorithms for the weighted \(k\)-center problem on a real line
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Exact and approximation algorithms for clustering
• Fast approximation algorithms for a nonconvex covering problem
• Geometric applications of a randomized optimization technique
• Hitting sets when the VC-dimension is small
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Improved results on geometric hitting set problems
• On column-restricted and priority covering integer programs
• On nonlinear multi-covering problems
• On the Complexity of Some Common Geometric Location Problems
• On the complexity of some geometric problems in unbounded dimension
• On the computational complexity of centers locating in a graph
• On the ratio of optimal integral and fractional covers
• Optimal packing and covering in the plane are NP-complete
• Optimizing over Consecutive 1's and Circular 1's Constraints
• PTAS for weighted set cover on unit squares
• Pareto optimality and a class of set covering heuristics
• The maximum reliability location problem and \(\alpha\)-reliable p-center problem: Derivatives of the probabilistic location set covering problem
• The slab dividing approach to solve the Euclidean \(P\)-center problem
• Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem

Cited in

(7)

• Fuzzy versions of the covering circle problem
• Optimal circle covering problems and their applications
• Capacitated Arc Stabbing
• scientific article; zbMATH DE number 1555975 (Why is no real title available?)
• scientific article; zbMATH DE number 3967928 (Why is no real title available?)
• Online algorithms for the maximum \(k\)-interval coverage problem
• On nonlinear multi-covering problems

This page was built for publication: On interval and circular-arc covering problems

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