論文の概要: On the Hardness of Approximation of the Fair k-Center Problem

• arxiv url: http://arxiv.org/abs/2602.16688v1
• Date: Wed, 18 Feb 2026 18:33:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-19 15:58:30.683463
• Title: On the Hardness of Approximation of the Fair k-Center Problem
• Title（参考訳）: フェアk-センター問題の近似の硬さについて
• Authors: Suhas Thejaswi,
• Abstract要約: 公平な$k$-center問題の近似の難しさについて検討する。 我々の結果は、2つの非連結群しか存在せず、各群から少なくとも1つの中心を選ばなければならない場合でも成り立つ。
• 参考スコア（独自算出の注目度）: 6.430130814523796
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we study the hardness of approximation of the fair $k$-center problem. Here the data points are partitioned into groups and the task is to choose a prescribed number of data points from each group, called centers, while minimizing the maximum distance from any point to its closest center. Although a polynomial-time $3$-approximation is known for this problem in general metrics, it has remained open whether this approximation guarantee is tight or could be further improved, especially since the unconstrained $k$-center problem admits a polynomial-time factor-$2$ approximation. We resolve this open question by proving that, for every $ε>0$, achieving a $(3-ε)$-approximation is NP-hard, assuming $\text{P} \neq \text{NP}$. Our inapproximability results hold even when only two disjoint groups are present and at least one center must be chosen from each group. Further, it extends to the canonical one-per-group setting with $k$-groups (for arbitrary $k$), where exactly one center must be selected from each group. Consequently, the factor-$3$ barrier for fair $k$-center in general metric spaces is inherent, and existing $3$-approximation algorithms are optimal up to lower-order terms even in these restricted regimes. This result stands in sharp contrast to the $k$-supplier formulation, where both the unconstrained and fair variants admit factor-$3$ approximation in polynomial time.
• Abstract（参考訳）: 本研究では,fair $k$-center問題の近似の難しさについて検討する。 ここでは、データポイントをグループに分割し、タスクは、任意のポイントから最も近いセンターまでの最大距離を最小化しながら、センターと呼ばれる各グループから所定の数のデータポイントを選択する。 多項式時間3ドル近似は一般のメトリクスではこの問題で知られているが、この近似保証が厳密であるか、さらに改善されるかは、特に制約のない$k$中心問題では多項式時間係数-$2$近似が認められているため、未解決のままである。 このオープンな問題は、すべての$ε>0$に対して、$(3-ε)$-近似を達成することは、$\text{P} \neq \text{NP}$を仮定してNPハードであることを証明することで解決する。 我々の非近似性の結果は、2つの非共役群しか存在せず、各群から少なくとも1つの中心を選ばなければならない場合でも成り立つ。 さらに、$k$-群(任意の$k$の場合)を持つ正準単位群設定にまで拡張され、各群から正確に1つの中心を選ばなければならない。 したがって、一般計量空間における$k$中心の係数$3$障壁は固有のものであり、既存の$3$近似アルゴリズムはこれらの制限された規則においても下位項まで最適である。 この結果は$k$-supplier の定式化とは対照的であり、制約のない変種と公正な変種の両方が多項式時間における係数-$3$近似を認めている。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
  複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。 我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。 PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
  論文  参考訳（メタデータ） (2024-11-02T02:50:12Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Diversity-aware clustering: Computational Complexity and Approximation Algorithms [18.009333081689498]
  本稿では,データポイントが複数の属性に関連付けられ,グループ間の交差が生じている,多様性を考慮したクラスタリング問題について検討する。 クラスタリングソリューションは、各グループから選択されたクラスタセンターの数が、各グループの下位および上位境界閾値で定義された範囲内にあることを保証する必要がある。 1+ frac2e + epsilon approx 1.736$+frac8e + epsilon approx 3.943$, and $5$ for diversity-aware $k$-median, diversity-aware $。
  論文  参考訳（メタデータ） (2024-01-10T19:01:05Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。 当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。