1 citations · 2 across the 3 of their papers we have counts for
5 papers
Hardness and Approximation Algorithms for Balanced Districting Problems
Prathamesh Dharangutte, Jie Gao, Shang-En Huang +1
We introduce and study the problem of balanced districting, where given an undirected graph with vertices carrying two types of weights (different population, resource types, etc)…
Deterministic Expander Routing: Faster and More Versatile
Yi-Jun Chang, Shang-En Huang, Hsin-Hao Su
We consider the expander routing problem formulated by Ghaffari, Kuhn, and Su (PODC 2017), where the goal is to route all the tokens to their destinations given that each vertex is…
Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
Nairen Cao, Shang-En Huang, Hsin-Hao Su
In this paper, we study parallel algorithms for the correlation clustering problem, where every pair of two different entities is labeled with similar or dissimilar. The goal is to…
Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
Shang-En Huang, Seth Pettie, Leqi Zhu
It has been known since the early 1980s that Byzantine Agreement in the full information, asynchronous model is impossible to solve deterministically against even one crash fault […
Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts
Shang-En Huang, Seth Pettie
We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce t…