CHChien-Chung Huang

Chien-Chung Huang

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Chien-Chung Huang has a total of 7 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    FPT-Algorithms for the \ell-Matchoid Problem with a Coverage Objective

    by Chien-Chung Huang, Justin Ward

    We consider the problem of optimizing a coverage function under a $\ell$-matchoid of rank $k$. We design fixed-parameter algorithms as well as streaming algorithms to compute an exact solution. Unlike previous work that presumes linear representativity of matroids, we consider the general oracle model. For the special case where the coverage function is linear, we give a deterministic fixed-parameter algorithm parameterized by $\ell$ and $k$. This result, combined with the lower bounds of Lovasz, and Jensen and Korte demonstrates a separation between the $\ell$-matchoid and the matroid $\ell$-parity problems in the setting of fixed-parameter tractability. For a general coverage function, we give both deterministic and randomized fixed-parameter algorithms, parameterized by $\ell$ and $z$, where $z$ is the number of points covered in an optimal solution. The resulting algorithms can be directly translated into streaming algorithms. For unweighted coverage functions, we show that we can find an exact solution even when the function is given in the form of a value oracle (and so we do not have access to an explicit representation of the set system). Our result can be implemented in the streaming setting and stores a number of elements depending only on $\ell$ and $z$, but completely indpendent of the total size $n$ of the ground set. This shows that it is possible to circumvent the recent space lower bound of Feldman et al, by parameterizing the solution value. This result, combined with existing lower bounds, also provides a new separation between the space and time complexity of maximizing an arbitrary submodular function and a coverage function in the value oracle model.

    • 6 January 2021
    • Published by HAL in HAL
    Open Access

    Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

    by Chien-Chung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida

    Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is much gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat 1 − 1 e in the single-pass streaming model. Let n be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio 2

  • Open Access

    Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

    by Chien-Chung Huang, Naonori Kakimura

    We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a small fraction of the data stored in primary memory. We propose the following streaming algorithms taking $O(\varepsilon^{-1})$ passes: ----a $(1-e^{-1}-\varepsilon)$-approximation algorithm for the cardinality-constrained problem ---- a $(0.5-\varepsilon)$-approximation algorithm for the knapsack-constrained problem. Both of our algorithms run in $O^\ast(n)$ time, using $O^\ast(K)$ space, where $n$ is the size of the ground set and $K$ is the size of the knapsack. Here the term $O^\ast$ hides a polynomial of $\log K$ and $\varepsilon^{-1}$. Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes $O(n\varepsilon^{-1} \log (\varepsilon^{-1}\log K) )$ time, improving on the algorithm of Badanidiyuru and Vondr\'{a}k that takes $O(n \varepsilon^{-1} \log (\varepsilon^{-1} K) )$ time.

  • New Algorithms for Maximum Weight Matching and a Decomposition Theorem

    by Chien-Chung Huang, Telikepalli Kavitha

    We revisit the classical maximum weight matching problem in general graphs with nonnegative integral edge weights. We present an algorithm that operates by decomposing the problem into W unweighted versions of the problem, where W is the largest edge weight. Our algorithm has running time as good as the current fastest algorithms for the maximum weight matching problem when W is small. One of the highlights of our algorithm is that it also produces an integral optimal dual solution; thus our algorithm also returns an integral certificate corresponding to the maximum weight matching that was computed. Our algorithm yields a new proof to the total dual integrality of Edmonds’ matching polytope and it also gives rise to a decomposition theorem for the maximum weight of a matching in terms of the maximum size of a matching in certain subgraphs. We also consider the maximum weight capacitated b-matching problem in bipartite graphs with nonnegative integral edge weights and show that it can also be decomposed into W unweighted versions of the problem, where W is the largest edge weight. Our second algorithm is competitive with known algorithms when W is small.


  • Open Access

    A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges

    by Chien-Chung Huang, Sebastian Ott

    Makespan minimization in restricted assignment $(R|p_{ij}\in \{p_j, \infty\}|C_{\max})$ is a classical problem in the field of machine scheduling. In a landmark paper in 1990 [8], Lenstra, Shmoys, and Tardos gave a 2-approximation algorithm and proved that the problem cannot be approximated within 1.5 unless P=NP. The upper and lower bounds of the problem have been essentially unimproved in the intervening 25 years, despite several remarkable successful attempts in some special cases of the problem [2,4,12] recently. In this paper, we consider a special case called graph-balancing with light hyper edges, where heavy jobs can be assigned to at most two machines while light jobs can be assigned to any number of machines. For this case, we present algorithms with approximation ratios strictly better than 2. Specifically, Two job sizes: Suppose that light jobs have weight $w$ and heavy jobs have weight $W$, and $w < W$. We give a $1.5$-approximation algorithm (note that the current 1.5 lower bound is established in an even more restrictive setting [1,3]). Indeed, depending on the specific values of $w$ and $W$, sometimes our algorithm guarantees sub-1.5 approximation ratios. Arbitrary job sizes: Suppose that $W$ is the largest given weight, heavy jobs have weights in the range of $(\beta W, W]$, where $4/7\leq \beta < 1$, and light jobs have weights in the range of $(0,\beta W]$. We present a $(5/3+\beta/3)$-approximation algorithm. Our algorithms are purely combinatorial, without the need of solving a linear program as required in most other known approaches.

  • Open Access

    A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State

    by Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott

    We study classical deadline-based preemptive scheduling of tasks in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each task is specified by a release time, a deadline and a processing volume, and has to be scheduled on a single, speed-scalable processor that is supplied with a sleep state. In the sleep state, the processor consumes no energy, but a constant wake-up cost is required to transition back to the active state. In contrast to speed scaling alone, the addition of a sleep state makes it sometimes beneficial to accelerate the processing of tasks in order to transition the processor to the sleep state for longer amounts of time and incur further energy savings. The goal is to output a feasible schedule that minimizes the energy consumption. Since the introduction of the problem by Irani et al. [16], its exact computational complexity has been repeatedly posed as an open question (see e.g. [2,8,15]). The currently best known upper and lower bounds are a 4/3-approximation algorithm and NP-hardness due to [2] and [2,17], respectively. We close the aforementioned gap between the upper and lower bound on the computational complexity of speed scaling with sleep state by presenting a fully polynomial-time approximation scheme for the problem. The scheme is based on a transformation to a non-preemptive variant of the problem, and a discretization that exploits a carefully defined lexicographical ordering among schedules.