Scholarlink

The Knapsack Median problem was known to be W[2]-hard if parameterized by the maximal number of opened facilities in feasible solutions (denoted by k), implying that exactly solving this problem in FPT(k) time is unlikely. We focus on parameterized approximation algorithms for the Knapsack Median problem. We give a sampling-based approach for reducing the solution search space, which yields a \((3+\varepsilon )\) -approximation algorithm that runs in \((k\varepsilon ^{-1})^{O(k)}n^{O(1)}\) time in general metric spaces and a \((1+\varepsilon )\) -approximation algorithm with similar running time in d-dimensional Euclidean space.

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

Clustering with a Knapsack Constraint: Parameterized Approximation Algorithms for the Knapsack Median Problem

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Zhen Zhang,
  • Limei Liu,
  • Yao Liu,
  • Jie Chen,
  • Qilong Feng

摘要

The Knapsack Median problem was known to be W[2]-hard if parameterized by the maximal number of opened facilities in feasible solutions (denoted by k), implying that exactly solving this problem in FPT(k) time is unlikely. We focus on parameterized approximation algorithms for the Knapsack Median problem. We give a sampling-based approach for reducing the solution search space, which yields a \((3+\varepsilon )\) -approximation algorithm that runs in \((k\varepsilon ^{-1})^{O(k)}n^{O(1)}\) time in general metric spaces and a \((1+\varepsilon )\) -approximation algorithm with similar running time in d-dimensional Euclidean space.