論文の概要: A Sub-4 Approximation for Fair $k$-Means

• arxiv url: http://arxiv.org/abs/2609.07974v1
• Date: Mon, 07 Sep 2026 20:54:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.520355
• Title: A Sub-4 Approximation for Fair $k$-Means
• Title（参考訳）: A Sub-4 Approximation for Fair $k$-Means
• Abstract要約: ユークリッド空間における公平な$k$-meansクラスタリングについて検討し、各クラスタにおける保護群の割合は、指定された下限と上限内にある必要がある。 本稿では,線形プログラミング緩和と入力の幾何学変換を組み合わせた近似アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 18.61347737579578
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair $k$-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. We propose an approximation algorithm that combines a linear programming relaxation with geometric transformations of the input to construct candidate center sets. Given a $ρ$-approximate algorithm for weighted $k$-means and any $ε>0$, our algorithm returns a fractional solution whose cost is at most $1+(3-1/Γ)ρ+O(ε)$ times the optimal integral fair cost, where $Γ\approx6.357$ is an upper bound on the integrality gap of the standard Euclidean $k$-means LP. With a PTAS as the subroutine, the approximation ratio becomes $3.8427+O(ε)$, improving the previous factor of $5+O(ε)$ to below $4$. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the $k$-sparse Wasserstein barycenter problem.
• Abstract（参考訳）: クラスタリングの公正さは、機械学習アプリケーションにおける保護されたグループの公平な表現の必要性から、継続的な研究関心を惹きつけている。 ユークリッド空間における公平な$k$-meansクラスタリングについて検討し、各クラスタにおける保護群の割合は、指定された下限と上限内にある必要がある。 これらの制約は、クラスタセンターとポイント割り当ての両方を決定するのを難しくする。 本稿では,線形プログラミング緩和と入力の幾何学変換を組み合わせた近似アルゴリズムを提案する。 重み付き$k$-meansおよび任意の$ε>0$に対する$ρ$-approximateアルゴリズムが与えられた場合、我々のアルゴリズムは、最大コストが1+(3-1)ρ+O(ε)$の分数解を返す。 PTASをサブルーチンとし、近似比は3.8427+O(ε)$となり、以前の5+O(ε)$を4ドル以下に改善した。 この解はすべての公正性の制約を正確に満たし、公正性の有界加法的違反とコストの増大を伴わない積分代入に丸めることができる。 同じ近似保証は、$k$sparse Wasserstein バリセンタ問題にまで拡張される。

関連論文リスト

• Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering [7.186850020419764]
  ユークリッド空間を用いた公平な$k$-centerクラスタリングのための近似アルゴリズムを開発した。 本手法はクラスタリング精度の点で最先端の手法よりも優れている。
  論文  参考訳（メタデータ） (2026-09-06T04:49:44Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• On the Hardness of Approximation of the Fair k-Center Problem [6.430130814523796]
  公平な$k$-center問題の近似の難しさについて検討する。 A-time $3$-approximation is known for fair $k$-center in general metrics。
  論文  参考訳（メタデータ） (2026-02-18T18:33:27Z)
• 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)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• 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)
• Improved Approximation Algorithms for Individually Fair Clustering [9.914246432182873]
  16p +varepsilon,3)$-bicriteria approximation for the fair $k$-clustering with $ell_p$-norm cost。 我々のアプローチは、Kleindessnerらによって提案されたグループフェアネス要件により、個別に公平なクラスタリングからクラスタリングに還元されることを示唆している。
  論文  参考訳（メタデータ） (2021-06-26T15:22:52Z)

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

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