Geometric Packing under Nonuniform Constraints
From MaRDI portal
Publication:4593249
DOI10.1137/120898413zbMath1380.68393arXiv1107.2949OpenAlexW2768906187MaRDI QIDQ4593249
Alina Ene, Benjamin Raichel, Sariel Har-Peled
Publication date: 22 November 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1107.2949
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved results on geometric hitting set problems
- Relative \((p,\varepsilon )\)-approximations in geometry
- New approaches to circle packing in a square. With program codes.
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Label placement by maximum independent set in rectangles
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Applications of random sampling in computational geometry. II
- Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
- Weighted geometric set cover via quasi-uniform sampling
- The Design of Approximation Algorithms
- Obnoxious Facility Location on Graphs
- Fat Triangles Determine Linearly Many Holes
- Polynomial-time approximation schemes for packing and piercing fat objects
- Small-size relative ( p ,ε)-approximations for well-behaved range spaces
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Approximation algorithms for maximum independent set of pseudo-disks
- On the set multi-cover problem in geometric settings
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
- Improved Bounds for the Union of Locally Fat Objects in the Plane
