Show simple item record

dc.contributor.authorFotakis, Dimitris
dc.contributor.authorGourvès, Laurent
dc.contributor.authorMathieu, Claire
dc.contributor.authorSrivastav, Abhinav
dc.date.accessioned2019-04-30T11:04:26Z
dc.date.available2019-04-30T11:04:26Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18870
dc.language.isoenen
dc.subjectFacility Locationen
dc.subjectGeometric Set Coveren
dc.subjectLocal Searchen
dc.subject.ddc004en
dc.titleCovering Clients with Types and Budgetsen
dc.typeCommunication / Conférence
dc.description.abstractenIn 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.en
dc.identifier.citationpages73:1-73:12en
dc.relation.ispartoftitle29th International Symposium on Algorithms and Computation (ISAAC 2018)en
dc.relation.ispartofeditorHsu, Wen-Lian
dc.relation.ispartofeditorLee, Der-Tsai
dc.relation.ispartofeditorLiao, Chung-Shou
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.relation.ispartofpublcityWadernen
dc.relation.ispartofdate2018
dc.subject.ddclabelInformatique généraleen
dc.relation.ispartofisbn978-3-95977-094-1en
dc.relation.conftitle29th International Symposium on Algorithms and Computation (ISAAC 2018)en
dc.relation.confdate2018-12
dc.relation.confcityJiaoxi, Yilan Countyen
dc.relation.confcountry"Taiwanen
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.ISAAC.2018.73en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-28T10:57:23Z
hal.person.labIds245158
hal.person.labIds989
hal.person.labIds4348
hal.person.labIds91477
hal.faultCodeThe supplied XML description does not validate the AOfr schema


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record