Document Open Access Logo

Covering Clients with Types and Budgets

Authors Dimitris Fotakis, Laurent Gourvès, Claire Mathieu, Abhinav Srivastav

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.73.pdf
  • Filesize: 444 kB
  • 12 pages

Document Identifiers

Author Details

Dimitris Fotakis
  • Yahoo Research-New York, USA & National Technical University of Athens, Greece
Laurent Gourvès
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016 Paris, France
Claire Mathieu
  • CNRS, France
Abhinav Srivastav
  • ENS Paris & Université Paris-Dauphine, France

Funding

PSL Project MULTIFAC

Cite AsGet BibTex

Dimitris Fotakis, Laurent Gourvès, Claire Mathieu, and Abhinav Srivastav. Covering Clients with Types and Budgets. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 73:1-73:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.73

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Facility location and clustering
Keywords
  • Facility Location
  • Geometric Set Cover
  • Local Search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Ageev, Y. Ye, and J. Zhang. Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem. SIAM J. Discrete Math., 18(1):207-2017, 2004. Google Scholar
  2. N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor. The Online Set Cover Problem. SIAM J. Computing, 39(2):361-370, 2009. Google Scholar
  3. S. Arora, N. Gupta, S. Khuller, Y. Sabharwal, and S. Singhal. Facility Location with Red-blue Demands. Operation Research Letter, 42(6):462-465, September 2014. Google Scholar
  4. N. Bansal and K. Pruhs. Weighted geometric set multi-cover via quasi-uniform sampling. J. Comp. Geometry, 7(1):221-236, 2016. Google Scholar
  5. R. Bar-Yehuda, G. Flysher, J. Mestre, and D. Rawitz. Approximation of Partial Capacitated Vertex Cover. SIAM J. Discrete Math., 24(4):1441-1469, 2010. Google Scholar
  6. J. Byrka, S. Li, and B. Rybicki. Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties). Theory of Computing Systems, 58(1):19-44, 2016. Google Scholar
  7. A. Caprara, G. F. Italiano, G. Mohan, A. Panconesi, and A. Srinivasan. Wavelength rerouting in optical networks, or the Venetian Routing problem. J. Algorithms, 45(2):93-125, 2002. Google Scholar
  8. R.D. Carr, S. Doddi, G. Konjevod, and M.V. Marathe. On the red-blue set cover problem. In Proc. of SODA, pages 345-353, 2000. Google Scholar
  9. I. Dinur and D. Steurer. Analytical approach to parallel repetition. In Proc. of STOC, pages 624-633, 2014. Google Scholar
  10. Y. Dodis and S. Khanna. Designing Networks with Bounded Pairwise Distance. In Proc. of STOC, pages 750-759, 1999. Google Scholar
  11. A. Efrat, F. Hoffmann, C. Knauer, K. Kriegel, G. Rote, and C. Wenk. Covering Shapes by Ellipses. In Proc. of SODA, pages 453-454, 2002. Google Scholar
  12. M. Elkin and D. Peleg. The Hardness of Approximating Spanner Problems. Theory Comp. Systems, 41(4):691-729, 2007. Google Scholar
  13. D. Fotakis. Online and Incremental Algorithms for Facility Location. SIGACT News, 42(1):97-131, 2011. Google Scholar
  14. M.R. Garey and D.S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., 1990. Google Scholar
  15. M. Hajiaghayi, R. Khandekar, and G. Kortsarz. Budgeted Red-blue Median and Its Generalizations. In Proc. of ESA, pages 314-325, 2010. Google Scholar
  16. D.S. Hochbaum and W. Maass. Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. J. ACM, 32(1):130-136, 1985. Google Scholar
  17. D.S. Hochbaum and W. Maass. Fast approximation algorithms for a nonconvex covering problem. J. Algorithms, 8(3):305-323, 1987. Google Scholar
  18. K. Jain and V.V. Vazirani. An approximation algorithm for the fault tolerant metric facility location problem. In Proc. of APPROX, pages 177-183, 2000. Google Scholar
  19. J. Könemann, O. Parekh, and D. Segev. A Unified Approach to Approximating Partial Covering Problems. Algorithmica, 59(4):489-509, 2011. Google Scholar
  20. N.H. Mustafa and S. Ray. Improved Results on Geometric Hitting Set Problems. Discrete & Computational Geometry, 44(4):883-895, 2010. Google Scholar
  21. C. Swamy and D.B. Shmoys. Fault-tolerant facility location. ACM Trans. Algorithms, 4(4):51:1-51:27, 2008. Google Scholar
  22. R.R. Yager. On ordered weighted averaging aggregation operators in multicriteria decision making. IEEE Trans. on Systems, Man, and Cybernetics, 18(1):183-190, 1988. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact