11 citations · 60 across the 21 of their papers we have counts for
5 papers · 1 filter
On Fair Division of Indivisible Items
Bhaskar Chaudhury, Yun Kuen Cheung, Jugal Garg +3
We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric…
Spanning Tree Congestion and Computation of Generalized Győri-Lovász Partition
L. Sunil Chandran, Yun Kuen Cheung, Davis Issac
We study a natural problem in graph sparsification, the Spanning Tree Congestion (\STC) problem. Informally, the \STC problem seeks a spanning tree with no tree-edge \emph{routing}…
Steiner Point Removal --- Distant Terminals Don't (Really) Bother
Yun Kuen Cheung
Given a weighted graph with a set of terminals , the Steiner Point Removal problem seeks for a minor of the graph with vertex set , such that the dis…
Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
Yun Kuen Cheung, Gramoz Goranci, Monika Henzinger
Given a graph where vertices are partitioned into terminals and non-terminals, the goal is to compress the graph (i.e., reduce the number of non-terminals) using minor operatio…
Multidimensional Divide-and-Conquer and Weighted Digital Sums
Y. K. Cheung, Philippe Flajolet, Mordecai Golin +1
This paper studies three types of functions arising separately in the analysis of algorithms that we analyze exactly using similar Mellin transform techniques. The first is the sol…