論文の概要: A Broader View on Clustering under Cluster-Aware Norm Objectives
- arxiv url: http://arxiv.org/abs/2512.06211v2
- Date: Tue, 09 Dec 2025 10:18:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-10 14:12:22.930581
- Title: A Broader View on Clustering under Cluster-Aware Norm Objectives
- Title（参考訳）: クラスタ対応ノルムオブジェクトにおけるクラスタリングに関するより広い視点
- Authors: Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase,
- Abstract要約: 最近の研究で紹介した$(f,g)$-clusteringの問題を再考する。
この問題は、各$k$クラスタに、クラスタ内のベクトル距離に適用される単調な対称ノルム$f$で決定されるコストを割り当てる。
一般的な$(f,g)$-clustering問題に対して$O(k)$-approximationを提供する。
- 参考スコア（独自算出の注目度）: 0.8016305126057338
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the $(f,g)$-clustering problem that we introduced in a recent work [SODA'25], and which subsumes fundamental clustering problems such as $k$-Center, $k$-Median, Min-Sum of Radii, and Min-Load $k$-Clustering. This problem assigns each of the $k$ clusters a cost determined by the monotone, symmetric norm $f$ applied to the vector distances in the cluster, and aims at minimizing the norm $g$ applied to the vector of cluster costs. Previously, we focused on certain special cases for which we designed constant-factor approximation algorithms. Our bounds for more general settings left, however, large gaps to the known bounds for the basic problems they capture. In this work, we provide a clearer picture of the approximability of these more general settings. First, we design an $O(\log^2 n)$-approximation algorithm for $(f, L_{1})$-clustering for any $f$. This improves upon our previous $\widetilde{O}(\sqrt{n})$-approximation. Second, we provide an $O(k)$-approximation for the general $(f,g)$-clustering problem, which improves upon our previous $\widetilde{O}(\sqrt{kn})$-approximation algorithm and matches the best-known upper bound for Min-Load $k$-Clustering. We then design an approximation algorithm for $(f,g)$-clustering that interpolates, up to polylog factors, between the best known bounds for $k$-Center, $k$-Median, Min-Sum of Radii, Min-Load $k$-Clustering, (Top, $L_{1}$)-clustering, and $(L_{\infty},g)$-clustering based on a newly defined parameter of $f$ and $g$.
- Abstract（参考訳）: これは$k$-Center, $k$-Median, Min-Sum of Radii, Min-Load $k$-Clusteringといった基本的なクラスタリング問題を仮定するものです。
この問題は、各$k$クラスタにモノトーン、対称ノルム$f$をクラスタ内のベクトル距離に適用するコストを割り当て、クラスタコストのベクトルに適用するノルム$g$を最小化することを目的としている。
これまで,定数近似アルゴリズムを設計した特殊なケースに焦点をあてた。
しかし、より一般的な設定に対する我々の限界は、彼らが捉えた基本的な問題に対する既知の境界に対する大きなギャップである。
本研究では、これらのより一般的な設定の近似性について、より明確な画像を提供する。
まず、$(f, L_{1})$-clustering for any $f$に対して$O(\log^2 n)$-approximationアルゴリズムを設計する。
これは、以前の$\widetilde{O}(\sqrt{n})$-approximationで改善されます。
第二に、一般的な$(f,g)$-clustering問題に対して$O(k)$-approximationを提供し、これは以前の$\widetilde{O}(\sqrt{kn})$-approximationアルゴリズムを改善し、Min-Load $k$-clusteringの最もよく知られた上限と一致する。
次に、$(f,g)$-clusteringの近似アルゴリズムを設計し、$k$-Center, $k$-Median, Min-Sum of Radii, Min-Load $k$-Clustering, (Top, $L_{1}$)-clustering, $(L_{\infty},g)$-clusteringの既知値である$f$と$g$を補間する。
関連論文リスト
- 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) - Generalization Performance of Ensemble Clustering: From Theory to Algorithm [57.176040163699554]
本稿では,アンサンブルクラスタリングにおける一般化誤差,過剰リスク,一貫性に着目した。
有限クラスタリングに様々な重みを割り当てることで、経験的平均クラスタリングと期待値との誤差を最小化する。
我々は、新しいアンサンブルクラスタリングアルゴリズムを開発するために、我々の理論をインスタンス化する。
論文 参考訳（メタデータ） (2025-06-01T09:34:52Z) - Clustering to Minimize Cluster-Aware Norm Objectives [0.3481985817302898]
与えられたデータセットの$P$を$k$クラスタに分割し、$X$の$k$センターを見つける。
中心の$xin X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。
目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。
論文 参考訳（メタデータ） (2024-10-31T16:33:40Z) - 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) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。
また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Differentially Private Clustering in Data Streams [56.26040303056582]
私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。
当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。
私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文 参考訳（メタデータ） (2023-06-05T12:22:46Z) - Approximating Fair Clustering with Cascaded Norm Objectives [10.69111036810888]
ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。
これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
論文 参考訳（メタデータ） (2021-11-08T20:18:10Z) - Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。
k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。
我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-30T15:49:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。