6 citations · 19 across the 14 of their papers we have counts for
14 papers · 1 filter
Streaming algorithms for computing coresets and -median clustering in the Hamming space
Taha El Ghazi, Jonas Ellert, Chien-Chung Huang +1
Clustering is one of the most fundamental tools in data analysis, allowing large datasets to be summarized by a small number of representative points. Given a metric space $(\mathc…
Matroid-Constrained Vertex Cover
Chien-Chung Huang, François Sellier
In this paper, we introduce the problem of Matroid-Constrained Vertex Cover: given a graph with weights on the edges and a matroid imposed on the vertices, our problem is to choose…
Maximum Weight b-Matchings in Random-Order Streams
Chien-Chung Huang, François Sellier
We consider the maximum weight -matching problem in the random-order semi-streaming model. Assuming all weights are small integers drawn from , we present a $2 - \frac{1}…
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai +3
In the -edge-connected spanning subgraph (ECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to link failures: Given an -nod…
Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
Chien-Chung Huang, François Sellier
We consider the problem of maximizing a non-negative submodular function under the -matching constraint, in the semi-streaming model. When the function is linear, monotone, and…
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints
Chien-Chung Huang, Theophile Thiery, Justin Ward
We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general -matchoid constraint…