On Partial Covering For Geometric Set Systems
From MaRDI portal
Publication:5115815
DOI10.4230/LIPIcs.SoCG.2018.47zbMath1489.68359arXiv1711.04882OpenAlexW2962723793MaRDI QIDQ5115815
Tanmay Inamdar, Kasturi R. Varadarajan
Publication date: 18 August 2020
Full work available at URL: https://arxiv.org/abs/1711.04882
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
Algorithms for covering multiple submodular constraints and applications, Minimum power partial multi-cover on a line, On fair covering and hitting problems, On colorful vertex and edge cover problems, A parameterized approximation scheme for generalized partial vertex cover, Few cuts meet many point sets, Parallel approximation for partial set cover, Unnamed Item, Treewidth, crushing and hyperbolic volume, Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks, A primal-dual algorithm for the minimum power partial cover problem, Approximation algorithm for minimum partial multi-cover under a geometric setting, A technique for obtaining true approximations for \(k\)-center with covering constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved performance of the greedy algorithm for partial cover
- Improved approximations for guarding 1.5-dimensional terrains
- Improved results on geometric hitting set problems
- A unified approach to approximating partial covering problems
- Improved approximation for guarding simple galleries from the perimeter
- Improved approximation algorithms for geometric set cover
- Hitting sets when the VC-dimension is small
- \(\epsilon\)-nets and simplex range queries
- The budgeted maximum coverage problem
- On combinatorial approximation of covering 0-1 integer programs and partial set cover
- New applications of random sampling in computational geometry
- Almost optimal set covers in finite VC-dimension
- Geometric red-blue set cover for unit squares and related problems
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- Using Homogeneous Weights for Approximating the Partial Cover Problem
- Weighted geometric set cover via quasi-uniform sampling
- Guarding terrains via local search
- A threshold of ln n for approximating set cover
- PTAS for Weighted Set Cover on Unit Squares
- Multiobjective Disk Cover Admits a PTAS
- Approximation schemes for covering and packing problems in image processing and VLSI
- Packing and Covering with Non-Piercing Regions
- Polynomial-time approximation schemes for packing and piercing fat objects
- Approximation algorithms for partial covering problems
- Applications of approximation algorithms to cooperative games
- Analytical approach to parallel repetition
- Epsilon nets and union complexity
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
