research
∙
05/30/2023
Optimal energetic paths for electric cars
A weighted directed graph G=(V,A,c), where A⊆ V× V and c:A→ R, describes...
share
research
∙
12/21/2022
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Assuming the Unique Games Conjecture (UGC), the best approximation ratio...
research
∙
11/20/2022
Optimal resizable arrays
A resizable array is an array that can grow and shrink by the addition o...
research
∙
01/18/2022
Finding Strong Components Using Depth-First Search
We survey three algorithms that use depth-first search to find strong co...
research
∙
09/22/2020
On the Mysteries of MAX NAE-SAT
MAX NAE-SAT is a natural optimization problem, closely related to its be...
research
∙
09/24/2019
Random k-out subgraph leaves only O(n/k) inter-component edges
Each vertex of an arbitrary simple graph on n vertices chooses k random ...
research
∙
06/22/2018
Improved bounds for multipass pairing heaps and path-balanced binary search trees
We revisit multipass pairing heaps and path-balanced binary search trees...
research
∙
02/20/2018