論文の概要: Dynamic Consistent $k$-Center Clustering with Optimal Recourse
- arxiv url: http://arxiv.org/abs/2412.03238v1
- Date: Wed, 04 Dec 2024 11:39:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-05 15:06:44.251432
- Title: Dynamic Consistent $k$-Center Clustering with Optimal Recourse
- Title（参考訳）: 最適リコース付き動的一貫性$k$-Centerクラスタリング
- Authors: Sebastian Forster, Antonis Skarlatos,
- Abstract要約: 我々は、$k$-centerクラスタリング問題において、決定論的定数係数近似を開発することにより、最適リコース境界を許容することを証明する。
当社のインクリメンタルアルゴリズムは,Charikar,Chekuri,Feder,Motwaniによる8ドルの近似アルゴリズムよりも改善されている。
- 参考スコア（独自算出の注目度）: 0.6077284832583713
- License:
- Abstract: Given points from an arbitrary metric space and a sequence of point updates sent by an adversary, what is the minimum recourse per update (i.e., the minimum number of changes needed to the set of centers after an update), in order to maintain a constant-factor approximation to a $k$-clustering problem? This question has received attention in recent years under the name consistent clustering. Previous works by Lattanzi and Vassilvitskii [ICLM '17] and Fichtenberger, Lattanzi, Norouzi-Fard, and Svensson [SODA '21] studied $k$-clustering objectives, including the $k$-center and the $k$-median objectives, under only point insertions. In this paper we study the $k$-center objective in the fully dynamic setting, where the update is either a point insertion or a point deletion. Before our work, {\L}\k{a}cki, Haeupler, Grunau, Rozho\v{n}, and Jayaram [SODA '24] gave a deterministic fully dynamic constant-factor approximation algorithm for the $k$-center objective with worst-case recourse of $2$ per update. In this work, we prove that the $k$-center clustering problem admits optimal recourse bounds by developing a deterministic fully dynamic constant-factor approximation algorithm with worst-case recourse of $1$ per update. Moreover our algorithm performs simple choices based on light data structures, and thus is arguably more direct and faster than the previous one which uses a sophisticated combinatorial structure. Additionally, we develop a new deterministic decremental algorithm and a new deterministic incremental algorithm, both of which maintain a $6$-approximate $k$-center solution with worst-case recourse of $1$ per update. Our incremental algorithm improves over the $8$-approximation algorithm by Charikar, Chekuri, Feder, and Motwani [STOC '97]. Finally, we remark that since all three of our algorithms are deterministic, they work against an adaptive adversary.
- Abstract（参考訳）: 任意の距離空間からの点と、敵が送信した点更新の列を与えられた場合、$k$クラスタリング問題に対する定数係数近似を維持するために、更新毎に最小のリコース(すなわち、更新後の中心集合に必要となる最小限の変更数)は何か。
この問題は近年、一貫したクラスタリングという名前で注目されている。
Lattanzi と Vassilvitskii [ICLM '17] と Fichtenberger, Lattanzi, Norouzi-Fard, Svensson [SODA '21] による以前の研究は、点挿入のみで$k$-center や$k$-median の目的を含む$k$-clustering の目的を研究した。
本稿では,完全動的設定における$k$-centerの目的について検討する。
我々の研究の前に、Haeupler、Grunau、Rozho\v{n}、Jayaram [SODA '24] は、決定論的に完全に動的で定数係数の近似アルゴリズムをk$-centerの目標に対して提供し、1回の更新で最悪のケースリコースで2ドルを支払った。
本研究では,$k$-centerクラスタリング問題において,決定論的完全動的定数係数近似アルゴリズムを開発することにより,最適リコースバウンダリを許容できることを示す。
さらに,本アルゴリズムは,光データ構造に基づく簡単な選択を行うため,高度な組合せ構造を用いた従来のアルゴリズムよりも直接的かつ高速である。
さらに,新たな決定論的デクリメントアルゴリズムと新たな決定論的インクリメンタルアルゴリズムを開発した。
我々のインクリメンタルアルゴリズムは、Charikar, Chekuri, Feder, Motwani (STOC '97] による8ドルの近似アルゴリズムよりも改善されている。
最後に、我々の3つのアルゴリズムは決定論的であるため、適応的な敵に対して作用する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - 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) - Multi-Swap $k$-Means++ [30.967186562175893]
Arthur and Vassilvitskii (SODA 2007)の$k$-means++アルゴリズムは、人気のある$k$-meansクラスタリングの目的を最適化するための実践者の選択アルゴリズムであることが多い。
Lattanzi氏とSohler氏(ICML)は、$k$-means++を$O(k log log k)$で拡張して、$k$-meansクラスタリング問題に$c$-approximationをもたらすよう提案した。
論文 参考訳（メタデータ） (2023-09-28T12:31:35Z) - Improved Learning-augmented Algorithms for k-means and k-medians
Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。
本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文 参考訳（メタデータ） (2022-10-31T03:00:11Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳（メタデータ） (2022-05-03T16:40:22Z) - Better Algorithms for Individually Fair $k$-Clustering [4.936817539835045]
Jung, Kannan, Lutz [FORC 2020]は、$ell_infty$または$k$-Centerの目的に対して、証明可能な(近似的な)フェアネスと客観的保証を備えたクラスタリングアルゴリズムを導入した。Mahabadi氏とVakilian氏(ICML 2020)は、この問題を再考して、すべての$ell_p$-normsに対してローカル検索アルゴリズムを提供する。
我々は、既知のLPラウンドリング技術を変更することで、MV20よりもはるかに優れた目標に対して最悪のケースを保証できることを実証的に証明し、この目標が最適に非常に近いことを実証した。
論文 参考訳（メタデータ） (2021-06-23T04:16:46Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering [0.0]
ローン申請や広告などの人間中心の意思決定システムへのデータクラスタリングの適用において、クラスタリングの結果は異なる人口集団の人々に対して差別される可能性がある。
そこで我々は,$k$-meansの更新とグループスワップ更新を併用した,新たな交代バランス型$k$-means (SAKM) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-29T01:47:15Z) - Revisiting Priority $k$-Center: Fairness and Outliers [5.3898004059026325]
我々は,プライオリティ $k$-center に対して定数係数近似アルゴリズムを導出するフレームワークを開発した。
私たちのフレームワークは,matroid と knapsack の制約に対する優先度 $k$-center の一般化にも拡張しています。
論文 参考訳（メタデータ） (2021-03-04T21:15:37Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。