Document Open Access Logo

Resolving Conflicts for Lower-Bounded Clustering

Author Katrin Casel

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.23.pdf
  • Filesize: 459 kB
  • 14 pages

Document Identifiers

Author Details

Katrin Casel
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany, Universität Trier, Fachbereich IV - Informatikwissenschaften, Germany

Cite As Get BibTex

Katrin Casel. Resolving Conflicts for Lower-Bounded Clustering. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.23

Abstract

This paper considers the effect of non-metric distances for lower-bounded clustering, i.e., the problem of computing a partition for a given set of objects with pairwise distance, such that each set has a certain minimum cardinality (as required for anonymisation or balanced facility location problems). We discuss lower-bounded clustering with the objective to minimise the maximum radius or diameter of the clusters. For these problems there exists a 2-approximation but only if the pairwise distance on the objects satisfies the triangle inequality, without this property no polynomial-time constant factor approximation is possible, unless P=NP. We try to resolve or at least soften this effect of non-metric distances by devising particular strategies to deal with violations of the triangle inequality (conflicts). With parameterised algorithmics, we find that if the number of such conflicts is not too large, constant factor approximations can still be computed efficiently.
In particular, we introduce parameterised approximations with respect to not just the number of conflicts but also for the vertex cover number of the conflict graph (graph induced by conflicts). Interestingly, we salvage the approximation ratio of 2 for diameter while for radius it is only possible to show a ratio of 3. For the parameter vertex cover number of the conflict graph this worsening in ratio is shown to be unavoidable, unless FPT=W[2]. We further discuss improvements for diameter by choosing the (induced) P_3-cover number of the conflict graph as parameter and complement these by showing that, unless FPT=W[1], there exists no constant factor parameterised approximation with respect to the parameter split vertex deletion set.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Facility location and clustering
Keywords
  • clustering
  • triangle inequality
  • parameterised approximation

Metrics

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

References

  1. F. N. Abu-Khzam, C. Bazgan, K. Casel, and H. Fernau. Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework. Algorithmica, 80(9):2517-2550, 2018. Google Scholar
  2. N. Alon, R. Yuster, and U. Zwick. Color Coding. In M.-Y. Kao, editor, Encyclopedia of Algorithms. Springer, 2008. Google Scholar
  3. G. Ausiello. Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer, 1999. Google Scholar
  4. C. Bazgan, M. Chopin, A. Nichterlein, and F. Sikora. Parameterized Inapproximability of Target Set Selection and Generalizations. Computability, 3(2):135-145, 2014. Google Scholar
  5. D. Berend and T. Tassa. Improved bounds on Bell numbers and on moments of sums of random variables. Probability and Mathematical Statistics, 30(2):185-205, 2010. Google Scholar
  6. B. Bollobás. Modern Graph Theory, volume 184 of Graduate texts in mathematics. Springer, 1998. Google Scholar
  7. A. Boral, M. Cygan, T. Kociumaka, and M. Pilipczuk. A Fast Branching Algorithm for Cluster Vertex Deletion. Theory Comput. Syst., 58(2):357-376, 2016. Google Scholar
  8. J. Chen, X. Huang, I. A. Kanj, and G. Xia. Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci., 72(8):1346-1367, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2006.04.007.
  9. J. Chen, I. A. Kanj, and G. Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. URL: http://dx.doi.org/10.1016/j.tcs.2010.06.026.
  10. I. Dinur and D. Steurer. Analytical approach to parallel repetition. In D. B. Shmoys, editor, Symposium on Theory of Computing, STOC, pages 624-633. ACM, 2014. Google Scholar
  11. R. G. Downey and M. Fellows. Fixed parameter tractability and completeness. Congressus Numerantium, 87:161-187, 1992. Google Scholar
  12. R. G. Downey and M. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  13. C. Elkan. Using the Triangle Inequality to Accelerate k-Means. In T. Fawcett and N. Mishra, editors, Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pages 147-153. AAAI Press, 2003. Google Scholar
  14. M. Fellows, F. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider, and C. Thomassen. On the complexity of some colorful problems parameterized by treewidth. Information and Computation, 209(2):143-153, 2011. Google Scholar
  15. M. Fellows, D. Hermelin, F. A. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53-61, 2009. Google Scholar
  16. J. Fiala, P. Golovach, and J. Kratochvíl. Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theor. Comput. Sci., 412(23):2513-2523, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.10.043.
  17. J. Guo, F. Hüffner, and R. Niedermeier. A Structural View on Parameterizing Problems: Distance from Triviality. In R. G. Downey, M. Fellows, and F. K. H. A. Dehne, editors, Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings, volume 3162 of LNCS. Springer, 2004. Google Scholar
  18. D. S. Hochbaum. Heuristics for the fixed cost median problem. Mathematical Programming, 22(1):148-162, 1982. Google Scholar
  19. R. Impagliazzo and R. Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  20. S. Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45-58, 2013. Google Scholar
  21. D. Lokshtanov, D. Marx, and S. Saurabh. Slightly Superexponential Parameterized Problems. SIAM J. Comput., 47(3):675-702, 2018. Google Scholar
  22. D. Marx. Parameterized complexity and approximation algorithms. The Computer Journal, 51(1):60-78, 2008. Google Scholar
  23. J. B. Schafer, D Frankowski, J. L. Herlocker, and S. Sen. Collaborative Filtering Recommender Systems. In P. Brusilovsky, A. Kobsa, and W. Nejdl, editors, The Adaptive Web, Methods and Strategies of Web Personalization, volume 4321 of LNCS, pages 291-324. Springer, 2007. Google Scholar
  24. M. Xiao and S. Kou. Kernelization and Parameterized Algorithms for 3-Path Vertex Cover. In Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, pages 654-668, 2017. 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 About DROPS Imprint Privacy Contact