Exact multi-covering problems with geometric sets
From MaRDI portal
Publication:2075389
DOI10.1007/s00224-021-10050-zOpenAlexW3184813396MaRDI QIDQ2075389
Neeldhara Misra, Saket Saurabh, Pradeesha Ashok, Sudeshna Kolay
Publication date: 14 February 2022
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-021-10050-z
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Computing methodologies and applications (68Uxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Randomized approximation of bounded multicovering problems
- A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
- On the parameterized complexity of multiple-interval graph problems
- A fast approximation algorithm for the multicovering problem
- Optimal packing and covering in the plane are NP-complete
- The multicovering problem
- On the complexity of locating linear facilities in the plane
- The parameterized complexity of unique coverage and its variants
- Covering things with things
- Parametrized complexity theory.
- Weighted Geometric Set Multi-cover via Quasi-uniform Sampling
- On the set multicover problem in geometric settings
- Unique Covering Problems with Geometric Sets
- Combination Can Be Hard: Approximability of the Unique Coverage Problem
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Fast approximation algorithms for a nonconvex covering problem
- Kernelization Lower Bounds Through Colors and IDs
- Reducibility among Combinatorial Problems
- PTAS for geometric hitting set problems via local search
- Algorithms – ESA 2005
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Local search strikes again: PTAS for variants of geometric covering and packing
This page was built for publication: Exact multi-covering problems with geometric sets
