論文の概要: Fast Classical and Quantum Algorithms for Online $k$-server Problem on
Trees
- arxiv url: http://arxiv.org/abs/2008.00270v3
- Date: Wed, 28 Jul 2021 07:28:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-07 10:28:17.952128
- Title: Fast Classical and Quantum Algorithms for Online $k$-server Problem on
Trees
- Title（参考訳）: 木上の$k$サーバ問題に対する高速古典的および量子的アルゴリズム
- Authors: Ruslan Kapralov, Kamil Khadiev, Joshua Mokut, Yixin Shen, and Maxim
Yagafarov
- Abstract要約: 木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。
Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。
本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.19573380763700712
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider online algorithms for the $k$-server problem on trees. Chrobak
and Larmore proposed a $k$-competitive algorithm for this problem that has the
optimal competitive ratio. However, a naive implementation of their algorithm
has $O(n)$ time complexity for processing each query, where $n$ is the number
of nodes in the tree. We propose a new time-efficient implementation of this
algorithm that has $O(n\log n)$ time complexity for preprocessing and
$O\left(k^2 + k\cdot \log n\right)$ time for processing a query. We also
propose a quantum algorithm for the case where the nodes of the tree are
presented using string paths. In this case, no preprocessing is needed, and the
time complexity for each query is $O(k^2\sqrt{n}\log n)$. When the number of
queries is $o\left(\frac{\sqrt{n}}{k^2\log n}\right)$, we obtain a quantum
speed-up on the total runtime compared to our classical algorithm.
We also give a simple quantum algorithm to find the first marked element in a
collection of $m$ objects, that works even in the presence of two-sided bounded
errors on the input oracle. It has worst-case complexity $O(\sqrt{m})$. In the
particular case of one-sided errors on the input, it has expected time
complexity $O(\sqrt{x})$ where $x$ is the position of the first marked element.
Compare with previous work, our algorithm can handle errors in the input
oracle.
- Abstract（参考訳）: 木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。
Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。
しかし、それらのアルゴリズムの単純な実装は、各クエリを処理するのに$o(n)$の時間複雑性を持ち、$n$はツリー内のノード数である。
我々は,前処理に$O(n\log n)$ time complexity と,クエリ処理に $O\left(k^2 + k\cdot \log n\right)$ time を新たに提案する。
また,木のノードが文字列パスを用いて表現される場合の量子アルゴリズムを提案する。
この場合、前処理は不要であり、各クエリの時間複雑性は$O(k^2\sqrt{n}\log n)$である。
クエリ数が$o\left(\frac{\sqrt{n}}{k^2\log n}\right)$である場合、従来のアルゴリズムと比較して、総実行時の量子スピードアップが得られる。
また、入力オラクルに二辺有界誤差が存在する場合でも機能する$m$オブジェクトの集合の最初のマーク要素を見つけるための単純な量子アルゴリズムも提供する。
最悪の場合の複雑性は$O(\sqrt{m})$である。
入力上の片側誤差の場合、期待時間複雑さ$O(\sqrt{x})$ ここで、$x$は最初のマークされた要素の位置である。
従来の手法と比較して,本アルゴリズムは入力オラクルの誤りを処理できる。
関連論文リスト
- 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) - Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv
Factorization [2.684542790908823]
我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。
2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
論文 参考訳（メタデータ） (2023-11-03T09:09:23Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。
我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
論文 参考訳（メタデータ） (2020-12-02T15:32:52Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文 参考訳（メタデータ） (2020-05-28T22:44:01Z) - Quantum Algorithms for the Most Frequently String Search, Intersection
of Two String Sequences and Sorting of Strings Problems [0.0]
弦の3つの問題を解くアルゴリズムについて研究する。
1つ目は、最も頻度の高い文字列検索問題である。
2つ目は、2つの弦列の交叉である。
第三の問題は長さ$k$の$n$文字列をソートすることだ。
論文 参考訳（メタデータ） (2020-01-07T07:22:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。