• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
LIPIcs-ISAAC-2018-73.pdf (444.7Kb)
Type
Communication / Conférence
Date
2018
Conference title
29th International Symposium on Algorithms and Computation (ISAAC 2018)
Conference date
2018-12
Conference city
Jiaoxi, Yilan County
Conference country
"Taiwan
Book title
29th International Symposium on Algorithms and Computation (ISAAC 2018)
Book author
Hsu, Wen-Lian; Lee, Der-Tsai; Liao, Chung-Shou
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Published in
Wadern
ISBN
978-3-95977-094-1
Pages
73:1-73:12
Publication identifier
10.4230/LIPIcs.ISAAC.2018.73
Metadata
Show full item record
Author(s)
Fotakis, Dimitris
School 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 Search

Related items

Showing items related by title and author.

  • Thumbnail
    Conference Program Design with Single-Peaked and Single-Crossing Preferences 
    Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2016) Communication / Conférence
  • Thumbnail
    On the Distortion of Single Winner Elections with Aligned Candidates 
    Fotakis, Dimitris; Gourvès, Laurent (2022) Article accepté pour publication ou publié
  • Thumbnail
    Object Allocation and Positive Graph Externalities 
    Fotakis, Dimitris; Gourvès, Laurent; Kasouridis, Stelios; Pagourtzis, Aris (2020) Communication / Conférence
  • Thumbnail
    Selfish Transportation Games 
    Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2017) Communication / Conférence
  • Thumbnail
    Approximating the optimal sequence of acquisitions and sales with a capped budget 
    Gourvès, Laurent (2015) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo