Yuhao Guo

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

A Simple Analysis of Quadratic Probing and Other Open Addressing Schemes

Yuhao Guo, Seth Pettie, Chengzhang Wan

In open addressed hashing, quadratic probing is attractive for striking a nice balance between having a high locality of reference and a low number of probes per search. However, t…

cs.DS2026

The Greedy Binary Search Tree is Non-trivially Competitive

Yuhao Guo, Seth Pettie, Daniel Skora +1

We prove that the $Greedy$ binary search tree is $2^{O (l o g l o g n)}$ -competitive. It is widely conjectured that $Greedy$ is $O (1)$ -competitive, but before…

cs.DS2026

$k$ -Clustering via Iterative Randomized Rounding

Jarosław Byrka, Yuhao Guo, Yang Hu +3

In this work we propose a single rounding algorithm for the fractional solutions of the standard LP relaxation for $k$ -clustering. As a starting point, we obtain an iterative round…

A Simple Analysis of Quadratic Probing and Other Open Addressing Schemes

The Greedy Binary Search Tree is Non-trivially Competitive

k-Clustering via Iterative Randomized Rounding

$k$ -Clustering via Iterative Randomized Rounding