Geometric Packing under Nonuniform Constraints
From MaRDI portal
Publication:4593249
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.
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
Cites work
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Applications of random sampling in computational geometry. II
- Approximation algorithms for maximum independent set of pseudo-disks
- Approximation algorithms for maximum independent set of pseudo-disks
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Computational geometry. Algorithms and applications.
- Computing the independence number of intersection graphs
- Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
- Fat Triangles Determine Linearly Many Holes
- Geometric approximation algorithms
- Improved bound for the union of fat triangles
- Improved bounds for the union of locally fat objects in the plane
- Improved results on geometric hitting set problems
- Label placement by maximum independent set in rectangles
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Maximum independent set of rectangles
- New approaches to circle packing in a square. With program codes.
- New approaches to covering and packing problems
- Obnoxious Facility Location on Graphs
- On the set multi-cover problem in geometric settings
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Relative \((p,\varepsilon )\)-approximations in geometry
- Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
- Small-size relative ( p ,ε)-approximations for well-behaved range spaces
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
- The design of approximation algorithms
- Weighted geometric set cover via quasi-uniform sampling
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)
