Efficient Approximations for the Online Dispersion Problem

DOI10.1137/17M1131027zbMath1421.68168arXiv1704.06823OpenAlexW2964196438WikidataQ128073505 ScholiaQ128073505MaRDI QIDQ4634023

Bo Li, Jing Chen, Yingkai Li

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

zbMATH Keywords

dispersiononline algorithmscompetitive ratiopackinggeometric optimization

Mathematics Subject Classification ID

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

• kepler98

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