論文の概要: Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity
- arxiv url: http://arxiv.org/abs/2512.03718v1
- Date: Wed, 03 Dec 2025 12:07:24 GMT
- ステータス: 情報取得中
- システム内更新日: 2025-12-04 12:03:36.723022
- Title: Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity
- Title（参考訳）: パラメータ化アルゴリズムと複雑度
- Authors: Robert Ganian, Hung P. Hoang, Simon Wietheger,
- Abstract要約: 離散ベクトルのクラスタリングをフェア平均で計算する際の計算問題について検討する。
高度に制限されたフェア平均クラスタリングインスタンスに対しても、類似アルゴリズムを除外する。
- 参考スコア（独自算出の注目度）: 16.72973567404685
- License:
- Abstract: We study the computational problem of computing a fair means clustering of discrete vectors, which admits an equivalent formulation as editing a colored matrix into one with few distinct color-balanced rows by changing at most $k$ values. While NP-hard in both the fairness-oblivious and the fair settings, the problem is well-known to admit a fixed-parameter algorithm in the former ``vanilla'' setting. As our first contribution, we exclude an analogous algorithm even for highly restricted fair means clustering instances. We then proceed to obtain a full complexity landscape of the problem, and establish tractability results which capture three means of circumventing our obtained lower bound: placing additional constraints on the problem instances, fixed-parameter approximation, or using an alternative parameterization targeting tree-like matrices.
- Abstract（参考訳）: 離散ベクトルのクラスタリングは,最大$k$の値で変化させることで,有色行列を色バランスの少ない行に編集するのと同等の定式化を許容する。
NPはフェアネスとフェアセッティングの両方においてハードであるが、問題は以前の「バニラ」セッティングに固定パラメータアルゴリズムを認めることで知られている。
最初のコントリビューションとして、高度に制限されたフェア平均クラスタリングインスタンスであっても、類似アルゴリズムを除外する。
そこで我々は,問題領域の全体像を把握し,得られた下界を回避する3つの手段,すなわち問題事例にさらなる制約を課す,固定パラメータ近似を行う,あるいは木のような行列を対象とする代替パラメータ化を利用する,というトラクタビリティー結果を確立する。
関連論文リスト
- Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。
既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。
これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-21T17:15:48Z) - A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering [0.0]
本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。
提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
論文 参考訳（メタデータ） (2024-03-17T21:43:19Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - Solution Path Algorithm for Twin Multi-class Support Vector Machine [6.97711662470035]
本論文は, ツインマルチクラスサポートベクトルマシンの高速正規化パラメータチューニングアルゴリズムについて述べる。
新たなサンプルデータセット分割法を採用し,ラグランジアン乗算器は分数線形であることが証明された。
提案手法は,グリッド探索手法の計算コストを指数レベルから定数レベルに削減し,優れた分類性能を実現する。
論文 参考訳（メタデータ） (2020-05-30T14:05:46Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。