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.

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.

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

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

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.