Zobrazeno 1 - 10
of 207
pro vyhledávání: '"Mathieu, Claire"'
Autor:
Mathieu, Claire, Thurston, William
Splay trees are a simple and efficient dynamic data structure, invented by Sleator and Tarjan. The basic primitive for transforming a binary tree in this scheme is a rotation. Sleator, Tarjan, and Thurston proved that the maximum rotation distance be
Externí odkaz:
http://arxiv.org/abs/2409.17905
Autor:
Zhao, Fuheng, Agrawal, Divyakant, Abbadi, Amr El, Mathieu, Claire, Metwally, Ahmed, de Rougemont, Michel
In this paper, we present an advanced analysis of near optimal algorithms that use limited space to solve the frequency estimation, heavy hitters, frequent items, and top-k approximation in the bounded deletion model. We define the family of SpaceSav
Externí odkaz:
http://arxiv.org/abs/2309.12623
Autor:
Mathieu, Claire, de Rougemont, Michel
We study how to verify specific frequency distributions when we observe a stream of $N$ data items taken from a universe of $n$ distinct items. We introduce the \emph{relative Fr\'echet distance} to compare two frequency functions in a homogeneous ma
Externí odkaz:
http://arxiv.org/abs/2309.11175
In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of $n$ terminals, and a distance constraint $D$. The goal is to find a minimum number of tours starting and ending at the depot
Externí odkaz:
http://arxiv.org/abs/2210.03811
In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum
Externí odkaz:
http://arxiv.org/abs/2209.05520
Autor:
Mathieu, Claire, Zhou, Hang
In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal
Externí odkaz:
http://arxiv.org/abs/2202.05691
Autor:
Mathieu, Claire, Zhou, Hang
How efficiently can we find an unknown graph using distance queries between its vertices? We assume that the unknown graph is connected, unweighted, and has bounded degree. The goal is to find every edge in the graph. This problem admits a reconstruc
Externí odkaz:
http://arxiv.org/abs/2112.04549
Autor:
Mathieu, Claire, Zhou, Hang
We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.
Comment: Accepted for publicatio
Comment: Accepted for publicatio
Externí odkaz:
http://arxiv.org/abs/2111.03735
School choice is the two-sided matching market where students (on one side) are to be matched with schools (on the other side) based on their mutual preferences. The classical algorithm to solve this problem is the celebrated deferred acceptance proc
Externí odkaz:
http://arxiv.org/abs/2109.09089
Autor:
Mathieu, Claire, Zhou, Hang
We give a probabilistic analysis of the unit-demand Euclidean capacitated vehicle routing problem in the random setting, where the input distribution consists of $n$ unit-demand customers modeled as independent, identically distributed uniform random
Externí odkaz:
http://arxiv.org/abs/2109.06958