License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.33
URN: urn:nbn:de:0030-drops-78831
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7883/
Go to the corresponding LIPIcs Volume Portal


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

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

pdf-format:
LIPIcs-ESA-2017-33.pdf (0.6 MB)


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.

BibTeX - Entry

@InProceedings{devanny_et_al:LIPIcs:2017:7883,
  author =	{William E. Devanny and Jeremy T. Fineman and Michael T. Goodrich and Tsvi Kopelowitz},
  title =	{{The Online House Numbering Problem: Min-Max Online List Labeling}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7883},
  URN =		{urn:nbn:de:0030-drops-78831},
  doi =		{10.4230/LIPIcs.ESA.2017.33},
  annote =	{Keywords: house numbering, list labeling, file maintenance}
}

Keywords: house numbering, list labeling, file maintenance
Seminar: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 31.08.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI