License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.73
URN: urn:nbn:de:0030-drops-100213
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10021/
Go to the corresponding LIPIcs Volume Portal

Fotakis, Dimitris ; Gourvès, Laurent ; Mathieu, Claire ; Srivastav, Abhinav

Covering Clients with Types and Budgets

pdf-format:
LIPIcs-ISAAC-2018-73.pdf (0.4 MB)

Abstract

In this paper, we consider a variant of the facility location problem. Imagine the scenario where facilities are categorized into multiple types such as schools, hospitals, post offices, etc. and the cost of connecting a client to a facility is realized by the distance between them. Each client has a total budget on the distance she/he is willing to travel. The goal is to open the minimum number of facilities such that the aggregate distance of each client to multiple types is within her/his budget. This problem closely resembles to the set cover and r-domination problems. Here, we study this problem in different settings. Specifically, we present some positive and negative results in the general setting, where no assumption is made on the distance values. Then we show that better results can be achieved when clients and facilities lie in a metric space.

BibTeX - Entry

@InProceedings{fotakis_et_al:LIPIcs:2018:10021,
  author =	{Dimitris Fotakis and Laurent Gourv{\`e}s and Claire Mathieu and Abhinav Srivastav},
  title =	{{Covering Clients with Types and Budgets}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{73:1--73:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10021},
  URN =		{urn:nbn:de:0030-drops-100213},
  doi =		{10.4230/LIPIcs.ISAAC.2018.73},
  annote =	{Keywords: Facility Location, Geometric Set Cover, Local Search}
}

Keywords: Facility Location, Geometric Set Cover, Local Search
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI