Geometric Packing under Nonuniform Constraints
From MaRDI portal
Publication:4593249
DOI10.1137/120898413zbMATH Open1380.68393arXiv1107.2949OpenAlexW2768906187MaRDI QIDQ4593249FDOQ4593249
Authors: Alina Ene, Benjamin Raichel, Sariel Har-Peled 
Publication date: 22 November 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Abstract: We study the problem of discrete geometric packing. Here, given weighted regions (say in the plane) and points (with capacities), one has to pick a maximum weight subset of the regions such that no point is covered more than its capacity. We provide a general framework and an algorithm for approximating the optimal solution for packing in hypergraphs arising out of such geometric settings. Using this framework we get a flotilla of results on this problem (and also on its dual, where one wants to pick a maximum weight subset of the points when the regions have capacities). For example, for the case of fat triangles of similar size, we show an O(1)-approximation and prove that no PTAS is possible.
Full work available at URL: https://arxiv.org/abs/1107.2949
Recommendations
- Geometric packing under non-uniform constraints
- Packing under convex quadratic constraints
- Packing under convex quadratic constraints
- Compactness theorems for geometric packings
- On a combinatorial structure of the problems of optimal packing of geometric objects
- Dealing with nonregular shapes packing
- scientific article; zbMATH DE number 861345
- Packing ellipsoids by nonlinear optimization
- Packing of convex polytopes into a parallelepiped
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- The design of approximation algorithms
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Applications of random sampling in computational geometry. II
- Weighted geometric set cover via quasi-uniform sampling
- Computational geometry. Algorithms and applications.
- Improved results on geometric hitting set problems
- Title not available (Why is that?)
- New approaches to circle packing in a square. With program codes.
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Geometric approximation algorithms
- Obnoxious Facility Location on Graphs
- Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
- Maximum independent set of rectangles
- Polynomial-time approximation schemes for packing and piercing fat objects
- Approximation algorithms for maximum independent set of pseudo-disks
- Computing the independence number of intersection graphs
- Label placement by maximum independent set in rectangles
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Improved bound for the union of fat triangles
- Fat Triangles Determine Linearly Many Holes
- Improved bounds for the union of locally fat objects in the plane
- Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
- Approximation algorithms for maximum independent set of pseudo-disks
- Relative \((p,\varepsilon )\)-approximations in geometry
- New approaches to covering and packing problems
- On the set multi-cover problem in geometric settings
- The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
- Small-size relative ( p ,ε)-approximations for well-behaved range spaces
Cited In (6)
This page was built for publication: Geometric Packing under Nonuniform Constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593249)
