Scholarlink

<p>Finding the <i>k</i>-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 20,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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An extended analysis of approximation algorithms for k-median problems on complex networks

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年3月3日

查看全文
  • Roldan Pozo

摘要

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 20,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.