Document Open Access Logo

Generalized Center Problems with Outliers

Authors Deeparnab Chakrabarty, Maryam Negahbani

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.30.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Deeparnab Chakrabarty
  • Department of Computer Science, Dartmouth College, 9 Maynard St, Hanover, NH, USA , https://web.cs.dartmouth.edu/people/deeparnab-chakrabarty
Maryam Negahbani
  • Department of Computer Science, Dartmouth College, 9 Maynard St, Hanover, NH, USA

Cite As Get BibTex

Deeparnab Chakrabarty and Maryam Negahbani. Generalized Center Problems with Outliers. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.30

Abstract

We study the F-center problem with outliers: given a metric space (X,d), a general down-closed family F of subsets of X, and a parameter m, we need to locate a subset S in F of centers such that the maximum distance among the closest m points in X to S is minimized.
Our main result is a dichotomy theorem. Colloquially, we prove that there is an efficient 3-approximation for the F-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over F subject to a partition constraint. One concrete upshot of our result is a polynomial time 3-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • Approximation Algorithms
  • Clustering
  • k-Center Problem

Metrics

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

Related Versions

References

  1. Gagan Aggarwal, Rina Panigrahy, Tomás Feder, Dilys Thomas, Krishnaram Kenthapadi, Samir Khuller, and An Zhu. Achieving Anonymity via Clustering. ACM Trans. Algorithms, 6(3):49:1-49:19, 2010. URL: http://dx.doi.org/10.1145/1798596.1798602.
  2. Hyung-Chan An, Mohit Singh, and Ola Svensson. LP-based algorithms for capacitated facility location. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS '14, pages 256-265, Washington, DC, USA, 2014. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2014.35.
  3. André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, and Guido Schäfer. Budgeted Matching and Budgeted Matroid Intersection via the Gasoline Puzzle. Mathematical Programming, 128(1):355-372, 2011. URL: http://dx.doi.org/10.1007/s10107-009-0307-4.
  4. Paolo M. Camerini, Giulia Galbiati, and Francesco Maffioli. Random Pseudo-Polynomial Algorithms for Exact Matroid Problems. J. Algorithms, 13(2):258-273, 1992. URL: http://dx.doi.org/10.1016/0196-6774(92)90018-8.
  5. Robert D. Carr, Lisa K. Fleischer, Vitus J. Leung, and Cynthia A. Phillips. Strengthening Integrality Gaps for Capacitated Network Design and Covering Problems. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00, pages 106-115, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=338219.338241.
  6. Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The Non-Uniform k-Center Problem. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 67:1-67:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.67.
  7. Deeparnab Chakrabarty, Ravishankar Krishnaswamy, and Amit Kumar. The Heterogeneous Capacitated k-Center Problem. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 123-135, 2017. URL: http://dx.doi.org/10.1007/978-3-319-59250-3_11.
  8. Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for Facility Location Problems with Outliers. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '01, pages 642-651, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics. Google Scholar
  9. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1080-1097, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.82.
  10. Danny Z. Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and Knapsack Center Problems. In Integer Programming and Combinatorial Optimization (IPCO), pages 110-122, 2013. Google Scholar
  11. Teofilo F. Gonzalez. Clustering to Minimize the Maximum Intercluster Distance. Theoretical Computer Science, 38:293-306, 1985. URL: http://dx.doi.org/10.1016/0304-3975(85)90224-5.
  12. Fabrizio Grandoni, R. Ravi, Mohit Singh, and Rico Zenklusen. New Approaches to Multi-Objective Optimization. Math. Program., 146(1-2):525-554, 2014. URL: http://dx.doi.org/10.1007/s10107-013-0703-7.
  13. Seifollah L. Hakimi. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph. Ops Res.INFORMS, 12:450-459, 1964. URL: http://dx.doi.org/10.1287/opre.12.3.450.
  14. Seifollah L. Hakimi. Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems. Ops Res.INFORMS, 13:462-475, 1965. URL: http://dx.doi.org/10.1287/opre.13.3.462.
  15. David G. Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. A Lottery Model for Center-Type Problems with Outliers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, pages 10:1-10:19, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.10.
  16. Dorit S. Hochbaum and David B. Shmoys. A Best Possible Heuristic for the k-Center Problem. Math. Oper. Res., 10(2):180-184, 1985. URL: http://dx.doi.org/10.1287/moor.10.2.180.
  17. Dorit S. Hochbaum and David B. Shmoys. A Unified Approach to Approximation Algorithms for Bottleneck Problems. J. ACM, 33(3):533-550, 1986. URL: http://dx.doi.org/10.1145/5925.5933.
  18. Wen-Lian Hsu and George L. Nemhauser. Easy and Hard Bottleneck Location Problems. Discrete Applied Mathematics, 1(3):209-215, 1979. URL: http://dx.doi.org/10.1016/0166-218X(79)90044-1.
  19. Shi Li. On Uniform Capacitated k-median Beyond the Natural LP Relaxation. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, pages 696-707, Philadelphia, PA, USA, 2015. Society for Industrial and Applied Mathematics. Google Scholar
  20. Shi Li. Approximating Capacitated k-median with (1 + ε)k Open Facilities. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 786-796, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2884435.2884491.
  21. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is As Easy As Matrix Inversion. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 345-354, New York, NY, USA, 1987. ACM. URL: http://dx.doi.org/10.1145/28395.383347.
  22. Christos H. Papadimitriou and Mihalis Yannakakis. The Complexity of Restricted Spanning Tree Problems. J. ACM, 29(2):285-309, 1982. URL: http://dx.doi.org/10.1145/322307.322309.
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 About DROPS Imprint Privacy Contact