Zobrazeno 1 - 10
of 107
pro vyhledávání: '"Jacob, Riko"'
A \emph{saddlepoint} of an $n \times n$ matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the \emph{value} of a two-player zero-sum game, corresponding to its pure-strategy Nash equilibria; efficiently
Externí odkaz:
http://arxiv.org/abs/2401.06512
Autor:
Goswami, Mayank, Jacob, Riko
The problem of sorting with priced information was introduced by [Charikar, Fagin, Guruswami, Kleinberg, Raghavan, Sahai (CFGKRS), STOC 2000]. In this setting, different comparisons have different (potentially infinite) costs. The goal is to find a s
Externí odkaz:
http://arxiv.org/abs/2311.05773
A saddlepoint of an $n \times n$ matrix $A$ is an entry of $A$ that is a maximum in its row and a minimum in its column. Knuth (1968) gave several different algorithms for finding a saddlepoint. The worst-case running time of these algorithms is $\Th
Externí odkaz:
http://arxiv.org/abs/2310.16801
Autor:
Goswami, Mayank, Jacob, Riko
We generalize the classical nuts and bolts problem to a setting where the input is a collection of $n$ nuts and $m$ bolts, and there is no promise of any matching pairs. It is not allowed to compare a nut directly with a nut or a bolt directly with a
Externí odkaz:
http://arxiv.org/abs/2211.04601
The fragile complexity of a comparison-based algorithm is $f(n)$ if each input element participates in $O(f(n))$ comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i.e., algorith
Externí odkaz:
http://arxiv.org/abs/2102.00338
We consider static, external memory indexes for exact and approximate versions of the $k$-nearest neighbor ($k$-NN) problem, and show new lower bounds under a standard indivisibility assumption: - Polynomial space indexing schemes for high-dimensiona
Externí odkaz:
http://arxiv.org/abs/2002.04870
We present priority queues in the cache-oblivious external memory model with block size $B$ and main memory size $M$ that support on $N$ elements, operation \textsc{UPDATE} (combination of \textsc{INSERT} and \textsc{DECREASEKEY}) in $O \left(\frac{1
Externí odkaz:
http://arxiv.org/abs/1903.03147
Autor:
Jacob, Riko, Brodal, Gerth Stølting
In this article, we determine the amortized computational complexity of the planar dynamic convex hull problem by querying. We present a data structure that maintains a set of n points in the plane under the insertion and deletion of points in amorti
Externí odkaz:
http://arxiv.org/abs/1902.11169
Autor:
Afshani, Peyman, Fagerberg, Rolf, Hammer, David, Jacob, Riko, Kostitsyna, Irina, Meyer, Ulrich, Penschuck, Manuel, Sitchinava, Nodari
We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We g
Externí odkaz:
http://arxiv.org/abs/1901.02857
An oblivious data structure is a data structure where the memory access patterns reveals no information about the operations performed on it. Such data structures were introduced by Wang et al. [ACM SIGSAC'14] and are intended for situations where on
Externí odkaz:
http://arxiv.org/abs/1810.10635