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
TypeCommunication / Conférence
Conference title29th International Symposium on Algorithms and Computation (ISAAC 2018)
Conference cityJiaoxi, Yilan County
Book title29th International Symposium on Algorithms and Computation (ISAAC 2018)
Book authorHsu, Wen-Lian; Lee, Der-Tsai; Liao, Chung-Shou
MetadataShow full item record
School of Electrical and Computer Engineering, National Technical University of Athens [ICCS]
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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 / KeywordsFacility Location; Geometric Set Cover; Local Search
Showing items related by title and author.
Ballerie, Alice; Cavalin, Catherine; Lederlin, Mathieu; Nicolas, Amélie; Garlantézec, Ronan; Jouneau, Stéphane; Lecureur, Valérie; Cazalets, Claire; Belhomme, Nicolas; Paris, Christophe; Rosental, Paul-André; Jégo, Patrick; Lescoat, Alain (2020) Article accepté pour publication ou publié