Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees

• URL: http://arxiv.org/abs/2008.00270v3
• Date: Wed, 28 Jul 2021 07:28:08 GMT
• Title: Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees
• Authors: Ruslan Kapralov, Kamil Khadiev, Joshua Mokut, Yixin Shen, and Maxim Yagafarov
• Abstract summary: 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. We propose a new time-efficient implementation of this algorithm that has $O(nlog n)$ time complexity for preprocessing.
• Score: 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.

Related papers

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  We present a quantum $tildeO(sqrtnk+k2)$-time algorithm that uses $tildeO(sqrtnz)$ queries, where $tildeO(cdot)$ hides polylogarithmic factors. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $tildeO(sqrtnz)$.
  arXiv  Detail & Related papers  (2023-11-03T09:09:23Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
  arXiv  Detail & Related papers  (2022-05-19T16:04:40Z)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
  arXiv  Detail & Related papers  (2021-05-18T06:51:11Z)
• Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
  We show a modified span program algorithm to show these speed-ups persist even without having a promise ahead of time. Our algorithm uses $tildeO(sqrtkn)$ queries to solve this problem if there is a path with at most $k$ edges.
  arXiv  Detail & Related papers  (2020-12-02T15:32:52Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
  We study algorithms for solving the problem of constructing a text from a dictionary (sequence of small strings) The problem has an application in bioinformatics and has a connection with the Sequence assembly method for reconstructing a long DNA sequence from small fragments.
  arXiv  Detail & Related papers  (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]
  We study algorithms for solving three problems on strings. The first one is the Most Frequently String Search Problem. The second is searching intersection of two sequences of strings. The third problem is sorting of $n$ strings of length $k$.
  arXiv  Detail & Related papers  (2020-01-07T07:22:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.