Source author record

Huiwen Yu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

3works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Approximate the k-Set Packing Problem by Local Improvements

We study algorithms based on local improvements for the $k$ -Set Packing problem. The well-known local improvement algorithm by Hurkens and Schrijver has been improved by Sviridenko and Ward from $\frac{k}{2}+ε$ to $\frac{k+2}{3}$ , and by Cygan to $\frac{k+1}{3}+ε$ for any $ε>0$ . In this paper, we achieve the approximation ratio $\frac{k+1}{3}+ε$ for the $k$ -Set Packing problem using a simple polynomial-time algorithm based on the method by Sviridenko and Ward. With the same approximation guarantee, our algorithm runs in time singly exponential in $\frac{1}{ε^2}$ , while the running time of Cygan's algorithm is doubly exponential in $\frac{1}ε$ . On the other hand, we construct an instance with locality gap $\frac{k+1}{3}$ for any algorithm using local improvements of size $O(n^{1/5})$ , here $n$ is the total number of sets. Thus, our approximation guarantee is optimal with respect to results achievable by algorithms based on local improvements.

preprint2014arXiv

Space Saving by Dynamic Algebraization

Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithm based on tree decompositions in polynomial space. We show how to construct a tree decomposition and extend the algebraic techniques of Lokshtanov and Nederlof such that the dynamic programming algorithm runs in time $O^*(2^h)$ , where $h$ is the maximum number of vertices in the union of bags on the root to leaf paths on a given tree decomposition, which is a parameter closely related to the tree-depth of a graph. We apply our algorithm to the problem of counting perfect matchings on grids and show that it outperforms other polynomial-space solutions. We also apply the algorithm to other set covering and partitioning problems.

preprint2011arXiv

Packing-Based Approximation Algorithm for the k-Set Cover Problem

We present a packing-based approximation algorithm for the $k$ -Set Cover problem. We introduce a new local search-based $k$ -set packing heuristic, and call it Restricted $k$ -Set Packing. We analyze its tight approximation ratio via a complicated combinatorial argument. Equipped with the Restricted $k$ -Set Packing algorithm, our $k$ -Set Cover algorithm is composed of the $k$ -Set Packing heuristic \cite{schrijver} for $k\geq 7$ , Restricted $k$ -Set Packing for $k=6,5,4$ and the semi-local $(2,1)$ -improvement \cite{furer} for 3-Set Cover. We show that our algorithm obtains a tight approximation ratio of $H_k-0.6402+Θ(\frac{1}{k})$ , where $H_k$ is the $k$ -th harmonic number. For small $k$ , our results are 1.8667 for $k=6$ , 1.7333 for $k=5$ and 1.5208 for $k=4$ . Our algorithm improves the currently best approximation ratio for the $k$ -Set Cover problem of any $k\geq 4$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.