Document Open Access Logo

The Online House Numbering Problem: Min-Max Online List Labeling

Authors William E. Devanny, Jeremy T. Fineman, Michael T. Goodrich, Tsvi Kopelowitz

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.33.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

William E. Devanny
Jeremy T. Fineman
Michael T. Goodrich
Tsvi Kopelowitz

Cite As Get BibTex

William E. Devanny, Jeremy T. Fineman, Michael T. Goodrich, and Tsvi Kopelowitz. The Online House Numbering Problem: Min-Max Online List Labeling. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.33

Abstract

We introduce and study the online house numbering problem, where houses are added arbitrarily along a road and must be assigned labels to maintain their ordering along the road.  The online house numbering problem is related to classic online list labeling problems, except that the optimization goal here is to minimize the maximum number of times that any house is relabeled. We provide several algorithms that achieve interesting tradeoffs between upper bounds on the number of maximum relabels per element and the number of bits used by labels.

Subject Classification

Keywords
  • house numbering
  • list labeling
  • file maintenance

Metrics

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

References

  1. Amihood Amir, Martin Farach, Ramana M Idury, Johannes A Lapoutre, and Alejandro A Schaffer. Improved dynamic dictionary matching. Information and Computation, 119(2):258-282, 1995. Google Scholar
  2. Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Moshe Lewenstein, and Noa Lewenstein. Managing unbounded-length keys in comparison-driven data structures with applications to online indexing. SIAM J. Comput., 43(4):1396-1416, 2014. Google Scholar
  3. Avraham Ben-Aroya and Sivan Toledo. Competitive analysis of flash-memory algorithms. In Yossi Azar and Thomas Erlebach, editors, European Symp. on Algorithms (ESA), volume 4168 of LNCS, pages 100-111. Springer, 2006. URL: http://dx.doi.org/10.1007/11841036_12.
  4. M. A. Bender, E. D. Demaine, and M. Farach-Colton. Cache-oblivious B-trees. SIAM Journal on Computing, 35(2):341-358, 2005. Google Scholar
  5. M. A. Bender, Z. Duan, J. Iacono, and J. Wu. A locality-preserving cache-oblivious dynamic dictionary. Journal of Algorithms, 3(2):115-136, 2004. Google Scholar
  6. Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito. Two simplified algorithms for maintaining order in a list. In Rolf H. Möhring and Rajeev Raman, editors, Euro. Symp. on Algorithms (ESA), volume 2461 of LNCS, pages 152-164. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45749-6_17.
  7. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, and Pablo Montes. File maintenance: When in doubt, change the layout! In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 1503-1522, 2017. Google Scholar
  8. R. Bez, E. Camerlenghi, A. Modelli, and A. Visconti. Introduction to flash memory. Proceedings of the IEEE, 91(4):489-502, 2003. URL: http://dx.doi.org/10.1109/JPROC.2003.811702.
  9. Dany Breslauer and Giuseppe F. Italiano. Near real-time suffix tree construction via the fringe marked ancestor problem. J. Discrete Algorithms, 18:32-48, 2013. Google Scholar
  10. Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob. Cache oblivious search trees via binary trees of small height. In Proc. 13th Annual Symposium on Discrete Algorithms (SODA), pages 39-48, 2002. URL: http://www.brics.dk/~gerth/Papers/soda02.ps.gz.
  11. Jan Bulánek, Michal Koucký, and Michael E. Saks. Tight lower bounds for the online labeling problem. SIAM J. Comput., 44(6):1765-1797, 2015. Google Scholar
  12. Shimin Chen, Phillip B. Gibbons, and Suman Nath. Rethinking database algorithms for phase change memory. In 5th Conf. on Innovative Data Systems Research (CIDR), pages 21-31, 2011. URL: http://www.cidrdb.org/cidr2011/Papers/CIDR11_Paper3.pdf.
  13. Richard Cole and Ramesh Hariharan. Dynamic LCA queries on trees. SIAM J. Comput., 34(4):894-923, 2005. URL: http://dx.doi.org/10.1137/S0097539700370539.
  14. P. Dietz and D. Sleator. Two algorithms for maintaining order in a list. In 19th ACM Symp. on Theory of Computing (STOC), pages 365-372, 1987. URL: http://dx.doi.org/10.1145/28395.28434.
  15. Paul F. Dietz. Fully persistent arrays (extended array). In Algorithms and Data Structures, Workshop WADS'89, Ottawa, Canada, August 17-19, 1989, Proceedings, pages 67-74, 1989. Google Scholar
  16. Paul F. Dietz and Rajeev Raman. Persistence, amortization and randomization. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 78-88, 1991. Google Scholar
  17. Yuval Emek and Amos Korman. New bounds for the controller problem. Distributed Computing, 24(3-4):177-186, 2011. Google Scholar
  18. David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amnon Nissenzweig. Sparsification—a technique for speeding up dynamic graph algorithms. Journal of the ACM (JACM), 44(5):669-696, 1997. Google Scholar
  19. David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, and Paweł Pszona. Wear minimization for cuckoo hashing: How not to throw a lot of eggs into one basket. In Joachim Gudmundsson and Jyrki Katajainen, editors, 13th Int. Symp. on Experimental Algorithms (SEA), volume 8504 of LNCS, pages 162-173, Cham, 2014. Springer. Google Scholar
  20. David Eppstein, Michael T Goodrich, and Jonathan Z Sun. Skip quadtrees: Dynamic data structures for multidimensional point sets. International Journal of Computational Geometry &Applications, 18(01n02):131-160, 2008. Google Scholar
  21. Sandy Irani, Moni Naor, and Ronitt Rubinfeld. On the time and space complexity of computation using write-once memory or is pen really much worse than pencil? Mathematical Systems Theory, 25(2):141-159, 1992. URL: http://dx.doi.org/10.1007/BF02835833.
  22. Alon Itai, Alan G Konheim, and Michael Rodeh. A sparse table implementation of priority queues. Springer, 1981. Google Scholar
  23. Tsvi Kopelowitz. On-line indexing for general alphabets via predecessor queries on subsets of an ordered list. In IEEE Symp. on Found. of Comp. Sci. (FOCS), pages 283-292, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.79.
  24. Tsvi Kopelowitz, Gregory Kucherov, Yakov Nekrich, and Tatiana A. Starikovskaya. Cross-document pattern matching. J. Discrete Algorithms, 24:40-47, 2014. Google Scholar
  25. P. Pavan, R. Bez, P. Olivo, and E. Zanoni. Flash memory cells - an overview. Proceedings of the IEEE, 85(8):1248-1271, 1997. URL: http://dx.doi.org/10.1109/5.622505.
  26. Dan E. Willard. Good worst-case algorithms for inserting and deleting records in dense sequential files. In Proc. International Conference on Management of Data (SIGMOD), pages 251-260, 1986. Google Scholar
  27. D.E. Willard. Maintaining dense sequential files in a dynamic environment (extended abstract). In Proc. 14th Annual Symposium on Theory of Computing (STOC), pages 114-121, 1982. Google Scholar
  28. H.-S.P. Wong, S. Raoux, SangBum Kim, Jiale Liang, John P. Reifenberg, B. Rajendran, Mehdi Asheghi, and Kenneth E. Goodson. Phase change memory. Proceedings of the IEEE, 98(12):2201-2227, 2010. URL: http://dx.doi.org/10.1109/JPROC.2010.2070050.
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