論文の概要: On Complexity of 1-Center in Various Metrics
- arxiv url: http://arxiv.org/abs/2112.03222v2
- Date: Tue, 4 Apr 2023 22:41:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-06 16:45:20.973191
- Title: On Complexity of 1-Center in Various Metrics
- Title（参考訳）: 各種計量における1中心の複雑さについて
- Authors: Amir Abboud, Mohammad Hossein Bateni, Vincent Cohen-Addad, Karthik C.
S., and Saeed Seddighin
- Abstract要約: 計量空間における集合 $P$ of $n$ が与えられたとき、$P$ の点を見つけると、他の点への最大距離が $P$ になる。
この問題の複雑さを$d$-dimensional $ell_p$-metricsと編集およびUlamメトリクスで調べる。
- 参考スコア（独自算出の注目度）: 20.92192456060298
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the classic 1-center problem: Given a set $P$ of $n$ points in a
metric space find the point in $P$ that minimizes the maximum distance to the
other points of $P$. We study the complexity of this problem in $d$-dimensional
$\ell_p$-metrics and in edit and Ulam metrics over strings of length $d$. Our
results for the 1-center problem may be classified based on $d$ as follows.
$\bullet$ Small $d$: Assuming the hitting set conjecture (HSC), we show that
when $d=\omega(\log n)$, no subquadratic algorithm can solve 1-center problem
in any of the $\ell_p$-metrics, or in edit or Ulam metrics.
$\bullet$ Large $d$: When $d=\Omega(n)$, we extend our conditional lower
bound to rule out subquartic algorithms for 1-center problem in edit metric
(assuming Quantified SETH). On the other hand, we give a
$(1+\epsilon)$-approximation for 1-center in Ulam metric with running time
$\tilde{O_{\varepsilon}}(nd+n^2\sqrt{d})$.
We also strengthen some of the above lower bounds by allowing approximations
or by reducing the dimension $d$, but only against a weaker class of algorithms
which list all requisite solutions. Moreover, we extend one of our hardness
results to rule out subquartic algorithms for the well-studied 1-median problem
in the edit metric, where given a set of $n$ strings each of length $n$, the
goal is to find a string in the set that minimizes the sum of the edit
distances to the rest of the strings in the set.
- Abstract（参考訳）: 古典的な 1 中心問題を考える: 計量空間の集合 $P$ の$n$ 点が与えられたとき、P$ の点を見つけると、他の点への最大距離が $P$ になる。
我々は、この問題の複雑さを、$d$-dimensional $\ell_p$-metricsと、$d$の文字列に対するeditおよびummメトリクスで研究する。
1中心問題に対する我々の結果は以下の$d$に基づいて分類することができる。
$\bullet$ small $d$: ヒット集合予想 (hsc) を仮定すると、$d=\omega(\log n)$ のとき、$\ell_p$-metrics または編集または ulam メトリクスのいずれかにおいて、1-センタ問題を解くサブクアドラティックなアルゴリズムは存在しない。
$\bullet$ Large $d$: if $d=\Omega(n)$ では、条件付き下限を拡張して、(量子化SETHを仮定すると)1中心問題に対する部分量子アルゴリズムを除外します。
一方、1+\epsilon)$-approximation for 1-center in Ulam metric with running time $\tilde{O_{\varepsilon}}(nd+n^2\sqrt{d})$とする。
また、上記の下限のいくつかを近似化したり、次元 $d$ を減らすことで強化するが、全ての必要な解をリストアップするより弱いアルゴリズムのクラスに対してのみ適用する。
さらに、私たちは難しさの1つを拡張して、編集メートル法でよく研究された1-median問題の下位4次アルゴリズムを除外し、長さ$n$のそれぞれ$n$文字列のセットが与えられた場合、編集距離の和をセット内の他の文字列の和に最小化する文字列を見つけることを目標としている。
関連論文リスト
- 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) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Towards Optimal Lower Bounds for k-median and k-means Coresets [25.713987341159918]
計量空間における点の集合が与えられたとき、$(k,z)$-クラスタリング問題は、センターと呼ばれる点の集合を見つけることからなる。
我々は、$(k,z)$クラスタリングの任意のコアセットが、少なくとも$Omega(k varepsilon-2 log n)$と$Omega(k varepsilon-2 D)$ポイントでなければならないことを示す。
論文 参考訳（メタデータ） (2022-02-25T16:13:28Z) - Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。
局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文 参考訳（メタデータ） (2021-05-31T14:41:40Z) - 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) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。