Chengzhang Wan

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2026

A Sharp Analysis of Fixed Offset Hash Tables

Yuhao Guo, Seth Pettie, Chengzhang Wan

We consider the class of open addressing hash tables that uses a fixed offset sequence $r_{0}, r_{1}, \dots, r_{n - 1}$ to find an open slot in the table. As special cases this subsumes li…

cs.DS2026

Iterative Randomized Rounding for Better-Than-2 k-Median Approximation

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

We study the classic $k$ -median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a $(2+\varepsil…

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 Sharp Analysis of Fixed Offset Hash Tables

Iterative Randomized Rounding for Better-Than-2 k-Median Approximation

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