Mobile facility location: combinatorial filtering via weighted occupancy

Amitai Armon (), Iftah Gamzu () and Danny Segev ()
Additional contact information
Amitai Armon: Tel-Aviv University
Iftah Gamzu: Microsoft R&D Center
Danny Segev: University of Haifa

Journal of Combinatorial Optimization, 2014, vol. 28, issue 2, No 4, 358-375

Abstract: Abstract An instance of the mobile facility location problem consists of a complete directed graph $$G = (V, E)$$ , in which each arc $$(u, v) \in E$$ is associated with a numerical attribute $$\mathcal M (u,v)$$ , representing the cost of moving any object from $$u$$ to $$v$$ . An additional ingredient of the input is a collection of servers $$S = \{ s_1, \ldots , s_k \}$$ and a set of clients $$C = \{ c_1, \ldots , c_\ell \}$$ , which are located at nodes of the underlying graph. With this setting in mind, a movement scheme is a function $$\psi : S \rightarrow V$$ that relocates each server $$s_i$$ to a new position, $$\psi ( s_i )$$ . We refer to $$\mathcal M ( s_i, \psi ( s_i ) )$$ as the relocation cost of $$s_i$$ , and to $$\min _{i \in [k]} \mathcal M (c_j, \psi ( s_i ) )$$ , the cost of assigning client $$c_j$$ to the nearest final server location, as the service cost of $$c_j$$ . The objective is to compute a movement scheme that minimizes the sum of relocation and service costs. In this paper, we resolve an open question posed by Demaine et al. (SODA ’07) by characterizing the approximability of mobile facility location through LP-based methods. We also develop a more efficient algorithm, which is based on a combinatorial filtering approach. The latter technique is of independent interest, as it may be applicable in other settings as well. In this context, we introduce a weighted version of the occupancy problem, for which we establish interesting tail bounds, not before demonstrating that existing bounds cannot be extended.

Keywords: Approximation algorithms; Movement problems; Non-metric facility location; Filtering; Occupancy problem (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9558-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:28:y:2014:i:2:d:10.1007_s10878-012-9558-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9558-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().