Geometric Packing under Nonuniform Constraints

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

zbMATH Keywords

optimizationindependent setrounding scheme

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

Non-uniform packings

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