Efficient Approximations for the Online Dispersion Problem

DOI10.4230/LIPICS.ICALP.2017.11zbMATH Open1441.68264OpenAlexW2947105928MaRDI QIDQ5111340FDOQ5111340

Authors: Jing Chen, Bo Li, Yingkai Li 

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1704.06823

Recommendations

• Efficient approximations for the online dispersion problem
• Obtaining online approximation algorithms for facility dispersion from offline algorithms
• Approximation algorithms for dispersion problems
• Approximation of geometric dispersion problems

zbMATH Keywords

dispersiononline algorithmsgeometric optimizationpackingcompetitive algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Cited In (5)

• Obtaining online approximation algorithms for facility dispersion from offline algorithms
• An on-line assignment problem with random effectiveness and costly information
• A competitive strategy for distance-aware online shape allocation
• A competitive strategy for distance-aware online shape allocation
• Randomized approximation and online algorithms for assignment problems

This page was built for publication: Efficient Approximations for the Online Dispersion Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111340)