Source author record

Guohui Lin

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 Computational Geometry Discrete Mathematics math.CO

Catalog footprint

Research overview

6works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

An efficient polynomial-time approximation scheme for parallel multi-stage open shops

Various new scheduling problems have been arising from practical production processes and spawning new research areas in the scheduling field. We study the parallel multi-stage open shops problem, which generalizes the classic open shop scheduling and parallel machine scheduling problems. Given m identical k-stage open shops and a set of n jobs, we aim to process all jobs on these open shops with the minimum makespan, i.e., the completion time of the last job, under the constraint that job preemption is not allowed. We present an efficient polynomial-time approximation scheme (EPTAS) for the case when both m and k are constant. The main idea for our EPTAS is the combination of several categorization, scaling, and linear programming rounding techniques. Jobs and/or operations are first scaled and then categorized carefully into multiple types so that different types of jobs and/or operations are scheduled appropriately without increasing the makespan too much.

preprint2022arXiv

Approximation algorithms for covering vertices by long paths

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least $k$ vertices is considered long. When $k \le 3$ , the problem is polynomial time solvable; when $k$ is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed $k \ge 4$ , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a $k$ -approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when $k = 4$ , the problem admits a $4$ -approximation algorithm which was presented recently. We propose the first $(0.4394 k + O(1))$ -approximation algorithm for the general problem and an improved $2$ -approximation algorithm when $k = 4$ . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies.

preprint2020arXiv

Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles

An acyclic edge coloring of a graph $G$ is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiam{č}ik (1978) and Alon, Sudakov and Zaks (2001) states that every simple graph with maximum degree $Δ$ is acyclically edge $(Δ+ 2)$ -colorable. Despite many milestones, the conjecture remains open even for planar graphs. In this paper, we confirm affirmatively the conjecture on planar graphs without intersecting triangles. We do so by first showing, by discharging methods, that every planar graph without intersecting triangles must have at least one of the six specified groups of local structures, and then proving the conjecture by recoloring certain edges in each such local structure and by induction on the number of edges in the graph.

preprint2020arXiv

On Computing a Center Persistence Diagram

Throughout this paper, a persistence diagram ${\cal P}$ is composed of a set $P$ of planar points (each corresponding to a topological feature) above the line $Y=X$ , as well as the line $Y=X$ itself, i.e., ${\cal P}=P\cup\{(x,y)|y=x\}$ . Given a set of persistence diagrams ${\cal P}_1,...,{\cal P}_m$ , for the data reduction purpose, one way to summarize their topological features is to compute the {\em center} ${\cal C}$ of them first under the bottleneck distance. We consider two discrete versions and one continuous version. For technical reasons, we first focus on the case when $|P_i|$ 's are all the same (i.e., all have the same size $n$ ), and the problem is to compute a center point set $C$ under the bottleneck matching distance. We show, by a non-trivial reduction from the Planar 3D-Matching problem, that this problem is NP-hard even when $m=3$ diagrams are given. This implies that the general center problem for persistence diagrams under the bottleneck distance, when $P_i$ 's possibly have different sizes, is also NP-hard when $m\geq 3$ . On the positive side, we show that this problem is polynomially solvable when $m=2$ and admits a factor-2 approximation for $m\geq 3$ . These positive results hold for any $L_p$ metric when $P_i$ 's are point sets of the same size, and also hold for the case when $P_i$ 's have different sizes in the $L_\infty$ metric (i.e., for the Center Persistence Diagram problem). This is the best possible in polynomial time for the Center Persistence Diagram under the bottleneck distance unless P = NP. All these results hold for both of the discrete versions as well as the continuous version; in fact, the NP-hardness and approximation results also hold under the Wasserstein distance for the continuous version.

preprint2013arXiv

Algorithms for Cut Problems on Trees

We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that runs in time $O^{*}(ρ^k)$ , where $ρ= \sqrt{\sqrt{2} + 1} \approx 1.555$ is the positive root of the polynomial $x^4-2x^2-1$ . This improves the current-best algorithm of Chen et al. that runs in time $O^{*}(1.619^k)$ . For the {\sc generalized multiway cut on trees} problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the {\sc generalized multiway cut on trees} problem to the {\sc multicut on trees} problem, our results give a parameterized algorithm that solves the {\sc generalized multiway cut on trees} problem in time $O^{*}(ρ^k)$ , where $ρ= \sqrt{\sqrt{2} + 1} \approx 1.555$ time.

preprint2013arXiv

An approximation algorithm for the Bandpass-2 problem

The general Bandpass- $B$ problem is NP-hard and can be approximated by a reduction into the weighted $B$ -set packing problem, with a worst case performance ratio of $O(B^2)$ . When $B = 2$ , a maximum weight matching gives a 2-approximation to the problem. In this paper, we call the Bandpass-2 problem simply the Bandpass problem. The Bandpass problem can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present a ${426}{227}$ -approximation algorithm for the problem. Such an improved approximation is built on an intrinsic structural property proven for the optimal solution and several novel schemes to partition a $b$ -matching into desired matchings.

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.