Browsing by Author "Lee, RCT"

Now showing 1 - 3 of 3

The approximability of the weighted Hamiltonian path completion problem on a tree
(2005-09-05)
Wu, Q
;
Lu, CL
;
Lee, RCT
;
生物科技學系
;
Department of Biological Science and Technology
Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem remains hard to approximate even when the given subgraph is a tree. Moreover, if the edge weights are restricted to be either 1 or 2, the Hamiltonian path completion problem on a tree is still NP-hard. Then it is observed that this problem is strongly NP-hard, so it does not have any fully polynomial-time approximation scheme (FPTAS) unless NP = P. When the given tree is a k-tree, we give an approximation algorithm with performance ratio 1.5. (c) 2005 Elsevier B.V. All rights reserved.
The full Steiner tree problem
(2003-09-05)
Lu, CL
;
Tang, CY
;
Lee, RCT
;
生物科技學系
;
Department of Biological Science and Technology
Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V, E) with a length function on E and a proper subset R subset of V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either I or 2. For the instances with lengths either I or 2, we give a 8/5-approximation algorithm to find an approximate solution for the problem. (C) 2003 Elsevier B.V. All rights reserved.
Two-machine flow-shop scheduling to minimize total late work
(2006-06-01)
Lin, BMT
;
Lin, FC
;
Lee, RCT
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This article considers a two-machine flow-shop scheduling problem of minimizing total late work. Unlike tardiness, which is based upon the difference between the job completion time and the due date, the late work of a job is defined as the amount of work not completed by its due date. This article first shows that the problem remains non-deterministic polynomial time (NP) hard even if all jobs share a common due date. A lower bound and a dominance property are developed to design branch-and-bound algorithms. Computational experiments are conducted to assess the performance of the proposed algorithms. Numerical results demonstrate that the lower bound and dominance rule can help to reduce the computational efforts required by exploring the enumeration tree. The average deviation between the solution found by tabu search and the proposed lower bound is less than 3%, suggesting that the proposed lower bound is close to the optimal solution.