論文の概要: Dynamic algorithms for k-center on graphs
- arxiv url: http://arxiv.org/abs/2307.15557v1
- Date: Fri, 28 Jul 2023 13:50:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-31 12:24:18.017053
- Title: Dynamic algorithms for k-center on graphs
- Title（参考訳）: グラフ上のk中心の動的アルゴリズム
- Authors: Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari,
Antonis Skarlatos
- Abstract要約: エッジ更新を行う動的グラフ上での$k$-center問題に対する最初の効率的なアルゴリズムを提供する。
完全に動的な$(2+epsilon)$-approximationアルゴリズムを$k$-center問題に対して提案する。
- 参考スコア（独自算出の注目度）: 6.492259579837262
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we give the first efficient algorithms for the $k$-center
problem on dynamic graphs undergoing edge updates. In this problem, the goal is
to partition the input into $k$ sets by choosing $k$ centers such that the
maximum distance from any data point to the closest center is minimized. It is
known that it is NP-hard to get a better than $2$ approximation for this
problem.
While in many applications the input may naturally be modeled as a graph, all
prior works on $k$-center problem in dynamic settings are on metrics. In this
paper, we give a deterministic decremental $(2+\epsilon)$-approximation
algorithm and a randomized incremental $(4+\epsilon)$-approximation algorithm,
both with amortized update time $kn^{o(1)}$ for weighted graphs. Moreover, we
show a reduction that leads to a fully dynamic $(2+\epsilon)$-approximation
algorithm for the $k$-center problem, with worst-case update time that is
within a factor $k$ of the state-of-the-art upper bound for maintaining
$(1+\epsilon)$-approximate single-source distances in graphs. Matching this
bound is a natural goalpost because the approximate distances of each vertex to
its center can be used to maintain a $(2+\epsilon)$-approximation of the graph
diameter and the fastest known algorithms for such a diameter approximation
also rely on maintaining approximate single-source distances.
- Abstract（参考訳）: 本稿では、エッジ更新中の動的グラフにおける$k$-center問題に対する最初の効率的なアルゴリズムを提案する。
この問題では、任意のデータポイントから最寄りのセンターまでの最大距離が最小になるように、$k$センターを選択することで入力を$k$に分割する。
この問題に対して2ドル以上の近似を得ることはNPハードであることが知られている。
多くのアプリケーションでは、インプットは自然にグラフとしてモデル化されるが、動的セッティングにおける$k$-centerの問題は全てメトリクスに当てはまる。
本稿では,重み付きグラフに対して,決定論的漸近的$(2+\epsilon)$近似アルゴリズムとランダム化インクリメンタル$(4+\epsilon)$近似アルゴリズムと,償却更新時間$kn^{o(1)}$を与える。
さらに,$k$-center問題の完全動的$(2+\epsilon)$近似アルゴリズムと,$(1+\epsilon)$-approximate single-source distances in graphsを維持するための最先端上限の$k$以内の最悪のケース更新時間を示す。
なぜなら、各頂点から中心への近似距離はグラフの直径の$(2+\epsilon)$近似であり、そのような直径近似の最速のアルゴリズムは、近似的な単元距離の維持にも依存しているからである。
関連論文リスト
- Mini-Batch Kernel $k$-means [4.604003661048267]
私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。
実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
論文 参考訳（メタデータ） (2024-10-08T10:59:14Z) - Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
$ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。
我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。
我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
論文 参考訳（メタデータ） (2024-07-03T16:49:28Z) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An
Index-based Approach [9.13755431537592]
本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。
提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
論文 参考訳（メタデータ） (2023-01-01T10:57:36Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Coreset-based Strategies for Robust Center-type Problems [0.6875312133832077]
我々は、効率的なシーケンシャル、MapReduce、ストリーミングアルゴリズムをもたらす2つの問題に対するコアセットベースの戦略を考案する。
パラメータ$k,zepsilon,D$の広い範囲で、$|V|$で実行時間線形のシーケンシャルアルゴリズムと、ラウンド/パスが少なく、実質的にサブ線形な局所/ワーキングメモリを持つMapReduce/ストリーミングアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-02-18T10:04:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。