Search

Your search keyword '"Liu, Longcheng"' showing total 448 results
Start Over Author "Liu, Longcheng"
448 results on '"Liu, Longcheng"'

30. A local search $4/3$-approximation algorithm for the minimum $3$-path partition problem

Author

Chen, Yong, Goebel, Randy, Lin, Guohui, Liu, Longcheng, Su, Bing, Tong, Weitian, Xu, Yao, and Zhang, An

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Given a graph $G = (V, E)$, the $3$-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most $3$ to cover all the vertices of $V$. It is different from but closely related to the well-known $3$-set cover problem. The best known approximation algorithm for the $3$-path partition problem was proposed recently and has a ratio $13/9$. Here we present a local search algorithm and show, by an amortized analysis, that it is a $4/3$-approximation. This ratio matches up to the best approximation ratio for the $3$-set cover problem., Comment: 16 pages, 21 figures

Published
2018

36. Approximation algorithms for the three-machine proportionate mixed shop scheduling

Author

Liu, Longcheng, Chen, Yong, Dong, Jianming, Goebel, Randy, Lin, Guohui, Luo, Yue, Ni, Guanqun, Su, Bing, and Zhang, An

Subjects
Computer Science - Data Structures and Algorithms
Abstract

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 schedule than flow-shops and open-shops, and have been studied since the 1980's. We consider the three machine proportionate mixed shop problem denoted as $M3 \mid prpt \mid C_{\max}$, in which each job has equal processing times on all three machines. Koulamas and Kyparisis [{\it European Journal of Operational Research}, 243:70--74,2015] showed that the problem is solvable in polynomial time in some very special cases; for the non-solvable case, they proposed a $5/3$-approximation algorithm. In this paper, we present an improved $4/3$-approximation algorithm and show that this ratio of $4/3$ is asymptotically tight; when the largest job is a flow-shop job, we present a fully polynomial-time approximation scheme (FPTAS). On the negative side, while the $F3 \mid prpt \mid C_{\max}$ problem is polynomial-time solvable, we show an interesting hardness result that adding one open-shop job to the job set makes the problem NP-hard if this open-shop job is larger than any flow-shop job. We are able to design an FPTAS for this special case too., Comment: An extended abstract containing a subset of results has been accepted by AAIM 2018. This is the full version with 20 pages, 14 figures

Published
2018

37. Approximation algorithms for two-machine flow-shop scheduling with a conflict graph

Author

Cai, Yinhui, Chen, Guangting, Chen, Yong, Goebel, Randy, Lin, Guohui, Liu, Longcheng, and Zhang, An

Subjects
Computer Science - Data Structures and Algorithms, F.2.2, G.2.1, G.4
Abstract

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 objective function is not the number of paths but the number of length-$0$ paths (that is, isolated vertices), turns out to be polynomial-time solvable. We further show that another variant, where the objective function is the total number of length-$0$ and length-$1$ paths, is also polynomial-time solvable. Both variants find applications in approximating the two-machine flow-shop scheduling problem in which job processing has constraints that are formulated as a conflict graph. For the unit jobs, we present a $4/3$-approximation algorithm for the scheduling problem with an arbitrary conflict graph, based on the exact algorithm for the variants of the path cover problem. For the arbitrary jobs while the conflict graph is the union of two disjoint cliques, that is, all the jobs can be partitioned into two groups such that the jobs in a group are pairwise conflicting, we present a simple $3/2$-approximation algorithm., Comment: 15 pages, 2 figures

Published
2018

46. A Local Search 4/3-approximation Algorithm for the Minimum 3-path Partition Problem

Author

Chen, Yong, Goebel, Randy, Lin, Guohui, Liu, Longcheng, Su, Bing, Tong, Weitian, Xu, Yao, Zhang, An, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Chen, Yijia, editor, Deng, Xiaotie, editor, and Lu, Mei, editor

Published
2019
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results