A Competitive Strategy for Distance-Aware Online Shape Allocation
| Autor: | Fekete, Sándor P., Schweer, Nils, Reinhardt, Jan-Marc |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We consider the following online allocation problem: Given a unit square S, and a sequence of numbers n_i between 0 and 1, with partial sum bounded by 1; at each step i, select a region C_i of previously unassigned area n_i in S. The objective is to make these regions compact in a distance-aware sense: minimize the maximum (normalized) average Manhattan distance between points from the same set C_i. Related location problems have received a considerable amount of attention; in particular, the problem of determining the "optimal shape of a city", i.e., allocating a single n_i has been studied. We present an online strategy, based on an analysis of space-filling curves; for continuous shapes, we prove a factor of 1.8092, and 1.7848 for discrete point sets. Comment: 15 pages, 9 figures, 3 tables; extended abstract version appears in WALCOM 2013, LNCS 7748, pp. 41-52 |
| Databáze: | arXiv |
| Externí odkaz: |
|