已为您找到该学者7条结果 成果回收站
【期刊论文】Note Minimizing makespan with release times on identical parallel batching machines
李国君, Shuguang Lia, *, Guojun Lib, c, , Shaoqiang Zhangd
Discrete Applied Mathematics 148(2005)127-134,-0001,():
-1年11月30日
We consider the problem of scheduling n jobs on m identical parallel batching machines. Each job is characterized by a release time and a processing time. Each machine can process up to B (B<n) jobs as a batch simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. The objective is to minimize the maximum completion time (makespan). We present a polynomial time approximation scheme (PTAS) for this problem.
Polynomial time approximation scheme, Identical parallel batching machines, Scheduling, Makespan
-
45浏览
-
0点赞
-
0收藏
-
0分享
-
88下载
-
0
-
引用
李国君, Shuguang Lia, *, Guojun Lib, c, , Xiaoli Wangb, Qiming Liud
Operations Research Letters 33(2005)157-164,-0001,():
-1年11月30日
We consider the problem of scheduling jobs with release times and non-identical job sizes on a single batching machine; our objective is to minimize makespan. We present an approximation algorithm with worst-case ratio 2+ε, where ε>0 can be made arbitrarily small
Approximation algorithms, Scheduling, Batch processing, Makespan, Release times
-
51浏览
-
0点赞
-
0收藏
-
0分享
-
83下载
-
0
-
引用
【期刊论文】Proof of Chvátal’s conjecture on maximal stable sets and maximal cliques in graphs
李国君, Xiaotie Deng, a, , Guojun Li, b, c, and Wenan Zangd
Journal of Combinatorial Theory, Series B 91(2004)301-325,-0001,():
-1年11月30日
Grillet established conditions on a partially ordered set under which each maximal antichain meets each maximal chain. Chvatal made a conjecture in terms of graphs that strengthens Grillet's theorem. The purpose of this paper is to prove this conjecture.
-
50浏览
-
0点赞
-
0收藏
-
0分享
-
71下载
-
0
-
引用
【期刊论文】GENETIC DESIGN OF DRUGS WITHOUT SIDE-EFFECTS∗
李国君, XIAOTIE DENG†, GUOJUN LI‡, ZIMAO LI§, BIN MA¶, AND LUSHENG WANG†
SIAM J. COMPUT. Vol. 32, No.4, pp. 1073-1090,-0001,():
-1年11月30日
Consider two sets of strings, B (bad genes) and G (good genes), as well as two integers db and dg (db ≤dg). A frequently occurring problem in computational biology (and other fields) is to find a (distinguishing) substring s of length L that distinguishes the bad strings from good strings, i.e., such that for each string si ∈ B there exists a length-L substring ti of si with d (s, ti) ≤db (close to bad strings), and for every substring ui of length L of every string gi ∈ G, d(s, ui)≥dg (far from good strings). We present a polynomial time approximation scheme to settle the problem; i.e., for any constant >0, the algorithm finds a string s of length L such that for every si ∈ B there is a length-L substring ti of si with d(ti, s)≤(1+)db, and for every substring ui of length L of every gi ∈ G, d (ui, s)≥(1−)dg if a solution to the original pair (db≤dg) exists. Since there is a polynomial number of such pairs (db, dg), we can exhaust all the possibilities in polynomial time to find a good approximation required by the corresponding application problems.
approximation algorithms,, computational molecular biology,, distinguishing substring selection
-
67浏览
-
0点赞
-
0收藏
-
0分享
-
55下载
-
0
-
引用
【期刊论文】A 2-approximation algorithm for path coloring on a restricted class of trees of rings
李国君, Xiaotie Deng, a, *, , Guojun Li, b, Wenan Zang, c, and Yi Zhou a
Journal of Algorithms 47(2003)1-13,-0001,():
-1年11月30日
A tree of rings is an undirected graph obtained from a tree by replacing each node of the tree with a cycle (called tree-node-cycle) and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common and no three tree-node-cycles share a same node. (A more general definition may allow them to share the same node.) Given a set of paths on a tree of rings, the path coloring problem is to color these paths with the smallest number of colors so that any two paths sharing an edge are assigned different colors. In
this paper,, we present a 2-approximation algorithm for this problem., Path coloring, Trees of rings, Approximation algorithms
-
66浏览
-
0点赞
-
0收藏
-
0分享
-
85下载
-
0
-
引用