Efficient Approximations for the Online Dispersion Problem
From MaRDI portal
Publication:4634023
DOI10.1137/17M1131027zbMath1421.68168arXiv1704.06823OpenAlexW2964196438WikidataQ128073505 ScholiaQ128073505MaRDI QIDQ4634023
Publication date: 7 May 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.06823
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)
Related Items (2)
Two-facility location games with distance requirement ⋮ Two-facility Location Games with Minimum Distance Requirement
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- kepler98
- Polynomial-time approximation schemes for circle and other packing problems
- A literature review on circle and sphere packing problems: models and methodologies
- Greedy vacancy search algorithm for packing equal circles in a square
- Dispersion in disks
- Maximizing the number of obnoxious facilities to locate within a bounded region
- Optimal packing and covering in the plane are NP-complete
- Packing equal circles in a square: A deterministic global optimization approach
- Maximum dispersion and geometric maximum weight cliques
- Improved algorithms for placing undesirable facilities
- The sphere packing problem in dimension 8
- The sphere packing problem in dimension \(24\)
- An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
- Bounds for online bounded space hypercube packing
- On the competitive ratio for online facility location
- A proof of the Kepler conjecture
- Incremental algorithms for facility location and \(k\)-median
- Über die dichteste Kugellagerung
- Existence theorems in the geometry of numbers
- OBNOXIOUS FACILITY LOCATION: COMPLETE SERVICE WITH MINIMAL HARM
- Max-sum diversity via convex programming
- Approximation algorithms for spreading points
- On the online bin packing problem
- Approximation schemes for covering and packing problems in image processing and VLSI
- How to Cut A Cake Fairly
- How to Cut a Cake Fairly
- Heuristic and Special Case Algorithms for Dispersion Problems
- Local Search for Max-Sum Diversification
- The Online Median Problem
- A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
- Optimal Online Algorithms for Multidimensional Packing Problems
- Obtaining online approximation algorithms for facility dispersion from offline algorithms
- On a Geometric Extremum Problem
- The Densest Packing of 9 Circles in a Square
- Approximation of geometric dispersion problems
- A bounded space algorithm for online circle packing
This page was built for publication: Efficient Approximations for the Online Dispersion Problem
