Obtaining online approximation algorithms for facility dispersion from offline algorithms

DOI10.1002/NET.20109MaRDI QIDQ5487808zbMATH OpenOpenAlexFDO

Authors S. S. Ravi, Daniel J. Rosenkrantz, Giri Kumar Tayi

Publication date 12 September 2006

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20109

zbMATH Keywords

competitive ratioonline algorithmapproximation ratiooffline algorithmfacility dispersion

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Recommendations

• Efficient Approximations for the Online Dispersion Problem
• Efficient approximations for the online dispersion problem
• The Online Median Problem
• Approximation algorithms for dispersion problems
• scientific article; zbMATH DE number 177561

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• Online algorithms. The state of the art
• Online seat reservations via offline seating arrangements.
• Reducing truth-telling online mechanisms to online optimization

Cited in

(3)

• Efficient approximations for the online dispersion problem
• An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
• Online facility location with deletions

This page was built for publication: Obtaining online approximation algorithms for facility dispersion from offline algorithms

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