Chien-Chung Huang

collaborators

3 papers

cs.DS2026

Auction-Based Algorithms for Matroid Intersection: Near-Linear Query Complexity and Constant-Pass Semi-Streaming

Chien-Chung Huang, Yusuke Kobayashi

In this paper, we develop a new auction-based framework for matroid intersection and use it to obtain improved approximation algorithms in several computational settings. Our frame…

cs.DS2026

Polynomial Kernels with Reachability for Weighted $d$ -Matroid Intersection

Chien-Chung Huang, Naonori Kakimura, Yusuke Kobayashi +1

This paper studies randomized polynomial kernelization for the weighted $d$ -matroid intersection problem. While the problem is known to have a kernel of size $O (d^{(k - 1) d})$ wher…

cs.DS2023

Robust Sparsification for Matroid Intersection with Applications

Chien-Chung Huang, François Sellier

Matroid intersection is a classical optimization problem where, given two matroids over the same ground set, the goal is to find the largest common independent set. In this paper,…

Auction-Based Algorithms for Matroid Intersection: Near-Linear Query Complexity and Constant-Pass Semi-Streaming

Polynomial Kernels with Reachability for Weighted d-Matroid Intersection

Robust Sparsification for Matroid Intersection with Applications

Polynomial Kernels with Reachability for Weighted $d$ -Matroid Intersection