Zobrazeno 1 - 9
of 9
pro vyhledávání: '"Cassis, Alejandro"'
We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation algorithm in almost-linear time, recent years have witnessed a notable s
Externí odkaz:
http://arxiv.org/abs/2312.01759
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions of characters needed to transform one string into the other. The textbook dynamic-programming algorithm computes the edit distance of two length-$n$ st
Externí odkaz:
http://arxiv.org/abs/2305.06659
Autor:
Bringmann, Karl, Cassis, Alejandro
We revisit the classic 0-1-Knapsack problem, in which we are given $n$ items with their weights and profits as well as a weight budget $W$, and the goal is to find a subset of items of total weight at most $W$ that maximizes the total profit. We stud
Externí odkaz:
http://arxiv.org/abs/2305.01593
In this work we revisit the fundamental Single-Source Shortest Paths (SSSP) problem with possibly negative edge weights. A recent breakthrough result by Bernstein, Nanongkai and Wulff-Nilsen established a near-linear $O(m \log^8(n) \log(W))$-time alg
Externí odkaz:
http://arxiv.org/abs/2304.05279
Autor:
Bringmann, Karl, Cassis, Alejandro
We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack: * Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time $\widetilde{O}(n + \min\{n OPT, n W, OPT^2, W^2\})$, where $n$ is the num
Externí odkaz:
http://arxiv.org/abs/2205.08493
We study the problem of approximating the edit distance of two strings in sublinear time, in a setting where one or both string(s) are preprocessed, as initiated by Goldenberg, Rubinstein, Saha (STOC '20). Specifically, in the $(k, K)$-gap edit dista
Externí odkaz:
http://arxiv.org/abs/2204.14137
We initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest Neighbor in the Hamming metric, Maximum Inner Product, optimization v
Externí odkaz:
http://arxiv.org/abs/2204.11681
We revisit the task of computing the edit distance in sublinear time. In the $(k,K)$-gap edit distance problem the task is to distinguish whether the edit distance of two strings is at most $k$ or at least $K$. It has been established by Goldenberg,
Externí odkaz:
http://arxiv.org/abs/2202.08066
We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019
Externí odkaz:
http://arxiv.org/abs/2107.01721