Publications (27)
A local search -approximation algorithm for the minimum -path partition problem
Yong Chen, Randy Goebel, Guohui Lin +5
Given a graph , the -path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most to cover all the vertices of . It i…
An efficient polynomial-time approximation scheme for parallel multi-stage open shops
Jianming Dong, Ruyan Jin, Guohui Lin +3
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 ope…
Single machine scheduling with job-dependent machine deterioration
Wenchang Luo, Yao Xu, Weitian Tong +1
We consider the single machine scheduling problem with job-dependent machine deterioration. In the problem, we are given a single machine with an initial non-negative maintenance l…
Approximation algorithms for the three-machine proportionate mixed shop scheduling
Longcheng Liu, Yong Chen, Jianming Dong +6
A mixed shop is a manufacturing infrastructure designed to process a mixture of a set of flow-shop jobs and a set of open-shop jobs. Mixed shops are in general much more complex to…
A local search 2.917-approximation algorithm for duo-preservation string mapping
Yao Xu, Yong Chen, Taibo Luo +1
We study the {\em maximum duo-preservation string mapping} ({\sc Max-Duo}) problem, which is the complement of the well studied {\em minimum common string partition} ({\sc MCSP}) p…
Algorithms for Cut Problems on Trees
Iyad Kanj, Guohui Lin, Tian Liu +7
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 ru…
Approximately covering vertices by order- or longer paths
Mingyang Gong, Zhi-Zhong Chen, Guohui Lin +1
This paper studies , which is to cover as many vertices as possible in a given graph by vertex-disjoint -paths (i.e., paths each with at least five verti…
A -approximation algorithm for the -Max-Duo problem
Yao Xu, Yong Chen, Guohui Lin +3
The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the well studied minimum common string partition (MCSP) problem, both of which have applications…
An improved local search based algorithm for -star partition
Mingyang Gong, Guohui Lin, Brendan Mumey
We study the -star partition problem that aims to find a minimum collection of vertex-disjoint stars, each having at most vertices to cover all vertices in a simple undire…
Randomized algorithms for fully online multiprocessor scheduling with testing
Mingyang Gong, Zhi-Zhong Chen, Guohui Lin +1
We contribute the first randomized algorithm that is an integration of arbitrarily many deterministic algorithms for the fully online multiprocessor scheduling with testing problem…
An Approximation Algorithm for Covering Vertices by 4^+-Paths
Mingyang Gong, Zhi-Zhong Chen, Guohui Lin +1
This paper deals with the problem of finding a collection of vertex-disjoint paths in a given graph G=(V,E) such that each path has at least four vertices and the total number of v…
Planar graphs are acyclically edge -colorable
Qiaojun Shu, Guohui Lin
An edge coloring of a graph is to color all the edges in the graph such that adjacent edges receive different colors. It is acyclic if each cycle in the graph receives at least…
Approximation algorithms for covering vertices by long paths
Mingyang Gong, Brett Edgar, Jing Fan +2
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…
Approximation algorithms for two-machine flow-shop scheduling with a conflict graph
Yinhui Cai, Guangting Chen, Yong Chen +4
Path cover is a well-known intractable problem that finds a minimum number of vertex disjoint paths in a given graph to cover all the vertices. We show that a variant, where the ob…
On Computing a Center Persistence Diagram
Yuya Higashikawa, Naoki Katoh, Guohui Lin +4
Throughout this paper, a persistence diagram is composed of a set of planar points (each corresponding to a topological feature) above the line , as well as the…
Approximation algorithms for the directed path partition problems
Yong Chen, Zhi-Zhong Chen, Curtis Kennedy +3
Given a directed graph , the -path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most to cover all the ver…
Approximation algorithms for the maximum weight internal spanning tree problem
Zhi-Zhong Chen, Guohui Lin, Lusheng Wang +2
Given a vertex-weighted connected graph , the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree of such that the total we…
An approximation algorithm for the Bandpass-2 problem
Weitian Tong, Zhi-Zhong Chen, Lusheng Wang +4
The general Bandpass- problem is NP-hard and can be approximated by a reduction into the weighted -set packing problem, with a worst case performance ratio of . When…
Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles
Qiaojun Shu, Guohui Lin, Eiji Miyano
An acyclic edge coloring of a graph is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiam{Ä}ik (1978) and Alon,…
Approximation algorithms for maximally balanced connected graph partition
Yong Chen, Zhi-Zhong Chen, Guohui Lin +2
Given a simple connected graph , we seek to partition the vertex set into non-empty parts such that the subgraph induced by each part is connected, and the part…
Maximizing social welfare among EF1 allocations at the presence of two types of agents
Jiaxuan Ma, Yong Chen, Guangting Chen +3
We study the fair allocation of indivisible items to agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are o…
Approximation algorithms for non-sequential star packing problems
Mengyuan Hu, An Zhang, Yong Chen +2
For a positive integer , a -star (-star, -star, respectively) is a connected graph containing a degree- vertex and degree- vertices, where $\e…
Approximation algorithms for the vertex happiness
Yao Xu, Peng Zhang, Randy Goebel +1
We investigate the maximum happy vertices (MHV) problem and its complement, the minimum unhappy vertices (MUHV) problem. We first show that the MHV and MUHV problems are a special…
Pre-trained protein language model for codon optimization
Shashank Pathak, Guohui Lin
Motivation: Codon optimization of Open Reading Frame (ORF) sequences is essential for enhancing mRNA stability and expression in applications like mRNA vaccines, where codon choice…
On rescheduling due to machine disruption while to minimize the total weighted completion time
Wenchang Luo, Taibo Luo, Randy Goebel +1
We investigate a single machine rescheduling problem that arises from an unexpected machine unavailability, after the given set of jobs has already been scheduled to minimize the t…
Covering vertices by sequential stars
Mengyuan Hu, An Zhang, Yong Chen +5
We study the problem of covering the maximum number of vertices in a graph by a collection of vertex-disjoint stars, each with a number of satellites in a given interval $[k, \ell]…
Improved approximation algorithms for path vertex covers in regular graphs
An Zhang, Yong Chen, Zhi-Zhong Chen +1
Given a simple graph and a constant integer , the -path vertex cover problem ({\sc PVC}) asks for a minimum subset of vertices such that…