Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

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,

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 15, 2024)
Created February 21, 2024, Updated February 28, 2024