論文の概要: Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

• arxiv url: http://arxiv.org/abs/2604.16061v1
• Date: Fri, 17 Apr 2026 13:36:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-20 22:00:19.937547
• Title: Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
• Title（参考訳）: 二重拘束されたfair k-Center,k-Median,k-Meansに対する定数因子近似
• Authors: Nicole Funk, Annika Hennes, Johanna Hillebrand, Sarah Sturm,
• Abstract要約: 2つの異なるフェアネス条件の組み合わせによって制約される一般距離空間における離散kクラスタリング問題について検討する。 我々のアルゴリズムは、多種多様な中心選択を満たす解を2つの制約付き公正クラスタリングに変換する。 この結果は、マトロイドkクラスタリングやknapsack制約など、他の中心選択制約に一般化可能である。
• 参考スコア（独自算出の注目度）: 2.2400646874013037
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P,d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern and Zhang (2023) denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen (2020). For k-median and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints.
• Abstract（参考訳）: 一般計量空間における離散kクラスタリング問題を、人口統計学的フェアネスモデル内の2つの異なるフェアネス条件の組み合わせによって制約する。 P のすべての点が保護された属性と数 k を備える距離空間 (P,d) が与えられたとき、その目標は、P を指定された中心を持つ k 個のクラスタに分割することである。 1) グループフェアネス: 所望の属性比の下位値と上位値を指定することで、属性のバランスの取れた数を持つクラスタを目指す。 2) 多様な中心選択: クラスターは自然の代表者、すなわちその中心を持つ。 各属性から選択すべきセンター数を指定して、バランスのとれた代表者のセットを求める。 Dickerson, Esmaeili, Morgenstern and Zhang (2023) は、これらの2つの制約の組み合わせを2つの制約付き公正クラスタリングとして表している。 これらの問題に対して最もよく知られた近似因子に依存するアルゴリズムを提案する。 現在、これは群フェアネス制約に小さな加法的違反を伴う8-近似を意味する。 k中心の場合、この近似係数を小さい加法的違反で4に改善する。 この保証は、Jones, Nguyen and Nguyen (2020) によって与えられるDS-fair k-centerの現在最高のアルゴリズムにも依存する。 k-median および k-means に対して、最初の定数係数近似アルゴリズムを提案する。 我々のアルゴリズムは、多種多様な中心選択を満たす解を、LPベースのアプローチを用いて2つの制約付き公正クラスタリングに変換する。 さらに、この結果は、マトロイドkクラスタリングやknapsack制約など、他の中心選択制約に一般化可能である。

関連論文リスト

• A Computational Approach to Improving Fairness in K-means Clustering [8.001963712764569]
  一般的なK平均クラスタリングアルゴリズムは、さらなる分析や解釈の大きな弱点に悩まされる可能性がある。 この研究は、K平均クラスタリングの公平性を改善するために、2段階最適化の定式化を試みる。 ベンチマークデータセットの実験は、クラスタリングの品質に最小限の影響を伴って、フェアネスを大幅に改善したことを示している。
  論文  参考訳（メタデータ） (2025-05-29T01:48:12Z)
• Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
  一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。 そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
  論文  参考訳（メタデータ） (2024-10-16T18:00:19Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  ファジィK平均クラスタリングは教師なしデータ分析において重要な手法である。 本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィテクストK-Meansクラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-07T12:25:03Z)
• Fair Labeled Clustering [28.297893914525517]
  クラスタリングのダウンストリーム適用と,そのような設定に対してグループフェアネスをどのように確保するかを検討する。 このような問題に対するアルゴリズムを提供し、グループフェアクラスタリングにおけるNPハードのアルゴリズムとは対照的に、効率的な解が可能であることを示す。 また、距離空間における中心位置に関係なく、意思決定者が自由にクラスタにラベルを割り当てることができるような、モチベーションのよい代替設定についても検討する。
  論文  参考訳（メタデータ） (2022-05-28T07:07:12Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• Determinantal consensus clustering [77.34726150561087]
  本稿では,クラスタリングアルゴリズムのランダム再起動における決定点プロセス (DPP) の利用を提案する。 DPPは部分集合内の中心点の多様性を好んでいる。 DPPとは対照的に、この手法は多様性の確保と、すべてのデータフェースについて良好なカバレッジを得るために失敗することを示す。
  論文  参考訳（メタデータ） (2021-02-07T23:48:24Z)
• Ball k-means [53.89505717006118]
  Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。 高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
  論文  参考訳（メタデータ） (2020-05-02T10:39:26Z)

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

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