Scholarlink

<p>We consider generalizations of the <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(k\)</EquationSource> </InlineEquation><span>-Center</span> problem in graphs of low doubling and highway dimension. For the <span>Capacitated </span><InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(k\)</EquationSource> </InlineEquation><span>-Supplier with Outliers (CkSwO)</span> problem, we show an efficient parameterized approximation scheme (EPAS) when the parameters are&#xa0;<InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(k\)</EquationSource> </InlineEquation>, the number of outliers and the doubling dimension of the graph induced by the supplier set. On the other hand, we show that for the <span>Capacitated </span><InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(k\)</EquationSource> </InlineEquation><span>-Center</span> problem, which is a special case of <span>CkSwO</span>, obtaining a parameterized approximation scheme (PAS) is&#xa0;<InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\mathsf {W[1]}\)</EquationSource> </InlineEquation>-hard when the parameters are&#xa0;<InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(k\)</EquationSource> </InlineEquation>, and the highway dimension. This is the first known example of a problem for which it is hard to obtain a PAS for highway dimension, while simultaneously admitting an EPAS for doubling dimension.</p>

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

Generalized \(k\)-Center: Distinguishing Doubling and Highway Dimension

  • 期刊论文

  • 发表日期：

    2025年12月8日

查看全文
  • Andreas Emil Feldmann,
  • Tung Anh Vu

摘要

We consider generalizations of the \(k\) -Center problem in graphs of low doubling and highway dimension. For the Capacitated \(k\) -Supplier with Outliers (CkSwO) problem, we show an efficient parameterized approximation scheme (EPAS) when the parameters are  \(k\) , the number of outliers and the doubling dimension of the graph induced by the supplier set. On the other hand, we show that for the Capacitated \(k\) -Center problem, which is a special case of CkSwO, obtaining a parameterized approximation scheme (PAS) is  \(\mathsf {W[1]}\) -hard when the parameters are  \(k\) , and the highway dimension. This is the first known example of a problem for which it is hard to obtain a PAS for highway dimension, while simultaneously admitting an EPAS for doubling dimension.