APPROXIMATION ALGORITHMS FOR K-MEDIAN PROBLEMS ON COMPLEX NETWORKS: THEORY AND PRACTICE

Published

February 21, 2024

Author(s)

Roldan Pozo

Abstract

Finding the k-median in a network involves identifying a subset of k vertices that minimize the total distance to all other vertices in a graph. This problem has been extensively studied in computer science, graph theory, operations research, and numerous areas due to its significance in a wide range of applications. While known to be computationally challenging (NP-hard) several approximation algorithms have been proposed, most with high-order polynomial-time complexity. However, the graph topology of complex networks with heavy- tailed degree distributions present characteristics that can be exploited to yield custom-tailored algorithms. We compare eight algorithms specifically designed for complex networks and evaluate their performance based on accuracy and efficiency for problems of varying sizes and application areas. Rather than relying on a small number of problems, we conduct over 25,000 experiments covering a wide range of network sizes and k-median values. While individual results vary, a few methods provide consistently good results. We draw general conclusions about how algorithms perform in practice and provide general guidelines for solutions.

Citation

Complex Networks & Their Applications XII Proceedings of The Twelfth International Conference on Complex Networks and their Applications: COMPLEX NETWORKS 2023 Volume 3

Publisher Info

Springer Nature Switzerland AG, Cham,

Pub Type

Books

Download Paper

https://doi.org/10.1007/978-3-031-53472-0_8

Local Download

Keywords

graph theory, heuristics, approximation algorithms

Citation

Pozo, R. (2024), APPROXIMATION ALGORITHMS FOR K-MEDIAN PROBLEMS ON COMPLEX NETWORKS: THEORY AND PRACTICE, Springer Nature Switzerland AG, Cham, , [online], https://doi.org/10.1007/978-3-031-53472-0_8, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=936883 (Accessed April 27, 2024)