2026-07-21T21:09:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7883 2024-03-06T10:41:19Z ddc:004 open_access

The Online House Numbering Problem: Min-Max Online List Labeling Devanny, William E. Fineman, Jeremy T. Goodrich, Michael T. Kopelowitz, Tsvi house numbering list labeling file maintenance 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik William E. Devanny and Jeremy T. Fineman and Michael T. Goodrich and Tsvi Kopelowitz 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.33 urn:nbn:de:0030-drops-78831 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.33 eng https://creativecommons.org/licenses/by/3.0/legalcode