On interval and circular-arc covering problems

DOI10.1007/S10479-018-3025-6zbMATH Open1493.68368OpenAlexW2887997824WikidataQ129344302 ScholiaQ129344302MaRDI QIDQ2327673FDOQ2327673

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

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

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)

Cites Work

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

Cited In (7)

• Fuzzy versions of the covering circle problem
• Optimal circle covering problems and their applications
• Capacitated Arc Stabbing
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)