کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436092 | 689970 | 2014 | 12 صفحه PDF | دانلود رایگان |
We consider the following online allocation problem: Given a unit square S , and a sequence of numbers ni∈[0,1]ni∈[0,1] with ∑j=0inj⩽1; at each step i , select a region CiCi of previously unassigned area nini 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 CiCi. 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 nini 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.
Journal: Theoretical Computer Science - Volume 555, 23 October 2014, Pages 43–54