68 citations · 72 across the 7 of their papers we have counts for
6 papers · 1 filter
Relative Error Fair Clustering in the Weak-Strong Oracle Model
Vladimir Braverman, Prathamesh Dharangutte, Shaofeng H. -C. Jiang +4
We study fair clustering problems in a setting where distance information is obtained from two sources: a strong oracle providing exact distances, but at a high cost, and a weak or…
Fair Clustering in the Sliding Window Model
Vincent Cohen-Addad, Shaofeng H. -C. Jiang, Qiaoyuan Yang +2
We study streaming algorithms for proportionally fair clustering, a notion originally suggested by Chierichetti et. al. (2017), in the sliding window model. We show that although t…
Algorithms for the Generalized Poset Sorting Problem
Shaofeng H. -C. Jiang, Wenqian Wang, Yubo Zhang +1
We consider a generalized poset sorting problem (GPS), in which we are given a query graph and an unknown poset that is defined on the same ver…
Online Facility Location with Predictions
Shaofeng H. -C. Jiang, Erzhi Liu, You Lyu +2
We provide nearly optimal algorithms for online facility location (OFL) with predictions. In OFL, demand points arrive in order and the algorithm must irrevocably assign each d…
Coresets for Kernel Clustering
Shaofeng H. -C. Jiang, Robert Krauthgamer, Jianing Lou +1
We devise coresets for kernel -Means with a general kernel, and use them to obtain new, more efficient, algorithms. Kernel -Means has superior clustering capability compared…
Generalized Sorting with Predictions
Pinyan Lu, Xuandi Ren, Enze Sun +1
Generalized sorting problem, also known as sorting with forbidden comparisons, was first introduced by Huang et al. together with a randomized algorithm which requires $\tilde O(n^…