• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Covering Clients with Types and Budgets

Thumbnail
View/Open
LIPIcs-ISAAC-2018-73.pdf (444.7Kb)
Date
2018
Dewey
Informatique générale
Sujet
Facility Location; Geometric Set Cover; Local Search
DOI
http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.73
Conference name
29th International Symposium on Algorithms and Computation (ISAAC 2018)
Conference date
12-2018
Conference city
Jiaoxi, Yilan County
Conference country
"Taiwan
Book title
29th International Symposium on Algorithms and Computation (ISAAC 2018)
Author
Hsu, Wen-Lian; Lee, Der-Tsai; Liao, Chung-Shou
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Publisher city
Wadern
Year
2018
ISBN
978-3-95977-094-1
URI
https://basepub.dauphine.fr/handle/123456789/18870
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Fotakis, Dimitris
245158 School of Electrical and Computer Engineering, National Technical University of Athens [ICCS]
Gourvès, Laurent
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mathieu, Claire
status unknown
Srivastav, Abhinav
91477 Ecole Normale Supérieure
Type
Communication / Conférence
Item number of pages
73:1-73:12
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.