Zobrazeno 1 - 10
of 1 099
pro vyhledávání: '"Cassis, P."'
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
Autor:
Elisa Matias Vieira de Melo, Bruno Cassis Antunes Rodrigues, Felipe Teijeiro Cabral, Luíza Alves Monteiro Torreão Villarim, Maria Fernanda Mendes
Publikováno v:
Arquivos de Neuro-Psiquiatria, Vol 82, Iss 10, Pp 001-011 (2024)
A few decades ago, women diagnosed with multiple sclerosis were discouraged from becoming pregnant. However, with new knowledge about the disease and treatments, this recommendation has changed, and it is pregnancy after the diagnosis of the disease
Externí odkaz:
https://doaj.org/article/4238e00fa9964030a7404308d2982364
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
Autor:
Nancy E. Schoenberg, Jimmy Robinson, Margaret McGladrey, Lisa A. Cassis, Darwin Conwell, Kevin J. Pearson, Lisa R. Tannock, Donna Wilcock, Stephanie White
Publikováno v:
BMC Medical Education, Vol 24, Iss 1, Pp 1-11 (2024)
Abstract Background Novel and comprehensive approaches are needed to address shortcomings in the diversity and inclusiveness of the scientific workforce. In response to this need and informed by multiple programs and data sources, we created the Rese
Externí odkaz:
https://doaj.org/article/f6fa21a4659c48498ca440730fcaa08c
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