文章基本信息

标题：The Online House Numbering Problem: Min-Max Online List Labeling
本地全文：下载
作者：William E. Devanny ; Jeremy T. Fineman ; Michael T. Goodrich 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：33:1-33:15
DOI：10.4230/LIPIcs.ESA.2017.33
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：house numbering; list labeling; file maintenance