Document Open Access Logo

Efficient Approximations for the Online Dispersion Problem

Authors Jing Chen, Bo Li, Yingkai Li

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.11.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Jing Chen
Bo Li
Yingkai Li

Cite As Get BibTex

Jing Chen, Bo Li, and Yingkai Li. Efficient Approximations for the Online Dispersion Problem. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.11

Abstract

The dispersion problem has been widely studied in computational geometry and facility location, and is closely related to the packing problem. The goal is to locate n points (e.g., facilities or persons) in a k-dimensional polytope, so that they are far away from each other and from the boundary of the polytope. In many real-world scenarios however, the points arrive and depart at different times, and decisions must be made without knowing future events. Therefore we study, for the first time in the literature, the online dispersion problem in Euclidean space.

There are two natural objectives when time is involved: the all-time worst-case (ATWC) problem tries to  maximize the minimum distance that ever appears at any time; and the cumulative distance (CD) problem tries to maximize the integral of the minimum distance throughout the whole time interval. Interestingly, the online  problems are highly non-trivial even on a segment. For cumulative distance, this remains the case even when the problem is time-dependent but offline, with all the arriving and departure times given in advance.

For the online ATWC problem on a segment, we construct a deterministic polynomial-time algorithm which is (2ln2+epsilon)-competitive, where epsilon>0 can be arbitrarily small and the algorithm's running time is polynomial in 1/epsilon. We show this algorithm is actually optimal. For the same problem in a square, we provide a 1.591-competitive algorithm and a 1.183 lower-bound. Furthermore, for arbitrary k-dimensional polytopes with k>=2, we provide a 2/(1-epsilon)-competitive algorithm and a 7/6 lower-bound. All our lower-bounds come from the structure of the online problems and hold even when computational complexity is not a concern. Interestingly, for the offline CD problem in arbitrary k-dimensional polytopes, we provide a polynomial-time black-box reduction to the online ATWC problem, and the resulting competitive ratio increases by a factor of at most 2. Our techniques also apply to online dispersion problems with different boundary conditions.

Subject Classification

