
Covering Clients with Types and Budgets
Fotakis, Dimitris; Gourvès, Laurent; Mathieu, Claire; Srivastav, Abhinav (2018), Covering Clients with Types and Budgets, in Hsu, Wen-Lian; Lee, Der-Tsai; Liao, Chung-Shou, 29th International Symposium on Algorithms and Computation (ISAAC 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik : Wadern, p. 73:1-73:12. 10.4230/LIPIcs.ISAAC.2018.73
View/ Open
Type
Communication / ConférenceDate
2018Conference title
29th International Symposium on Algorithms and Computation (ISAAC 2018)Conference date
2018-12Conference city
Jiaoxi, Yilan CountyConference country
"TaiwanBook title
29th International Symposium on Algorithms and Computation (ISAAC 2018)Book author
Hsu, Wen-Lian; Lee, Der-Tsai; Liao, Chung-ShouPublisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Published in
Wadern
ISBN
978-3-95977-094-1
Pages
73:1-73:12
Publication identifier
Metadata
Show full item recordAuthor(s)
Fotakis, DimitrisSchool of Electrical and Computer Engineering, National Technical University of Athens [ICCS]
Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mathieu, Claire
Srivastav, Abhinav
Ecole Normale Supérieure
Abstract (EN)
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.Subjects / Keywords
Facility Location; Geometric Set Cover; Local SearchRelated items
Showing items related by title and author.
-
Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2016) Communication / Conférence
-
Fotakis, Dimitris; Gourvès, Laurent (2022) Article accepté pour publication ou publié
-
Fotakis, Dimitris; Gourvès, Laurent; Kasouridis, Stelios; Pagourtzis, Aris (2020) Communication / Conférence
-
Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2017) Communication / Conférence
-
Gourvès, Laurent (2015) Article accepté pour publication ou publié