3 citations · 14 across the 18 of their papers we have counts for
17 papers · 1 filter
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…
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…
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…
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 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…
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…
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…
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…
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…
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…
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…
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…
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 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…
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…
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…