Keywords
  • dispersion
  • online algorithms
  • geometric optimization
  • packing
  • competitive algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Shimon Abravaya and Michael Segal. Maximizing the number of obnoxious facilities to locate within a bounded region. Computers & Operations Research, 37(1):163-171, 2010. Google Scholar
  2. Christoph Baur and Sándor P. Fekete. Approximation of geometric dispersion problems. Algorithmica, 30(3):451-470, 2001. Google Scholar
  3. Boaz Ben-Moshe, Matthew J Katz, and Michael Segal. Obnoxious facility location: Complete service with minimal harm. International Journal of Computational Geometry & Applications, 10(06):581-592, 2000. Google Scholar
  4. Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, René van Oostrum, and Alexander Wolff. A polynomial-time approximation algorithm for a geometric dispersion problem. In International Computing and Combinatorics Conference, pages 166-175. Springer, 2006. Google Scholar
  5. Benjamin Birnbaum and Kenneth J. Goldman. An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs. Algorithmica, 55(1):42-59, 2009. Google Scholar
  6. Alfonso Cevallos, Friedrich Eisenbrand, and Rico Zenklusen. Max-sum diversity via convex programming. In Proceedings of the 32nd Symposium on Computational Geometry (SoCG), pages 26:1-26:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  7. Alfonso Cevallos, Friedrich Eisenbrand, and Rico Zenklusen. Local search for max-sum diversification. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 130-142. SIAM, 2017. Google Scholar
  8. Jing Chen, Bo Li, and Yingkai Li. Efficient approximations for the online dispersion problem. arXiv:1704.06823, 2017. Full version. Google Scholar
  9. Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska. The sphere packing problem in dimension 24. arXiv:1603.06518, 2016. Google Scholar
  10. Lester E. Dubins and Edwin H. Spanier. How to cut a cake fairly. The American Mathematical Monthly, 68(1):1-17, 1961. Google Scholar
  11. Adrian Dumitrescu and Minghui Jiang. Dispersion in disks. Theory of Computing Systems, 51(2):125-142, 2012. Google Scholar
  12. Leah Epstein and Rob Van Stee. Optimal online algorithms for multidimensional packing problems. SIAM Journal on Computing, 35(2):431-448, 2005. Google Scholar
  13. Leah Epstein and Rob Van Stee. Bounds for online bounded space hypercube packing. Discrete optimization, 4(2):185-197, 2007. Google Scholar
  14. L. Fejes Tóth. Über die dichteste kugellagerung. Mathematische Zeitschrift, 48(1):676-684, 1942. Google Scholar
  15. Sándor P. Fekete and Henk Meijer. Maximum dispersion and geometric maximum weight cliques. Algorithmica, 38(3):501-511, 2004. Google Scholar
  16. Dimitris Fotakis. Incremental algorithms for facility location and k-median. Theoretical Computer Science, 361(2):275-313, 2006. Google Scholar
  17. Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008. Google Scholar
  18. Robert J. Fowler, Michael S. Paterson, and Steven L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Information processing letters, 12(3):133-137, 1981. Google Scholar
  19. Eric Friedman, Christos-Alexandros Psomas, and Shai Vardi. Dynamic fair division with minimal disruptions. In Proceedings of the sixteenth ACM conference on Economics and Computation, pages 697-713. ACM, 2015. Google Scholar
  20. Thomas C. Hales. A proof of the Kepler conjecture. Annals of mathematics, 162(3):1065-1185, 2005. Google Scholar
  21. Mhand Hifi and Rym M'hallah. A literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research, 2009:150624:1-150624:22, 2009. Google Scholar
  22. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM (JACM), 32(1):130-136, 1985. Google Scholar
  23. Pedro Hokama, Flávio K. Miyazawa, and Rafael C. S. Schouery. A bounded space algorithm for online circle packing. Information Processing Letters, 116(5):337-342, 2016. Google Scholar
  24. Wenqi Huang and Tao Ye. Greedy vacancy search algorithm for packing equal circles in a square. Operations Research Letters, 38(5):378-382, 2010. Google Scholar
  25. Matthew J. Katz, Klara Kedem, and Michael Segal. Improved algorithms for placing undesirable facilities. Computers & Operations Research, 29(13):1859-1872, 2002. Google Scholar
  26. Marco Locatelli and Ulrich Raber. Packing equal circles in a square: a deterministic global optimization approach. Discrete Applied Mathematics, 122(1):139-166, 2002. Google Scholar
  27. Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. SIAM Journal on Computing, 32(3):816-832, 2003. Google Scholar
  28. Adam Meyerson. Online facility location. In 42rd Annual IEEE Symposium on Foundations of Computer Science, pages 426-431. IEEE, 2001. Google Scholar
  29. Flávio K Miyazawa, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Maxim Sviridenko, and Yoshiko Wakabayashi. Polynomial-time approximation schemes for circle packing problems. In European Symposium on Algorithms, pages 713-724. Springer, 2014. Google Scholar
  30. Ronald Peikert, Diethelm Würtz, Michael Monagan, and Claas de Groot. Packing circles in a square: a review and new results. In System Modelling and Optimization: Proceedings of the 15th IFIP Conference, Zurich, Switzerland, September 2-6, 1991, pages 45-54. Springer, 1992. Google Scholar
  31. Zhongping Qin, Yinfeng Xu, and Binhai Zhu. On some optimization problems in obnoxious facility location. In International Computing and Combinatorics Conference, pages 320-329. Springer, 2000. Google Scholar
  32. Sekharipuram S. Ravi, Daniel J. Rosenkrantz, and Giri K. Tayi. Heuristic and special case algorithms for dispersion problems. Operations Research, 42(2):299-310, 1994. Google Scholar
  33. Claude Ambrose Rogers. Existence theorems in the geometry of numbers. Annals of Mathematics, pages 994-1002, 1947. Google Scholar
  34. Daniel J. Rosenkrantz, Giri K. Tayi, and S. S. Ravi. Obtaining online approximation algorithms for facility dispersion from offline algorithms. Networks, 47(4):206-217, 2006. Google Scholar
  35. J. Schaer. The densest packing of nine circles in a square. Canad. Math. Bull, 8:273-277, 1965. Google Scholar
  36. J. Schaer and A. Meir. On a geometric extremum problem. Canad. Math. Bull, 8:21-27, 1965. Google Scholar
  37. B. L. Schwartz. Separating points in a square. J. Recr. Math, 3:195-204, 1970. Google Scholar
  38. Steven S. Seiden. On the online bin packing problem. Journal of the ACM (JACM), 49(5):640-671, 2002. Google Scholar
  39. Hugo Steinhaus. The problem of fair division. Econometrica, 16:101-104, 1948. Google Scholar
  40. Walter Stromquist. How to cut a cake fairly. The American Mathematical Monthly, 87(8):640-644, 1980. Google Scholar
  41. Péter Gábor Szabó and Eckard Specht. Packing up to 200 equal circles in a square. In Models and Algorithms for Global Optimization, pages 141-156. Springer, 2007. Google Scholar
  42. Maryna Viazovska. The sphere packing problem in dimension 8. arXiv:1603.04246, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact