論文の概要: Incremental (k, z)-Clustering on Graphs

• arxiv url: http://arxiv.org/abs/2602.08542v1
• Date: Mon, 09 Feb 2026 11:43:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:25.198523
• Title: Incremental (k, z)-Clustering on Graphs
• Title（参考訳）: グラフ上のインクリメンタル(k, z)クラスタリング
• Authors: Emilio Cruciani, Sebastian Forster, Antonis Skarlatos,
• Abstract要約: 確率を一定要素近似で高い確率で維持するランダム化インクリメンタル$(k, z)$-clusteringアルゴリズムを開発した。 第1段階では、すべての対向エッジ挿入に対して、総更新時間$m1+o(1)$で、サイズ$tildeO(k)$の定数要素ビクリテリア近似解を維持できる。 第2段階では、バイクリテリア近似解によって誘導される動的重み付きインスタンス上で、定数係数近似$(k,z)$-クラスタリング解を維持する。
• 参考スコア（独自算出の注目度）: 2.3322477552758234
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a weighted undirected graph, a number of clusters $k$, and an exponent $z$, the goal in the $(k, z)$-clustering problem on graphs is to select $k$ vertices as centers that minimize the sum of the distances raised to the power $z$ of each vertex to its closest center. In the dynamic setting, the graph is subject to adversarial edge updates, and the goal is to maintain explicitly an exact $(k, z)$-clustering solution in the induced shortest-path metric. While efficient dynamic $k$-center approximation algorithms on graphs exist [Cruciani et al. SODA 2024], to the best of our knowledge, no prior work provides similar results for the dynamic $(k,z)$-clustering problem. As the main result of this paper, we develop a randomized incremental $(k, z)$-clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of $\tilde O(k m^{1+o(1)}+ k^{1+\frac{1}λ} m)$, where $λ\geq 1$ is an arbitrary fixed constant. Our incremental algorithm consists of two stages. In the first stage, we maintain a constant-factor bicriteria approximate solution of size $\tilde{O}(k)$ with a total update time of $m^{1+o(1)}$ over all adversarial edge insertions. This first stage is an intricate adaptation of the bicriteria approximation algorithm by Mettu and Plaxton [Machine Learning 2004] to incremental graphs. One of our key technical results is that the radii in their algorithm can be assumed to be non-decreasing while the approximation ratio remains constant, a property that may be of independent interest. In the second stage, we maintain a constant-factor approximate $(k,z)$-clustering solution on a dynamic weighted instance induced by the bicriteria approximate solution. For this subproblem, we employ a dynamic spanner algorithm together with a static $(k,z)$-clustering algorithm.
• Abstract（参考訳）: 重み付き無向グラフ、多数のクラスタ$k$、指数$z$が与えられたとき、グラフ上の$(k, z)$-クラスタリング問題におけるゴールは、各頂点の出力$z$への距離の和を最小化する中心として$k$頂点を選択することである。 動的な設定では、グラフは逆のエッジ更新を受けており、目標は、誘導された最短パス計量において、正確に$(k, z)$-clusteringソリューションを明示的に維持することである。 グラフ上の効率的な$k$-center近似アルゴリズムは存在するが [Cruciani et al SODA 2024] われわれの知る限り、これまでの研究では$(k,z)$-clustering問題に対して同様の結果が得られなかった。 この論文の主目的として、ランダム化された$(k, z)$-clusteringアルゴリズムを開発し、エッジ挿入を行うグラフにおける定数係数近似を高い確率で維持し、総更新時間$\tilde O(k m^{1+o(1)}+ k^{1+\frac{1}λ} m)$とする。 我々の増分アルゴリズムは2段階からなる。 第一段階では、すべての対向エッジ挿入に対して、総更新時間$m^{1+o(1)$で、サイズ$\tilde{O}(k)$の定数要素ビクリテリア近似解を維持する。 この第1段階は、Mettu と Plaxton [Machine Learning 2004] による Bicriteria approximation アルゴリズムの増分グラフへの複雑な適応である。 我々の重要な技術的成果の1つは、近似比が一定でありながらアルゴリズムのラジイが非減少であると仮定できることである。 第2段階では、バイクリテリア近似解によって誘導される動的重み付きインスタンス上で、定数係数近似$(k,z)$-クラスタリング解を維持する。 このサブプロブレムに対して、静的な$(k,z)$-clusteringアルゴリズムとともに動的スパンナーアルゴリズムを用いる。

関連論文リスト

• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• 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)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Dynamic algorithms for k-center on graphs [3.568439282784197]
  エッジ更新を行う動的グラフ上での$k$-center問題に対する最初の効率的なアルゴリズムを提供する。 完全に動的な$(2+epsilon)$-approximationアルゴリズムを$k$-center問題に対して提案する。
  論文  参考訳（メタデータ） (2023-07-28T13:50:57Z)
• 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)
• 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)
• Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [9.29659220237395]
  本稿では,相関クラスタリングの解法を提案する。 我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。 提案手法の主な要素はスパース線グラフ分解への新規な接続である。
  論文  参考訳（メタデータ） (2021-09-29T16:25:02Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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