[ Conference Proceedings Publications | Edited Works | Others ]

Journal publications (Algorithms^left, Bioinformatics^right) organized in chronological order.
Preliminary versions and extended abstracts previously appearing in conference proceedings are listed under their respective journal versions.

				2025	2024	2023	2022	2021	2020
2010	2011	2012	2013	2014	2015	2016	2017	2018	2019
2009	2008	2007	2006	2005	2004	2003	2002	2001	2000
							1997	1998	1999

You may want to check my lists of publications through DBLP, MathSciNet, and PubMed.

Informal publications at arXiv:

4. Jianming Dong, Ruyan Jin, ——, Bing Su, Weitian Tong^*, and Yao Xu^*.
   An efficient polynomial-time approximation scheme for parallel multi-stage open shops.
   (2022) CoRR abs/2205.14407.
3. Yao Xu, Yong Chen, Taibo Luo, and ——^*.
   A local search 2.917-approximation algorithm for duo-preservation string mapping.
   (2017) CoRR abs/1702.01877.
   Note: Both the design and analysis of our 2.917-approximation was superseded by the work presented in CoRR abs/1702.02405.
2. Yao Xu, Peng Zhang, Randy Goebel, and ——^*.
   Approximation algorithms for the vertex happiness.
   (2017) CoRR abs/1606.03185.
   Note: It was pointed out by a reviewer that for the MUHV problem, one can contract vertices of the same color into only one vertex to reduce the problem to the Submodular Multiway Partition. The blackbox reduction thus gives a (2-2/k)-approximation.
1. Weitian Tong, Zhi-Zhong Chen, Lusheng Wang, Yinfeng Xu, Jiuping Xu, Randy Goebel, and ——^*.
   An approximation algorithm for the Bandpass-2 problem.
   (2013) CoRR abs/1307.7089.

146. 
     Qiaojun Shu and ——^*.
     Planar graphs are acyclically edge (Δ+5)-colorable.
     Journal of Combinatorial Optimization.
     Accepted on March 31, 2024.
145. Xianyu Yu, Hengte Du, Dequn Zhou, Qunwei Wang^*, and ——^*.
     Bi-objective carbon-efficient distributed flow-shop scheduling with multistep electricity pricing.
     International Journal of Production Research.
     Accepted on January 18, 2024.

      

     ---

     67. 
         Mingyang Gong, Jing Fan, ——^*, and Eiji Miyano.
         Approximation algorithms for covering vertices by long paths.
         In Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Vienna, Austria. LIPIcs 241, pages 53:1-53:14.
         Abstract: 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 least k vertices is considered long. When k ≤ 3, the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4, the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394k + O(1))-approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4. Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies.
     66. 
         Mingyang Gong, Zhi-Zhong Chen^*, ——, and Lusheng Wang.
         An approximation algorithm for covering vertices by 4⁺-paths.
         The 16th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2023). Honolulu, Hawaii, December 15-17, 2023. LNCS 14461, pages 459-470.
         Abstract: 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 vertices in these paths is maximized. The problem is NP-hard and admits an approximation algorithm which achieves a ratio of 2 and runs in O(|V|⁸) time. The known algorithm is based on time-consuming local search, and its authors ask whether one can design a better approximation algorithm by a completely different approach. In this paper, we answer their question in the affirmative by presenting a new approximation algorithm for the problem. Our algorithm achieves a ratio of 1.874 and runs in O(min{|E|²|V|², |V|⁵}) time. Unlike the previously best algorithm, ours starts with a maximum matching M of G and then tries to transform M into a solution by utilizing a maximum-weight path-cycle cover in a suitably constructed graph.

69. Hiroshi Eto, Shunsuke Kawaharada, ——, Eiji Miyano^*, and Tugce Ozdemir.
    Directed path partition problem on directed acyclic graphs.
    The 35th International Workshop on Combinatorial Algorithms (IWOCA 2024). Ischia, Italy, July 1-3, 2024.
    Accepted on April 15, 2024.
68. Yuichi Asahiro, Hiroshi Eto, Taku Kato, ——, and Eiji Miyano^*.
    Bounded-deletion maximum independent set problem on chordal bipartite graphs.
    The 15th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2024). Osaka, Japan, May 31-June 1, 2024.
    Accepted on April 8, 2024.
65. 
    Yuya Higashikawa, Naoki Katoh, ——, Eiji Miyano, Suguru Tamaki, Junichi Teruyama, and Binhai Zhu^*.
    On computing a center persistence diagram.
    The 24th International Symposium on Fundamentals of Computation Theory (FCT 2023). Trier, Germany, September 18-21, 2023. LNCS 14292, pages 262-275.

    ---

64. 
    Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, ——, Eiji Miyano^*, Hirotaka Ono, and Shunichi Tanaka.
    Approximation algorithms for longest run subsequence problems.
    The 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Marne-la-Vallée, France, June 26–28, 2023. LIPIcs 259, pages 2:1-2:12.
63. Yuichi Asahiro, Hiroshi Eto, Kana Korenaga, ——, Eiji Miyano^*, and Reo Nonoue.
    Independent set under a change constraint from an initial solution.
    In Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC 2023). Larnaca, Cyprus, June 13-16, 2023. LNCS 13898, pages 37-51.
62. Lin Chen, Minming Li, ——, and Kai Wang^*.
    Approximation of scheduling with calibrations on multiple machines.
    In Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019). Pages 237-239.
61. Weitian Tong, Randy Goebel, Wei Ding, and ——^*.
    An improved approximation algorithm for the Bandpass problem.
    In Proceedings of the Joint Conference of the Sixth International Frontiers of Algorithmics Workshop and the Eighth International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM 2012). LNCS 7285, Pages 351-358.
    Abstract: The general Bandpass-B problem is NP-hard and can be approximated by a reduction into the B-set packing problem, with a worst case performance ratio of O(B²). When B = 2, a maximum weight matching gives a 2-approximation to the problem. The Bandpass-2 problem, or simply the Bandpass problem, can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present in this paper a 36⁄19-approximation algorithm for the Bandpass problem, which is the first improvement over the simple maximum weight matching based 2-approximation algorithm.

144. Mingyang Gong, Zhi-Zhong Chen, and ——^*.
     Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time.
     Algorithmica. 86(2024), 1400-1427.
     Abstract: In offline scheduling models, jobs are given with their exact processing times. In their online counterparts, jobs arrive in sequence together with their processing times and the scheduler makes irrevocable decisions on how to execute each of them upon its arrival. We consider a semi-online variant which has equally rich application background, called scheduling with testing, where the exact processing time of a job is revealed only after a required testing operation is finished, or otherwise the job has to be executed for a given possibly over-estimated length of time. For multiprocessor scheduling with testing to minimize the total job completion time, we present several first approximation algorithms with constant competitive ratios for various settings, including a 2φ-competitive algorithm for the non-preemptive general testing case and a (0.0382 + 2.7925 (1 - 1/2m))-competitive randomized algorithm, when the number of machines m ≥ 37 or otherwise 2.7925-competitive, where φ = (1 + &sqrt;5) / 2 < 1.6181 is the golden ratio and m is the number of machines, a (3.5 - 3/2m)-competitive algorithm allowing job preemption when m ≥ 3 or otherwise 3-competitive, and a (φ + (φ + 1)(1 - 1/m)/2)-competitive algorithm for the non-preemptive uniform testing case when m ≥ 5 or otherwise (φ + 1)-competitive. Our results improve three previous best approximation algorithms for the single machine scheduling with testing problems, respectively.
143. Mingyang Gong, ——^*, Eiji Miyano, Bing Su, and Weitian Tong.
     A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops.
     Annals of Operations Research. 335(2024), 185-204.
     Abstract: We investigate the seemingly untouched yet the most general parallel identical k-stage flow-shops scheduling, in which we are given an arbitrary number of indistinguishable k-stage flow-shops and a set of jobs each to be processed on one of the flow-shops, and the goal is to schedule these jobs to the flow-shops so as to minimize the makespan. Here the number k of stages is a fixed constant, but the number of flow-shops is part of the input. This scheduling problem is strongly NP-hard. To the best of our knowledge all previously presented approximation algorithms are for the special case where k = 2, including a 17/6-approximation in 2017, a (2 + ε)-approximation in 2018, and the most recent polynomial-time approximation scheme in 2020; they all take advantage of the number of stages being two. We deal with an arbitrary constant k ≥ 3, where the k-stage flow-shop scheduling is already strongly NP-hard. To define a configuration that summarizes the key information about the job assignments in a feasible schedule, we present novel concepts of big job type, big job assignment pair type, and flow-shop type. We show that the total number of distinct configurations is a polynomial in the input number of flow-shops. We then present how to compute a schedule for each configuration that assigns all the big jobs, followed by how to allocate all the small jobs into the schedule at a cost only a fraction of the makespan. These together lead to a polynomial-time approximation scheme for the problem.
142. 
     Yong Chen, Zhi-Zhong Chen, Curtis Kennedy, ——^*, Yao Xu, and An Zhang.
     Approximating the directed path partition problems.
     Information and Computation. 297(2024), Article 105150 (19 pages).
     Abstract: Given a digraph G = (V, E), the k-path partition problem aims to find a minimum collection of vertex-disjoint directed paths, each of order at most k, to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation networks and others. Its special case on undirected graphs is NP-hard when k ≥ 3, and has received much study recently from the approximation algorithm perspective. However, the general problem on digraphs is seemingly untouched in the literature. We fill the gap with the first k⁄2-approximation algorithm, for any k ≥ 3, based on a novel concept of enlarging walk to minimize the number of singletons in the k-path partition. Secondly, for k = 3, we define a second novel kind of enlarging walks to greedily reduce the number of 2-paths in the 3-path partition and propose an improved 13⁄9-approximation algorithm. Lastly, for any k ≥ 7, we present an improved (k+2)⁄3-approximation algorithm built on the maximum path-cycle cover followed by a careful 2-cycle elimination process.
     59. Yong Chen, Zhi-Zhong Chen, Curtis Kennedy, ——^*, Yao Xu, and An Zhang.
         Approximation algorithms for the directed path partition problems.
         In Proceedings of the 15th International Workshop on Frontiers of Algorithmics (IJTCS-FAW 2021). Beijing, China. LNCS 12874, pages 23-36.

141. 
     Yuichi Asahiro, Jesper Jansson, ——, Eiji Miyano^*, Hirotaka Ono, and Tadatoshi Utashima.
     Polynomial-time equivalences and refined algorithms for longest common subsequence variants.
     Discrete Applied Mathematics. 353(2024), 44-64.
     60. Yuichi Asahiro, Jesper Jansson, ——, Eiji Miyano^*, Hirotaka Ono, and Tadatoshi Utashima.
         Polynomial-time equivalences and refined algorithms for longest common subsequence variants.
         In Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Prague, Czech Republic. LIPIcs 223, pages 15:1-15:17.

140. Kenya Kobayashi, ——, Eiji Miyano^*, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, and Tsuyoshi Yagita.
     Path cover problems with length cost.
     Algorithmica (SI for WALCOM 2022). 85(2023), 3348-3375.
     58. Kenya Kobayashi, ——, Eiji Miyano^*, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, and Tsuyoshi Yagita.
         Path cover problems with length cost.
         In Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022). Jember, Indonesia. LNCS 13174, pages 396-408.
139. Yuichi Asahiro^*, Hiroshi Eto, Tesshu Hanaka, ——, Eiji Miyano, and Ippei Terabaru.
     Corrigendum to "Complexity and approximability of the happy set problem" [Theoret. Comput. Sci. 866(2021) 123-144].
     Theoretical Computer Science. 975(2023), Article 114114 (7 pages).

138. Yunong Li, Hao Li, Taibo Luo, ——, and Liang Li^*.
     Intensity-dependent mass search for improving metabolite database matches in chemical isotope labeling LC-QTOF-MS-based metabolomics.
     Analytica Chimica Acta. 1272(2023), Article 341467 (9 pages).
137. 
     Nazmus Sakeef, Sabine Scandola, Curtis Kennedy, Christina Lummer, Jiameng Chang, R. Glen Uhrig^*, and ——^*.
     Machine learning classification of plant genotypes grown under different light conditions through the integration of multi-scale time-series data.
     Computational and Structural Biotechnology Journal. 21(2023), 3183-3195.

136. 
     Yong Chen, Randy Goebel, ——^*, Longcheng Liu, Bing Su^*, Weitian Tong, Yao Xu, and An Zhang.
     A local search 4/3-approximation algorithm for the minimum 3-path partition problem.
     Journal of Combinatorial Optimization. 44(2022), 3595-3610.
     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.
     57. Yong Chen, Randy Goebel, ——^*, Longcheng Liu, Bing Su, Weitian Tong, Yao Xu^*, and An Zhang.
         A local search 4/3-approximation algorithm for the minimum 3-path partition problem.
         In Proceedings of the 13th International Frontiers of Algorithmics Workshop (FAW 2019).
         LNCS 11458, pages 14-25.
135. Guangting Chen, Yong Chen, Zhi-Zhong Chen, ——^*, Tian Liu, and An Zhang.
     Approximation algorithms for the maximally balanced connected tripartition problem.
     Journal of Combinatorial Optimization. 44(2022), 1753-1773.
134. Bing Su, Wyatt Carlson, Jiabin Fan, Arthur Gao, Yanjun Shao, and ——^*.
     Sharing bicycle re-locating with minimum carbon emission.
     Operations Research Transactions. 26(3)(2022), 75-91.
133. An Zhang, Yong Chen, Guangting Chen, Zhanwen Chen, Qiaojun Shu, and ——^*.
     Maximum matching based approximation algorithms for precedence constrained open-shop and flow-shop scheduling.
     Operations Research Transactions. 26(3)(2022), 57-74.
132. Mingyang Gong, Randy Goebel, ——^*, and Eiji Miyano.
     Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing.
     Journal of Combinatorial Optimization (SI for FAW 2021). 44(2022), 877-893.
     56. Mingyang Gong and ——^*.
         Improved approximation algorithms for multiprocessor scheduling with testing.
         In Proceedings of the 15th International Workshop on Frontiers of Algorithmics (IJTCS-FAW 2021). Beijing, China. LNCS 12874, pages 65-77.
131. Wenchang Luo, Rylan Chin, Alexander Cai, ——^*, Bing Su^*, and An Zhang.
     A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling.
     Journal of Combinatorial Optimization. 44(2022), 690-722.
130. 
     Yong Chen^†, Yinhui Cai^†, Longcheng Liu^†, Guangting Chen, Randy Goebel, ——^*, Bing Su^*, and An Zhang.
     Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph.
     Journal of Combinatorial Optimization. 43(2022), 571-588.
     55. Yinhui Cai^†, Guangting Chen, Yong Chen^*, Randy Goebel, ——^*, Longcheng Liu^†, and An Zhang.
         Approximation algorithms for two-machine flow-shop scheduling with a conflict graph.
         In Proceedings of the 24th International Computing and Combinatorics Conference (COCOON 2018). LNCS 10976, pages 205-217.

129. 
     Yong Chen, Zhi-Zhong Chen, ——^*, Yao Xu, and An Zhang.
     Approximation algorithms for maximally balanced connected graph partition.
     Algorithmica. 83(2021), 3715-3740.
     Abstract: Given a connected graph G = (V, E), we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k ≥ 4, no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k ≥ 3. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems.
     54. Yong Chen, Zhi-Zhong Chen, ——^*, Yao Xu, and An Zhang.
         Approximation algorithms for maximally balanced connected graph partition.
         In Proceedings of the 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019). LNCS 11949, pages 130-141.
128. 
     Qiaojun Shu, Yong Chen, Shuguang Han, ——^*, Eiji Miyano, and An Zhang.
     Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles.
     Theoretical Computer Science (SI for TAMC 2020). 882(2021), 77-108.
     53. Qiaojun Shu, Yong Chen, Shuguang Han, ——^*, Eiji Miyano, and An Zhang.
         Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles.
         In Proceedings of the 16th International Conference on Theory and Applications of Models of Computation (TAMC 2020). Changsha, China. LNCS 12337, pages 426-438.
127. Jianming Dong, Randy Goebel, Jueliang Hu, ——^*, and Bing Su^*.
     Minimizing total job completion time in MapReduce scheduling.
     Computers & Industrial Engineering. 158(2021), Article 107387.
     Abstract: We follow up an earlier studied multiple-task parallel-machine scheduling model that captures the core challenges in MapReduce scheduling, with the optimization goal to minimize the total job completion time. The problem is a novel generalization of the classic two-stage flow-shop scheduling, in which we are given a set of jobs each is associated with multiple map tasks and multiple reduce tasks. All these tasks are non-preemptive to be processed on multiple parallel identical map machines and multiple parallel identical reduce machines, respectively, under the strict precedence constraints that, for each job, any reduce task cannot start before all its map tasks have been finished. We prove a new lower bound on the total job completion time, and based on which we present an O(n log n + N + m₁ + m₂)-time (9 - 3⁄ m₁)-approximation algorithm, where n and N are the number of jobs and the total number of tasks, respectively, m₁ and m₂ are the numbers of map and reduce machines, respectively, and they can even be part of the input. Our algorithm improves the previous best 12-approximation, and it reduces to the best approximation algorithms for several interesting or well studied special cases. We confirm through numerical experiments on 828,100 instances that both our lower bound and our algorithm significantly outperform: the empirical mean improvement ratio of the new lower bound is as high as 37.75%, and the empirical mean approximation ratio of our algorithm is only 1.7582.
126. Xing Wang, Guangting Chen, Yong Chen, ——^*, Yonghao Wang, and An Zhang^*.
     Improved hardness and approximation results for single allocation hub location.
     Theoretical Computer Science (SI for AAIM 2020). 864(2021), 10-19.
     52. Xing Wang, Guangting Chen, Yong Chen, ——^*, Yonghao Wang, and An Zhang^*.
         Improved hardness and approximation results for single allocation hub location.
         In Proceedings of the 14th International Conference on Algorithmic Aspects in Information and Management (AAIM 2020). Jinhua, China. LNCS 12290, pages 85-96.
125. Yong Chen, Zhi-Zhong Chen^*, ——^*, Lusheng Wang, and An Zhang.
     A randomized approximation algorithm for metric triangle packing.
     Journal of Combinatorial Optimization (SI for COCOA 2019). 41(2021), 12-27.
     51. Yong Chen, Zhi-Zhong Chen^*, ——^*, Lusheng Wang, and An Zhang.
         A randomized approximation algorithm for metric triangle packing.
         In Proceedings of the 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019). Xiamen, China. LNCS 11949, pages 119-129.

124. ——^* and Weitian Tong.
     An improved approximation algorithm for the minimum common integer partition problem.
     Information and Computation. 281(2021), Article 104784 (13 pages).
     Abstract: Given a collection of multisets {X₁, X₂, ..., X_k} (k ≥ 2) of positive integers, a multiset S is a common integer partition for them if S is an integer partition of every multiset X_i, 1 ≤ i ≤ k. The minimum common integer partition (k-MCIP) problem is defined as to find a CIP for {X₁, X₂, ..., X_k} with the minimum cardinality. We present a 6⁄5-approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of performance ratio 5⁄4 designed by Chen et al. in 2006. We then extend it to obtain an absolute 0.6k-approximation algorithm for k-MCIP when k is even (when k is odd, the approximation ratio is 0.6k+0.4).
     50. Weitian Tong and ——^*.
         An improved approximation algorithm for the minimum common integer partition problem.
         In Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014). LNCS 8889, Pages 353-364.
123. Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, ——, Eiji Miyano^*, and Ippei Terabaru.
     Parameterized algorithms for the happy set problem.
     Discrete Applied Mathematics. 304(2021), 32-44.
     49. Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, ——, Eiji Miyano^*, and Ippei Terabaru.
         Algorithms and hardness results for the happy set problem.
         (Short Abstract) In Proceedings of the 14th International Conference on Algorithms and Computation (WALCOM 2020). LNCS 12049, pages 323-328.
122. Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, ——, Eiji Miyano^*, and Ippei Terabaru.
     Complexity and approximability of the happy set problem.
     Theoretical Computer Science (SI for COCOON 2020). 866(2021), 123-144.
     48. Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, ——, Eiji Miyano^*, and Ippei Terabaru.
         Graph classes and approximability of the happy set problem.
         (Extended Abstract) In Proceedings of the 26th International Conference on Computing and Combinatorics (COCOON 2020). Atlanta, GA, USA. LNCS 12273, pages 335-346.

121. Jianming Dong, Joshua Chang, Bing Su, Jueliang Hu, and ——^*.
     Two-stage openshop scheduling with a two-machine flowshop as a stage: approximation algorithms and empirical experiments.
     Journal of Scheduling. 23(2020), 595-608.
120. 
     An Zhang, Yong Chen, Zhi-Zhong Chen, and ——^*.
     Improved approximation algorithms for path vertex covers in regular graphs.
     Algorithmica. 82(2020), 3041-3064.
119. Wenchang Luo, Miaomiao Jin, Bing Su^*, and ——^*.
     An approximation scheme for rejection-allowed single-machine rescheduling.
     Computers & Industrial Engineering. 146(2020), Article 106574.
118. Yong Chen, Randy Goebel, and ——^*, Bing Su, and An Zhang.
     Open-shop scheduling for unit jobs under precedence constraints.
     Theoretical Computer Science (SI for COCOA 2018). 803(2020), 144-151.
     Abstract: We study open-shop scheduling for unit jobs under precedence constraints, where if one job precedes another job then it has to be finished before the other job can start to be processed. For the three-machine open-shop to minimize the makespan, we first present a simple 5/3-approximation based on a partition of the job set into agreeable layers using the natural layered representation of the precedence graph. We then show a greedy algorithm to reduce the number of singleton-job layers, resulting in an improved partition, which leads to a 4/3-approximation. Both approximation algorithms apply to the general m-machine open-shops too.
     47. An Zhang, Yong Chen, Randy Goebel, and ——^*.
         Open-shop scheduling for unit jobs under precedence constraints.
         In Proceedings of the 12th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2018). LNCS 11346, pages 329-340.
117. 
     Longcheng Liu, Yong Chen, Jianming Dong, Randy Goebel, ——^*, Yue Luo, Guanqun Ni, Bing Su, Yao Xu, and An Zhang.
     Approximation algorithms for the three-machine proportionate mixed-shop scheduling.
     Theoretical Computer Science (SI for AAIM 2018). 803(2020), 57-70.
     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 | prpt | C_max, in which each job has equal processing times on all three machines. Koulamas and Kyparisis [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 | prpt | 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.
     46. Longcheng Liu, Guanqun Ni, Yong Chen, Randy Goebel, Yue Luo, An Zhang, and ——^*.
         Approximation algorithms and a hardness result for the three-machine proportionate mixed-shop problem.
         In Proceedings of the 12th International Conference on Algorithmic Aspects in Information and Management (AAIM 2018). LNCS 11343, pages 268-280.

116. 
     Yong Chen, ——^*, Tian Liu, Taibo Luo, Bing Su, Yao Xu, and P. Zhang.
     A (1.4 + ε)-approximation algorithm for the 2-Max-Duo problem.
     Journal of Combinatorial Optimization. 40(3)(2020), 806-824.
     45. Yao Xu, Yong Chen, ——^*, Tian Liu, Taibo Luo, and Peng Zhang^*.
         A (1.4 + ε)-approximation algorithm for the 2-Max-Duo problem.
         In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017). LIPIcs 92, pages 66:1-66:12.
115. Yuichi Asahiro, Jesper Jansson, ——, Eiji Miyano^*, Hirotaka Ono, and Tadatoshi Utashima.
     Exact algorithms for the bounded repetition longest common subsequence problem.
     Theoretical Computer Science (SI for COCOA 2019). 838(2020), 238-249.
     44. Yuichi Asahiro, Jesper Jansson, ——, Eiji Miyano^*, Hirotaka Ono, and Tadatoshi Utashima.
         Exact algorithms for the bounded repetition longest common subsequence problem.
         In Proceedings of the 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019). LNCS 11949, pages 1-12.

114. 
     Wenchang Luo, Yao Xu, Weitian Tong, and ——^*.
     Single machine scheduling with job-dependent machine deterioration.
     Journal of Scheduling. 22(6)(2019), 691-707.
     Abstract: 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 level, and a set of jobs each with a non-preemptive processing time and a machine deterioration. Such a machine deterioration quantifies the decrement in the machine maintenance level after processing the job. To avoid a machine breakdown, one should guarantee a non-negative maintenance level at any time point; and whenever necessary, a maintenance activity must be allocated for restoring the machine maintenance level. The goal of the problem is to schedule the jobs and the maintenance activities such that the total completion time of jobs is minimized. There are two variants of maintenance activities: in the partial maintenance case each activity can be allocated to increase the machine maintenance level to any level not exceeding the maximum; in the full maintenance case every activity must be allocated to increase the machine maintenance level to the maximum. In a recent work, the problem in the full maintenance case has been proven NP-hard; several special cases of the problem in the partial maintenance case were shown to be solvable in polynomial time, but the complexity of the general problem is left open. In this paper we first prove that the problem in the partial maintenance case is binary NP-hard, thus settling the open problem; we then design a 2-approximation algorithm and a branch-and-bound exact search algorithm. Computational experiments have been conducted for the two algorithms to examine their practical performance.
     43. Wenchang Luo, Yao Xu, Weitian Tong, and ——^*.
         Single machine scheduling with job-dependent machine deterioration.
         In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016). LIPIcs 64, pages 55:1-55:13.
113. 
     Zhi-Zhong Chen^*, ——^*, Lusheng Wang, Yong Chen, and Dan Wang.
     Approximation algorithms for the maximum weight internal spanning tree problem.
     Algorithmica. 81(11-12)(2019), 4167-4199.
     Abstract: Given a vertex-weighted connected graph G = (V, E), the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of the internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio 13/17. The currently best approximation algorithm for MwIST only has a performance ratio 1/3 - ε, for any ε > 0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to claw-free graphs, a special case been previously studied, we design a 7/12-approximation algorithm.
     42. Z.-Z. Chen^*, ——^*, L. Wang, Y. Chen, and D. Wang.
         Approximation algorithms for the maximum weight internal spanning tree problem.
         In Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017). LNCS 10392, pages 124-136.
112. Yuichi Asahiro, ——, Zhilong Liu, and Eiji Miyano^*.
     An approximation algorithm for the maximum induced matching problem on C₅-free regular graphs.
     IEICE Transactions. E102-A(9)(2019), 1142-1149.
     41. Yuichi Asahiro, ——, Zhilong Liu, and Eiji Miyano^*.
         An approximation algorithm for the maximum induced matching problem on C₅-free regular graphs.
         Presented in The 12th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC 2019).
111. Yong Chen, Randy Goebel, ——^*, Bing Su, Yao Xu, and An Zhang.
     An improved approximation algorithm for the minimum 3-path partition problem.
     Journal of Combinatorial Optimization. 38(1)(2019), 150-164.
110. Jianming Dong, Ruyan Jin, Jueliang Hu, and ——^*.
     A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops.
     Journal of Combinatorial Optimization. 37(2)(2019), 668-648.
109. Huili Zhang^*, Weitian Tong, ——, and Yinfeng Xu.
     Online minimum latency problem with edge uncertainty.
     European Journal of Operational Research. 273(2)(2019), 418-429.

108. Shanshan Zhai, Peng Zhang, Daming Zhu, Weitian Tong, Yao Xu, and ——^*.
     An approximation algorithm for genome sorting by reversals to preserve all adjacencies.
     Journal of Combinatorial Optimization. 37(4)(2019), 1170-1190.

107. 
     Wenchang Luo, Taibo Luo, Randy Goebel, and ——^*.
     Rescheduling due to machine disruption to minimize the total weighted completion time.
     Journal of Scheduling. 21(5)(2018), 565-578.
     Abstract: 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 total weighted completion time. Such a disruption is represented as an unavailable time interval and is revealed to the production planner before any job is processed; the production planner wishes to reschedule the jobs to minimize the alteration to the originally planned schedule, which is measured as the maximum time deviation between the original and the new schedules for all the jobs. The objective function in this rescheduling problem is to minimize the sum of the total weighted completion time and the weighted maximum time deviation, under the constraint that the maximum time deviation is bounded above by a given value. That is, the maximum time deviation is taken both as a constraint and as part of the objective function. We present a pseudo-polynomial time exact algorithm and a fully polynomial time approximation scheme.
106. Wenchang Luo, Yao Xu, Boyuan Gu, Weitian Tong, Randy Goebel, and ——^*.
     Algorithms for communication scheduling in data gathering network with data compression.
     Algorithmica. 80(11)(2018), 3158-3176.
105. Wenchang Luo, Boyuan Gu, and ——^*.
     Communication scheduling in data gathering networks of heterogeneous sensors with data compression: algorithms and empirical experiments.
     European Journal of Operational Research. 271(2)(2018), 462-473.
104. Weitian Tong, Eiji Miyano, Randy Goebel, and ——^*.
     An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops.
     Theoretical Computer Science. 734(SI on FAW 2016)(2018), 24-31.
     40. W. Tong, E. Miyano, R. Goebel, and ——^*.
         A PTAS for multiple parallel identical multi-stage flowshops to minimize the makespan.
         In Proceedings of the 10th International Frontiers of Algorithmics Workshop (FAW 2016). LNCS 9711, pages 227-237.
103. Jianming Dong, Xueshi Wang, Jueliang Hu, and ——^*.
     Single machine scheduling with job delivery to multiple customers.
     Journal of Scheduling. 21(3)(2018), 337-348.
102. Peng Zhang, Yao Xu, Tao Jiang, Angsheng Li, ——^*, and Eiji Miyano.
     Improved approximation algorithms for the maximum happy vertices and edges problems.
     Algorithmica. 80(5)(2018), 1412-1438.

101. J. Dong, J. Hu, M. Y. Kovalyov, ——^*, T. Luo, W. Tong, X. Wang, and Y. Xu.
     Corrigendum to "An FPTAS for the parallel two-stage flowshop problem. Theoretical Computer Science, 657: 64-72 (2017)".
     Theoretical Computer Science. 687(2017), 93-94.
100. J. Dong^†, W. Tong^†, T. Luo^†, X. Wang, J. Hu, Y. Xu, and ——^*.
     An FPTAS for the parallel two-machine flowshop problem.
     Theoretical Computer Science. 657(Part A)(2017), 64-72.

99. J. Hu^†, T. Luo^†, X. Su, J. Dong, W. Tong, R. Goebel, Y. Xu, and ——^*.
    Machine scheduling with a maintenance interval and job delivery coordination.
    Optimization Letters. 10(8)(2016), 1645-1656.
    39. J. Hu^†, T. Luo^†, X. Su, J. Dong, W. Tong, R. Goebel, Y. Xu, and ——^*.
        Machine scheduling with a maintenance interval and job delivery coordination.
        In Proceedings of the Ninth International Frontiers of Algorithmics Workshop (FAW 2015). LNCS 9130, Pages 104-114.
98. J. Dong, X. Wang, J. Hu, and ——^*.
    An improved two-machine flowshop scheduling with intermediate transportation.
    Journal of Combinatorial Optimization. 31(3)(2016), 1316-1334.
97. H. Zhang, W. Tong, Y. Xu, and ——^*.
    The Steiner traveling salesman problem with online advanced edge blockages.
    Computers and Operations Research. 70(2016), 26-38.
96. J. Dong, J. Hu, and ——^*.
    A note on the algorithm LPT-FF for a flowshop scheduling with two batch-processing machines.
    Optimization Letters. 10(1)(2016), 109-118.
95. W. Tong, R. Goebel, and ——^*.
    On the smoothed heights of Trie and Patricia index trees.
    Theoretical Computer Science. 609(Part 3: SI on COCOON 2014)(2016), 620-626.
    38. W. Tong, R. Goebel, and ——^*.
        On the smoothed heights of Trie and Patricia index trees.
        In Proceedings of the 20th International Computing and Combinatorics Conference (COCOON 2014). LNCS 8591, Pages 94-103.

94. 
    
    Y. Wang, ——, C. Li^*, and P. Stothard^*.
    Genotype imputation methods and their effects on genomic predictions in cattle.
    Springer Science Reviews. 4(2)(2016), 79-98.
93. 
    
    Y. Wu, F. Streijger, Y. Wang, ——, S. Christie, J.-M. Mac-Thiong, S. Parent, C. Bailey, S. Paquette, M. Boyd, T. Ailon, J. T. Street, C. Fisher, M. Dvorak, B. Kwon^*, and L. Li^*.
    Parallel metabolomic profiling of cerebrospinal fluid and serum for identifying biomarkers of injury severity after acute human spinal cord injury.
    Scientific Reports. 6(2016), Article 38718.
    Abstract: Suffering an acute spinal cord injury (SCI) can result in catastrophic physical and emotional loss. Efforts to translate novel therapies in acute clinical trials are impeded by the SCI community's singular dependence upon functional outcome measures. Therefore, a compelling rationale exists to establish neurochemical biomarkers for the objective classification of injury severity. In this study, CSF and serum samples were obtained at 3 time points (~24, 48, and 72 hours post-injury) from 30 acute SCI patients (10 AIS A, 12 AIS B, and 8 AIS C). A differential chemical isotope labeling liquid chromatography mass spectrometry (CIL LC-MS) with a universal metabolome standard (UMS) was applied to the metabolomic profiling of these samples. This method provided enhanced detection of the amine- and phenol-containing submetabolome. Metabolic pathway analysis revealed dysregulations in arginine-proline metabolism following SCI. Six CSF metabolites were identified as potential biomarkers of baseline injury severity, and good classification performance (AUC > 0.869)s was achieved by using combinations of these metabolites in pair-wise comparisons of AIS A, B and C patients. Using the UMS strategy, the current data set can be expanded to a larger cohort for biomarker validation, as well as discovering biomarkers for predicting neurologic outcome.

92. 
    I. Kanj, ——, T. Liu, W. Tong, G. Xia, J. Xu, B. Yang, F. Zhang, P. Zhang^*, and B. Zhu.
    Improved parameterized and exact algorithms for cut problems on trees.
    Theoretical Computer Science. 607(Part 3: SI on COCOA 2014)(2015), 455-470.
    37. I. Kanj, ——, T. Liu, W. Tong, G. Xia^*, J. Xu, B. Yang, F. Zhang, P. Zhang, and B. Zhu.
        Algorithms for cut problems on trees.
        In Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2014). LNCS 8881, Pages 283-298.
91. F. Y. L. Chin, B. Fu, J. Guo, S. Han, J. Hu, M. Jiang, ——, H.-F. Ting, L. Zhang, Y. Zhang^*, and D. Zhou.
    Competitive algorithms for unbounded one-way trading.
    Theoretical Computer Science. 607(Part 1: SI on AAIM 2014)(2015), 35-48.
90. L. Huang, W. Tong, R. Goebel, T. Liu, and ——^*.
    A 0.5358-approximation for Bandpass-2.
    Journal of Combinatorial Optimization. 30(2015), 612-626.
89. H. Zhang, W. Tong, Y. Xu, and ——^*.
    The Steiner traveling salesman problem with online edge blockages.
    European Journal of Operational Research. 243(2015), 30-40.
    Abstract: We consider the online Steiner Traveling Salesman Problem. In this problem, we are given an edge-weighted graph G = (V, E) and a subset D ⊆ V of destination vertices, with the optimization goal to find a minimum weight closed tour that traverses every destination vertex of D at least once. During the traversal, the salesman could encounter at most k non-recoverable blocked edges. The edge blockages are real-time, meaning that the salesman knows about a blocked edge whenever it occurs. We first show a lower bound on the competitive ratio and present an online optimal algorithm for the problem. While this optimal algorithm has non-polynomial running time, we present another online polynomial-time near optimal algorithm for the problem. Experimental results show that our online polynomial-time algorithm produces solutions very close to the offline optimal solutions.

88. 
    
    T. Huan^†, C. Tang^†, R. Li, Y. Shi, ——, and L. Li^*.
    MyCompoundID MS/MS search: metabolite identification using a library of predicted fragment-ion-spectra of 383,830 possible human metabolites.
    Analytical Chemistry. 87(20)(2015), 10619-10626.
    Abstract: We report an analytical tool to facilitate metabolite identification based on an MS/MS spectral match of an unknown to a library of predicted MS/MS spectra of possible human metabolites. To construct the spectral library, the known endogenous human metabolites in the Human Metabolome Database (HMDB) (8,021 metabolites) and their predicted metabolic products via one metabolic reaction in the Evidence-based Metabolome Library (EML) (375,809 predicted metabolites) were subjected to in silico fragmentation to produce the predicted MS/MS spectra. This spectral library is hosted at the public MCID Web site (www.MyCompoundID.org), and a spectral search program, MCID MS/MS, has been developed to allow a user to search one or a batch of experimental MS/MS spectra against the library spectra for possible match(s). Using MS/MS spectra generated from standard metabolites and a human urine sample, we demonstrate that this tool is very useful for putative metabolite identification. It allows a user to narrow down many possible structures initially found by using an accurate mass search of an unknown metabolite to only one or a few candidates, thereby saving time and effort in selecting or synthesizing metabolite standard(s) for eventual positive metabolite identification.
87. 
    
    Y. Wang, T. Wylie, P. Stothard, and ——^*.
    Whole genome SNP genotype piecemeal imputation.
    BMC Bioinformatics. 16(2015), Article 340.
86. 
    T. Huan, Y. Wu, C. Tang, ——, and L. Li^*.
    DnsID in MyCompoundID for rapid identification of Dansylated Amine- and Phenol-containing metabolites in LC-MS-based metabolomics.
    Analytical Chemistry. 87(19)(2015), 9838-9845.
85. 
    H. Jiang, ——, W. Tong, D. Zhu, and B. Zhu^*.
    Isomorphism and similarity for 2-generation pedigrees.
    BMC Bioinformatics. 16(Suppl 5: SI for ISBRA'14)(2015), Article S7.
    36. H. Jiang, ——, W. Tong, B. Zhu^*, and D. Zhu.
        Isomorphism and similarity for 2-generation pedigrees.
        In Proceedings of the 10th International Symposium on Bioinformatics Research and Applications (ISBRA 2014). LNCS/LNBI 8492, Page 396.

84. W. Tong, R. Goebel, T. Liu, and ——^*.
    Approximating the maximum multiple RNA interaction problem.
    Theoretical Computer Science. 556(SI on COCOA 2013)(2014), 63-70.
    35. W. Tong, R. Goebel, T. Liu, and ——^*.
        Approximation algorithms for the maximum multiple RNA interaction problem.
        In Proceedings of the 7th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2013). LNCS 8287, Pages 49-59.
83. 
    W. Tong, R. Goebel, and ——^*.
    Approximating the minimum independent dominating set in perturbed graphs.
    Theoretical Computer Science. 554(SI on COCOON 2013)(2014), 275-282.
    34. W. Tong, R. Goebel, and ——^*.
        Approximating the minimum independent dominating set in perturbed graphs.
        In Proceedings of the 19th Annual International Computing and Combinatorics Conference (COCOON 2013). LNCS 7936, Pages 257-267.
82. Z. Chen, B. Fu, R. Goebel, ——, W. Tong, J. Xu, B. Yang, Z. Zhao, and B. Zhu^*.
    On the approximability of the exemplar adjacency number problem for genomes with gene repetitions.
    Theoretical Computer Science. 550(2014), 59-65.

81. 
    Y. Tang, R. Li, ——, and L. Li^*.
    PEP search in MyCompoundID: detection and identification of dipeptides and tripeptides using dimethyl labeling and hydrophilic interaction liquid chromatography tandem mass spectrometry.
    Analytical Chemistry. 86(7)(2014), 3568-3574.
    Abstract: Small peptides, such as dipeptides and tripeptides, are naturally present in many biological samples (e.g., human biofluids and cell extracts). They have attracted great attention in many research fields because of their important biological functions as well as potential roles as disease biomarkers. Tandem mass spectrometry (MS/MS) can be used to profile these small peptides. However, the type and number of fragment ions generated in MS/MS are often limited for unambiguous identification. Herein we report a novel database-search strategy based on the use of MS/MS spectra of both unlabeled and dimethyl labeled peptides to identify and confirm amino acid sequences of di/tripeptides that are separated using hydrophilic interaction (HILIC) liquid chromatography (LC). To facilitate the di/tripeptide identification, a database consisting of all the predicted MS/MS spectra from 400 dipeptides and 8,000 tripeptides was created and a search tool, PEP Search, was developed and housed at the MyCompoundID website (www.mycompoundid.org/PEP). To evaluate the identification specificity of this method, we used acid hydrolysis to degrade a standard protein, cytochrome c, to produce many di/tripeptides with known sequences for LC-MS/MS. The resultant MS/MS spectra were searched against the database to generate a list of matches which were compared to the known sequences. We correctly identified all the di/tripeptides produced from the protein hydrolysate. We then applied this method to detect and identify di/tripeptides naturally present in human urine samples with confidence. We envisage the use of this method as a complementary tool to various LC-MS techniques currently available for small molecule or metabolome profiling with an added benefit of covering all di/tripeptide chemical space.

80. 
    H. Sabaa, Z. Cai, Y. Wang, R. Goebel, S. Moore, and ——^*.
    Whole genome identity-by-descent determination.
    Journal of Bioinformatics and Computational Biology. 11(2)(2013), Article 1350002.
79. 
    L. Li^*, R. Li, J. Zhou, A. Zuniga, A. E. Lewis-Stanislaus, Y. Wu, T. Huan, J. Zheng, Y. Shi, D. S. Wishart, and ——.
    MyCompoundID: Using an evidence-based metabolome library for metabolite identification.
    Analytical Chemistry. 85(6)(2013), 3401-3408.
    Abstract: Identification of unknown metabolites is a major challenge in metabolomics. Without the identities of the metabolites, the metabolome data generated from a biological sample cannot be readily linked with the proteomic and genomic information for studies in systems biology and medicine. We have developed a web-based metabolite identification tool that allows searching and interpreting mass spectrometry (MS) data against a newly constructed metabolome library composed of 8,021 known human endogenous metabolites and their predicted metabolic products (375,809 compounds from one metabolic reaction and 10,583,901 from two reactions). As an example, in the analysis of a simple extract of human urine or plasma and the whole human urine by liquid chromatography-mass spectrometry and MS/MS, we are able to identify at least two times more metabolites in these samples than by using a standard human metabolome library. In addition, it is shown that the evidence-based metabolome library (EML) provides a much superior performance in identifying putative metabolites from a human urine sample, compared to the use of the ChemPub and KEGG libraries.

78. 
    H. Jiang, Z. Li, ——, L. Wang, and B. Zhu^*.
    Exact and approximation algorithms for the complementary maximum strip recovery problem.
    Journal of Combinatorial Optimization. 23(4)(2012), 493-506.
77. ——^*, R. Goebel, Z. Li, and L. Wang.
    An improved approximation algorithm for the complementary maximum strip recovery problem.
    Journal of Computer and System Sciences. 78(3)(2012), 720-730.
    Abstract: Given two genomic maps G₁ and G₂ each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G₁ and G₂ such that the resultant subsequences, denoted as G₁^* and G₂^*, can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The complementary maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown to be NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved 7⁄3-approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a local amortization with a re-weighting scheme.
    (An extended abstract appears in FAW-AAIM 2011, LNCS 6681, pages 46-57.)
    33. Z. Li, R. Goebel, L. Wang, and ——^*.
        An improved approximation algorithm for the complementary maximum strip recovery problem.
        In Proceedings of the Joint Conference of the Fifth International Frontiers of Algorithmics Workshop and the Seventh International Conference on Algorithmic Aspects of Information and Management (FAW-AIMM 2011). LNCS 6681, Pages 46-57.

76. Y. Shi^*, B. Yuan, ——, and D. Schuurmans.
    Protein phosphorylation site prediction via feature discovery support vector machine.
    Tsinghua Science & Technology. 17(6; SI on Bioinformatics and Computational Biology)(2012), 638-644.
75. 
    Y. Wang, Z. Cai, P. Stothard, S. Moore, R. Goebel, L. Wang, and ——^*.
    Fast accurate missing SNP genotype local imputation.
    BMC Research Notes. 5(2012), Article 404.
74. 
    M. Berjanskii, J. Zhou, Y. Liang, ——, and D. S. Wishart^*.
    Resolution-by-proxy: a simple measure for assessing and comparing the overall quality of NMR protein structures.
    Journal of Biomolecular NMR. 53(3)(2012), 167-180.
73. Y. Shi^*, M. Hasan, Z. Cai, ——, and D. Schuurmans.
    Linear coherent bi-clustering via beam searching and sample set clustering.
    Discrete Mathematics, Algorithms and Applications. 4(2)(2012), Article 1250023.
    (Two preliminary versions appear in COCOA 2010, LNCS 6509, Pages 85-103, and COCOA 2009, LNCS 5573, Pages 73-84.)
    32. Y. Shi^*, M. Hasan, Z. Cai, ——, and D. Schuurmans.
        Linear coherent bi-cluster discovery via beam detection and sample set clustering.
        In Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010). LNCS 6509, Pages 85-103.
    31. Y. Shi^*, Z. Cai, ——, and D. Schuurmans.
        Linear coherent bi-cluster discovery via line detection and sample majority voting.
        In Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA 2009). LNCS 5573, Pages 73-84.
72. Y. Cheng and ——^*.
    Solving haplotype inference problem with non-genotyped founders via integer linear programming.
    Journal of Combinatorial Optimization. 23(1)(2012), 50-60.

71. W. Ding^*, ——, and G. Xue.
    Diameter-constrained Steiner trees.
    Discrete Mathematics, Algorithms and Applications. 3(4)(2011), 491-502.
    (An extended abstract appears in COCOA 2010, LNCS 6509, pages 243-253.)
    30. W. Ding^*, ——, and G. Xue.
        Diameter-constrained Steiner tree.
        In Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010). LNCS 6509, Pages 243-253.
70. 
    ——.
    On the Bandpass problem.
    Journal of Combinatorial Optimization. 22(1)(2011), 71-77.
69. Z.-Z. Chen^*, ——, and L. Wang.
    An approximation algorithm for the minimum co-path set problem.
    Algorithmica. 60(4)(2011), 969-986.
68. 
    Z. Li and ——^*.
    The three column Bandpass problem is solvable in linear time.
    Theoretical Computer Science. 412(4-5)(2011), 281-299.
67. Z. Cai, R. Goebel, and ——^*.
    Size-constrained tree partitioning: approximating the multicast k-tree routing problem.
    Theoretical Computer Science. 412(3; SI for COCOA'09)(2011), 240-245.
    Abstract: In the multicast k-tree routing problem, a data copy is sent from the source node to at most k destination nodes in every transmission. The goal is to minimize the total cost of sending data to all destination nodes, which is measured as the sum of the costs of all routing trees. This problem was formulated out of optical networking and has applications in general multicasting.s Several approximation algorithms, with increasing performance, have been proposed in the last several years; the most recent ones rely heavily on a tree partitioning technique. In this paper, we present a further improved approximation algorithm along the line.s The algorithm has a worst-case performance ratio of 5ρ⁄4 + 3⁄2, where ρ denotes the best approximation ratio for the Steiner minimum tree problem. The proofs of the technical routing lemmas also provide some insights into why such a performance ratio could be the best possible that one can get using this tree partitioning technique.
    29. Z. Cai, R. Goebel, and ——^*.
        Size-constrained tree partitioning: a story on approximation algorithm design for the multicast k-tree routing problem.
        In Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA'09). LNCS 5573, Pages 363-374.

66. 
    Z. Cai, Y. Duan, Y. Li, ——, M. Ozden, and X. Wan^*.
    IPMiner: a progenitor gene identifier for influenza A virus.
    Influenza and Other Respiratory Viruses. 5(S1; SI for Options for the Control of Influenza VII)(2011), 413-415.

65. 
    W. S. Kennedy, H. Kong, ——^*, and G. Yan.
    Linear time construction of 5-phylogenetic roots for tree chordal graphs.
    Journal of Combinatorial Optimization. 19(1)(2010), 94-106.

64. 
    M. Berjanskii, J. Liang, J. Zhou, P. Tang, P. Stothard, Y. Zhu, J. Cruz, C. Macdonell, ——, P. Lu, and D. S. Wishart^*.
    PROSESS: a protein structure evaluation suite and server.
    Nucleic Acids Research. 38(Web Server issue)(2010), W633-W640.
63. 
    J. Zhou, J. Sander^*, Z. Cai, L. Wang, and ——^*.
    Finding the nearest neighbors in biological databases using less distance computations.
    IEEE/ACM Transactions on Computational Biology and Bioinformatics. 7(4)(2010), 669-680.
    Abstract: Modern biological applications usually involve the similarity comparison between two objects, which is often computationally very expensive, such as whole genome pairwise alignment and protein 3D structure alignment. Nevertheless, being able to quickly identify the closest neighboring objects from very large databases for a newly obtained sequence or structure can provide timely hints to its functions and more. This paper presents a substantial speedup technique for the well-studied k-nearest neighbor (k-nn) search, based on novel concepts of virtual pivots and partial pivots, such that a significant number of the expensive distance computations can be avoided. The new method is able to dynamically locate virtual pivots, according to the query, with increasing pruning ability. Using the same or less amount of database preprocessing effort, the new method outperformed the second best method by using no more than 40 percent distance computations per query, on a database of 10,000 gene sequences, compared to several best known k-nn search methods including M-Tree, OMNI, SA-Tree, and LAESA. We demonstrated the use of this method on two biological sequence data sets, one of which is for HIV-1 viral strain computational genotyping.

62. Z. Cai, Z.-Z. Chen, and ——^*.
    A 3.4713-approximation algorithm for the capacitated multicast tree routing problem.
    Theoretical Computer Science. 410(52)(2009), 5415-5424.
    (An extended abstract of an earlier version with performance ratio 3.5375, by Z. Cai, Z.-Z. Chen, ——^*, and L. Wang, appears in COCOA 2008, LNCS 5165, pages 286-295.)
    28. Z. Cai, Z.-Z. Chen, ——, and L. Wang.
        An improved approximation algorithm for the capacitated multicast tree routing problem.
        In Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA'08). LNCS 5165, Pages 286-295.
61. 
    Y. Cheng, H. Sabaa, Z. Cai, R. Goebel, and ——^*.
    Efficient haplotype inference algorithms in one whole genome scan for pedigree data with non-genotyped founders.
    Acta Mathematicae Applicatae Sinica (English Series). 25(3)(2009), 477-488.
    (SI dedicated to the 30th Anniversary of the Institute of Applied Mathematics within the Chinese Academy of Sciences.)
60. 
    Y. Cheng^*, D.-Z. Du, and ——.
    On the upper bounds of the minimum number of rows of disjunct matrices.
    Optimization Letters. 3(2)(2009), 297-302.

59. 
    Y. Cheng^*, D.-Z. Du, K.-I. Ko, and ——.
    On the parameterized complexity of pooling design.
    Journal of Computational Biology. 16(11)(2009), 1529-1537.
58. 
    J. Zhang, D. Xu, W. Gao, ——^*, and S. He^*.
    Isotope pattern vector based MS/MS data calibration for improving peptide and protein identification.
    Rapid Communications in Mass Spectrometry. 23(21)(2009), 3448-3456.
    Abstract: Tandem mass spectra contain noisy peaks which make peak picking for peptide identification difficult. Moreover, all spectral peaks can be shifted due to systematic measurement errors. In this paper, a novel use of an isotope pattern vector (IPV) is proposed for denoising and systematic measurement error prediction. By matching the experimental IPVs with the theoretical IPVs of candidate fragment ions, true ionic peaks can be identified. Furthermore, these identified experimental IPVs and their corresponding theoretical IPVs are used in an optimization process to predict the systematic measurement error associated with the target spectrum. In return, the subsequent spectral data calibration based on the predicted systematic measurement error enhances the data quality. We show that such an integrated denoising and calibration process leads to significantly improved peptide and protein identification. Different from the commonly employed chemical calibration methods, our IPV-based method is a purely computational method for individual spectra analysis and globally optimizes the use of spectral data.
57. 
    M. Berjanskii, P. Tang, J. Liang, J. A. Cruz, J. Zhou, Y. Zhu, E. Bassett, C. MacDonell, P. Lu, ——, and D. S. Wishart^*.
    GeNMR: a web server for rapid NMR-based protein structure determination.
    Nucleic Acids Research. 37(Web Server issue)(2009), W670-W677.
56. 
    Z. Cai, H. Sabaa, Y. Wang, R. Goebel, Z. Wang, J. Xu, P. Stothard, and ——^*.
    Most parsimonious haplotype allele sharing determination.
    BMC Bioinformatics. 10(2009), Article 115.
55. 
    
    G. N. Lin, Z. Cai, ——, S. Chakraborty, and D. Xu^*.
    ComPhy: prokaryotic composite distance phylogenies inferred from whole-genome gene sets.
    BMC Bioinformatics. 10(Suppl 1: SI for APBC'09)(2009), Article S5.
    27. Presented at The Seventh Asia-Pacific Bioinformatics Conference (APBC'09).

54. 
    
    M. E. J. Amaral^*, J. R. Grant, P. K. Riggs, N. B. Stafuzza, E. A. R. Filho, T. Goldammer, R. Weikard, R. M. Brunner, K. J. Kochan, A. J. Greco, J. Jeong, Z. Cai, ——, A. Prasad, S. Kumar, G. P. Saradhi, B. Mathew, M. A. Kumar, M. N. Miziara, P. Mariani, A. R. Caetano, S. R. Galvão, M. S. Tantia, R. K. Vijh, B. Mishra, S. T. B. Kumar, V. A. Pelai, A. M. Santana, L. C. Fornitano, B. C. Jones, H. Tonhati, S. Moore, P. Stothard, and J. E. Womack.
    A first generation whole genome RH map of the river buffalo with comparison to domestic cattle.
    BMC Genomics. 9(2008), Article 631.
53. 
    X.-F. Wan^*, M. Ozden, and ——.
    Ubiquitous reassortments in influenza A viruses.
    Journal of Bioinformatics and Computational Biology. 6(5)(2008), 981-999.
52. 
    D. S. Wishart^*, D. Arndt, M. Berjanskii, P. Tang, J. Zhou, and ——.
    CS23D: a web server for rapid protein structure generation using NMR chemical shifts and sequence data.
    Nucleic Acids Research. 36(Web Server Issue)(2008), W496-W502.
    (A poster by Wishart, Arndt, Berjanskii, Tang, Zhou, Shi, and Lin, presented in PrP Canada'08.)
    
51. 
    
    ——^*, Z. Cai, J. Wu, X.-F. Wan, L. Xu, and R. Goebel.
    Identifying a few foot-and-mouth disease virus signature nucleotide strings for computational genotyping.
    BMC Bioinformatics. 9(2008), Article 279.
    (A preliminary version on string selection, by Wu and Lin, appears in IEEE CIBCB'05, pages 105-112.)
    26. X. Wu and ——.
        Selected string representation for whole genomes.
        In Proceedings of 2005 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (IEEE CIBCB'05). Pages 105-112.
50. 
    Y. Shi, J. Zhou, D. Arndt, D. S. Wishart^*, and ——^*.
    Protein contact order prediction from primary sequences.
    BMC Bioinformatics. 9(2008), Article 255.
    (A poster by Zhou, Shi, Lin, and Wishart, presented in CPI'07.)
    
49. 
    G. Wu^*, M.-Y. Kao^*, ——, and J. You.
    Reconstructing phylogenies from noisy quartets in polynomial time with high success probability.
    Algorithms in Molecular Biology. 3(2008), Article 1.
48. 
    D. S. Wishart^*, D. Arndt, M. Berjanskii, A. C. Guo, Y. Shi, S. Shrivastava, J. Zhou, Y. Zhu, and ——.
    PPT-DB: the protein property prediction and testing database.
    Nucleic Acids Research. 36(Database Issue)(2008), D222-D229.
47. 
    ——^†, Z. Wang^†, L. Wang, Y.-L. Lau, and W. Yang^*.
    Identification of linked regions using high-density SNP genotype data for linkage analyses.
    Bioinformatics. 24(1)(2008), 86-93.

46. 
    X. Wu, Z. Cai, X.-F. Wan, T. Hoang, R. Goebel, and ——^*.
    Nucleotide composition string selection in HIV-1 subtyping using whole genomes.
    Bioinformatics. 23(14)(2007), 1744-1752.
    (A preliminary version on HIV-1 pure subtyping, by Wu, Goebel, Wan, and Lin, appears in LSS CSB'06, pages 179-190. )
    25. X. Wu, R. Goebel, X.-F. Wan, and ——^*.
        Whole genome composition distance for HIV-1 genotyping.
        In Proceedings of the 2006 LSS Computational Systems Bioinformatics Conference (LSS CSB'06). Pages 179-190.
45. 
    X. Wan and ——^*.
    CISA: combined NMR resonance connectivity information determination and sequential assignment.
    IEEE/ACM Transactions on Computational Biology and Bioinformatics. 4(3)(2007), 336-348.
44. 
    X. Wan and ——^*.
    GASA: a graph-based automated NMR backbone resonance sequential assignment program.
    Journal of Bioinformatics and Computational Biology. 5(2A)(2007), 313-333.
    (SI for LSS CSB'06: a preliminary version, by the same authors, appears in LSS CSB'06, pages 55-66. )
    24. X. Wan and ——^*.
        A graph-based automated NMR backbone resonance sequential assignment.
        In Proceedings of the 2006 LSS Computational Systems Bioinformatics Conference (LSS CSB'06). Pages 55-66.
43. 
    Z. Cai, R. Goebel, M. R. Salavatipour, and ——^*.
    Selecting dissimilar genes for multi-class classification: an application in cancer subtyping.
    BMC Bioinformatics. 8(2007), Article 206.
    
    (Preliminary versions, by Cai, Goebel, Salavatipour, Shi, Xu, and Lin, appears in APBC'07, pages 81-90;
    and by Cai, Xu, Shi, Salavatipour, Goebel, and Lin, appears in IEEE BIBE'06, pages 235-242.)
    23. Z. Cai, R. Goebel, M. Salavatipour, Y. Shi, L. Xu, and ——^*.
        Selecting genes with dissimilar discrimination strength for sample class prediction.
        In Proceedings of the Fifth Asia-Pacific Bioinformatics Conference (APBC'07). Pages 81-90.
    22. Z. Cai, L. Xu, Y. Shi, M. Salavatipour, R. Goebel, and ——^*.
        Using gene clustering to identify discriminatory genes with higher classification accuracy.
        In Proceedings of IEEE The 6th Symposium on Bioinformatics and Bioengineering (IEEE BIBE'06). Pages 235-242.
42. 
    X.-F. Wan^†*, X. Wu^†, ——, S. B. Holton, R. A. Desmone, C.-R. Shyu, Y. Guan, and M. Emch.
    Computational identification of reassortments in avian influenza viruses.
    Avian Diseases. 51(s1)(2007), 434-439.
    (SI for ISAI'06: an abstract, by Wu, Holton, Shyu, Lin, and Wan, presented as a poster in ISAI'06, 2006.)
41. 
    G. Wu, J. You, and ——^*.
    Quartet based phylogeny reconstruction with answer set programming.
    IEEE/ACM Transactions on Computational Biology and Bioinformatics. 4(1)(2007), 139-152.
    (Preliminary versions of several parts, by Wu, You, and Lin, appears in LPNMR'05, LNCS/LNAI 3663, pages 369-373;
    and by Wu, Lin, You, and Wu, appears in APBC'05, pages 329-338;
    and by Wu, Lin, and You, appears in IEEE ICTAI'04, pages 612-619.)
    21. G. Wu, J. You^*, and ——.
        Application of Smodels in quartet based phylogeny construction.
        In Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'05). LNCS/LNAI 3662, Pages 369-373.
    20. G. Wu, ——^*, J. You, and X. Wu.
        Faster solution to the maximum quartet consistency problem with constrained programming.
        In Proceedings of the 3rd Asia-Pacific Bioinformatics Conference (APBC'05). Pages 329-338.
    19. G. Wu, ——^*, and J. You.
        Quartet based phylogeny reconstruction with answer set programming.
        In Proceedings of The 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'04). Pages 612-619.
40. 
    J. Zhou, J. Sander, and ——^*.
    Efficient composite pattern finding from monad patterns.
    International Journal on Bioinformatics Research and Applications. 3(1)(2007), 86-99.

39. W. Kennedy, ——^*, and G. Y. Yan.
    Strictly chordal graphs are leaf powers.
    Journal of Discrete Algorithms. 4(4)(2006), 511-525.
38. G. Wu, J. You, and ——^*.
    A polynomial time algorithm for the minimum quartet inconsistency problem with O(n) quartet errors.
    Information Processing Letters. 100(4)(2006), 167-171.
    (An extended abstract, by the same authors, appears in Posters in IEEE CSB'05, pages 55-56.)
37. ——^*, Z. Cai, and D. Lin.
    Path covering on trees with its applications in machine translation.
    Information Processing Letters. 97(2)(2006), 73-81.

36. 
    Z. Cai, M. Heydari, and ——^*.
    Iterated local least squares imputation for microarray missing values.
    Journal of Bioinformatics and Computational Biology. 4(5)(2006), 935-957.
    (A preliminary version, by the same authors, appears in APBC'06, pages 159-168.)
    18. Z. Cai, M. Heydari, and ——^*.
        Microarray missing value imputation by iterated local least squares.
        In Proceedings of the Fourth Asia-Pacific Bioinformatics Conference (APBC'06). Pages 159-168.
35. 
    X.-F. Wan, ——, and D. Xu^*.
    Rnall: an efficient algorithm for predicting RNA local secondary structural landscape in genomes.
    Journal of Bioinformatics and Computational Biology. 4(5)(2006), 1015-1031.
34. 
    X. Wu, X.-F. Wan, G. Wu, D. Xu, and ——^*.
    Phylogenetic analysis using complete signature information of whole genomes and clustered Neighbor-Joining method.
    International Journal on Bioinformatics Research and Applications. 2(3)(2006), 219-248.
33. 
    K. Yang^†, Z. Cai^†, J. Li, and ——^*.
    A stable gene selection in microarray data analysis.
    BMC Bioinformatics. 7(2006), Article 228.
    (A preliminary version, by Yang, Li, Cai, and Lin, appears in IEEE BIBE'05, pages 3-10.)
    17. K. Yang, Z. Cai, J. Li and ——^*.
        A model-free and stable gene selection in microarray data analysis.
        In Proceedings of IEEE The 5th Symposium on Bioinformatics and Bioengineering (IEEE BIBE'05). Pages 3-10.
32. 
    ——^*, X. Wan, T. Tegos, and Y. Li.
    Statistical evaluation of NMR backbone resonance assignment.
    International Journal of Bioinformatics Research and Applications. 2(2)(2006), 147-160.

31. ——.
    An improved approximation algorithm for multicast k-tree routing.
    Journal of Combinatorial Optimization. 9(4)(2005), 349-356.
30. Z. Cai, M. Heydari, and ——^*.
    Clustering binary oligonucleotide fingerprint vectors for DNA clone classification analysis.
    Journal of Combinatorial Optimization. 9(2)(2005), 199-211.

29. 
    T. Tegos, Z.-Z. Chen, and ——^*.
    Heuristic search in constrained bipartite matching with applications to protein NMR backbone resonance assignment.
    Journal of Bioinformatics and Computational Biology. 3(6)(2005), 1331-1350.
28. 
    Z.-Z. Chen, ——, R. Rizzi, J.-J. Wen, D. Xu, Y. Xu, and T. Jiang^*.
    More reliable protein NMR peak assignment via improved 2-interval scheduling.
    Journal of Computational Biology. 12(2)(2005), 129-146.
    (An extended abstract, by Chen, Jiang, Lin, Rizzi, Wen, Xu, and Xu, appears in ESA'03, LNCS 2832, pages 580-592.)
    16. Z.-Z. Chen^*, T. Jiang, ——, R. Rizzi, J. J. Wen, D. Xu, and Y. Xu.
        More reliable protein NMR peak assignment via improved 2-interval scheduling.
        In Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03). LNCS 2832, Pages 580-592.

27. Z.-Z. Chen, Y. Gao, ——^*, R. Niewiadomski, Y. Wang, and J. Wu.
    A space-efficient algorithm for sequence alignment with inversions and reversals.
    Theoretical Computer Science. 325(3)(2004), 361-372.
    (SI for COCOON'03: A preliminary version, by Gao, Wu, Niewiadomski, Wang, Chen, and Lin, appears in COCOON'03, LNCS 2697, pages 57-67.)
    14. Y. Gao, J. Wu, R. Niewiadomski, Y. Wang, Z.-Z. Chen, and ——^*.
        A space efficient algorithm for sequence alignment with inversions.
        In Proceedings of the Ninth International Computing and Combinatorics Conference (COCOON'03). LNCS 2697, Pages 57-67.
26. ——^* and T. Jiang.
    A further improved approximation algorithm for breakpoint graph decomposition.
    Journal of Combinatorial Optimization. 8(2)(2004), 183-194.
25. T. Jiang, ——^*, B. Ma, and K. Zhang.
    The longest common subsequence problem for arc-annotated sequences.
    Journal of Discrete Algorithms. 2(2)(2004), 257-270.
    (SI for CPM'00: An extended abstract, by the same authors, appears in CPM'00, LNCS 1848, pages 154-165.)
    13. T. Jiang, ——^*, B. Ma, and K. Zhang.
        The longest common subsequence problem for arc-annotated sequences.
        In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM'00). LNCS 1848, Pages 154-165.

24. 
    X. Wan, T. Tegos, and ——^*.
    Histogram-based scoring schemes for protein NMR resonance assignment.
    Journal of Bioinformatics and Computational Biology. 2(4)(2004), 747-764.
    (A preliminary version of one part, by Wan, Xu, Slupsky, and Lin, appears in IEEE CSB'03, pages 197-208. )
    15. X. Wan, D. Xu, C. M. Slupsky, and ——^*.
        Automated protein NMR resonance assignments.
        In Proceedings of the 2nd IEEE Computer Society Bioinformatics Conference (CSB'03). Pages 197--208.

23. Z.-Z. Chen, T. Jiang^*, and ——.
    Computing phylogenetic roots with bounded degrees and errors.
    SIAM Journal on Computing. 32(2003), 864-879.
    (An extended abstract, by the same authors, appears in WADS'01, LNCS 2125, pages 377-388.)
    11. Z.-Z. Chen, T. Jiang^*, and ——.
        Computing phylogenetic roots with bounded degrees and errors.
        In Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS'01). LNCS 2125, Pages 377-388.
22. E. Bach, J. Boyar, L. Epstein, L. M. Favrholdt, T. Jiang, K. S. Larsen, ——^*, and R. van Stee.
    Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem.
    Journal of Scheduling. 6(2)(2003), 131-147.
    (An extended abstract, by Bach, Boyar, Jiang, Larsen, and Lin, appears in COCOON'00, LNCS 1858, pages 221-231.)
    10. E. Bach, J. Boyar, T. Jiang, K. S. Larsen, and ——^*.
        Better bounds on the accommodating ratio for seat reservation problem.
        In Proceedings of the 6th Annual International Computing and Combinatorics Conference (COCOON'00). LNCS 1858, Pages 221-231.

21. Z.-Z. Chen, T. Jiang, ——^*, J.-J. Wen, D. Xu, J. Xu, and Y. Xu.
    Approximation algorithms for NMR spectral peak assignment.
    Theoretical Computer Science. 299(1-3)(2003), 211-229.
    (A preliminary version, by Chen, Jiang, Lin, Wen, Xu, and Xu, appears in WABI'02, LNCS 2452, pages 82-96.)
    9. Z.-Z. Chen, T. Jiang, ——^*, J. J. Wen, D. Xu, and Y. Xu.
       Better approximation algorithms for NMR spectral peak assignment.
       In Proceedings of the 2nd Workshop on Algorithms in Bioinformatics (WABI'02). LNCS 2452, Pages 82-96.
20. 
    ——^*, D. Xu, Z.-Z. Chen, T. Jiang, J.-J. Wen, and Y. Xu.
    Computational assignment of protein backbone NMR peaks by efficient bounding and filtering.
    Journal of Bioinformatics and Computational Biology. 1(2)(2003), 387-410.
    (SI for IEEE CSB'02: A preliminary version of one part, by Lin, Xu, Chen, Jiang, Wen, and Xu, appears in IEEE CSB'02, pages 165-174. )
    12. ——^*, D. Xu, Z.-Z. Chen, T. Jiang, and Y. Xu.
        An efficient branch-and-bound algorithm for the assignment of protein backbone NMR peaks.
        In Proceedings of the IEEE Computer Society Bioinformatics Conference 2002 (CSB'02). Pages 165-174.

19. ^[citations] —— and G.L. Xue^*.
    On the terminal Steiner tree problem.
    Information Processing Letters. 84(2)(2002), 103-107.
18. S. P. Chen, Y. He, and ——^*.
    3-partitioning problems for maximizing the minimum load.
    Journal of Combinatorial Optimization. 6(1)(2002), 67-80.
    (A preliminary version, by Lin and Chen, appears in CORSC'96, pages 161-166.)
    6. ——^* and S. P. Chen.
       On worst-case performance of MLPT applying to 3-partitioning problem.
       In Proceedings of the Fifth Conference of Operations Research Society of China (CORSC'96). Pages 161-166.

17. ——^*, Z.-Z. Chen, T. Jiang, and J.-J. Wen.
    The longest common subsequence problem for sequences with nested arc annotations.
    Journal of Computer and System Sciences. 65(3)(2002), 465-480.
    (An extended abstract, by the same authors, appears in ICALP'01, LNCS 2076, pages 444-455.)
    8. ——, Z.-Z. Chen, T. Jiang^*, and J.-J. Wen.
       The longest common subsequence problem for sequences with nested arc annotations.
       In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP'01). LNCS 2076, Pages 444-455.
16. D. Jaitly, P.E. Kearney, ——, and B. Ma^*.
    Methods for reconstructing the history of tandem repeats and their application to the human genome.
    Journal of Computer and System Sciences. 65(3)(2002), 494-507.
15. 
    T. Jiang, ——, B. Ma^*, and K. Zhang.
    A general edit distance between RNA structures.
    Journal of Computational Biology. 9(2)(2002), 371-388.
    (An extended abstract, by Lin, Ma, and Zhang, appears in ACM RECOMB'01, pages 211-220.)
    7. ——, B. Ma^*, and K. Zhang.
       Edit distance between two RNA structures.
       In Proceedings of the 5th ACM Annual International Conference on Computational Molecular Biology (RECOMB'01). Pages 200-209.

14. G. L. Xue^*, —— and D. Z. Du.
    Grade of service Steiner minimum trees in the Euclidean plane.
    Algorithmica. 31(4)(2001), 479-500.
    (An extended abstract, by the same authors, appears in IEEE ISCAS'99, pages VI:182-185.)
    5. G. L. Xue^*, ——, and D. Z. Du.
       Grade of service Steiner minimum trees in the euclidean plane.
       In Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS'99). Vol. VI, 182-185.

13. —— and G. L. Xue^*.
    Signed genome rearrangements by reversals and transpositions: models and approximations.
    Theoretical Computer Science. 259(1-2)(2001), 513-531.
    (An extended abstract, by the same authors, appears in COCOON'99, LNCS 1627, pages 71-80.)
    4. —— and G. L. Xue^*.
       Signed genome rearrangements by reversals and transpositions: models and approximations.
       In Proceedings of the Fifth Annual International Computing and Combinatorics Conference (COCOON'99). LNCS 1627, Pages 71-80.

12. D. H. Chen, D. Z. Du, X. D. Hu, ——, L. S. Wang, and G. L. Xue^*.
    Approximations for Steiner trees with minimum number of Steiner points.
    Journal of Global Optimization. 18(1)(2000), 17-33.
11. ——, D. S. Kim, and D. Z. Du^*.
    Strictly nonblocking multirate broadcasting Clos networks.
    Information. 3(3)(2000), 403-413.
    (An extended abstract, by the same authors, appears in PDCS'98, pages 71-80.)
    3. —— D. S. Kim, and D. Z. Du^*.
       Strictly nonblocking multirate multicast Clos networks.
       In Proceedings of the 10th International Conference on Parallel and Distributed Computing and Systems (PDCS'98)). Pages 417-420.
10. S.-X. Gao^* and ——.
    Decision tree complexity of graph properties with dimension at most 5.
    Journal of Computer Science and Technology. 15(5)(2000), 416-422.
9. D. F. Hsu, X. D. Hu^*, and ——.
   On minimum-weight k-edge connected Steiner networks on metric spaces.
   Graphs and Combinatorics. 16(3)(2000), 275-284.
   (A preliminary version, by Cui, Hsu, Hu, and Lin, appears in ISORA'96, pages 159-164.)
   2. H. Q. Cui, D. F. Hsu, X. D. Hu^*, and ——.
      Algorithms for constructing k-connected spanning networks.
      In Proceedings of the Second International Symposium on Operations Research and its Applications (ISORA'96). Pages 159-164.
8. —— and G. L. Xue^*.
   Reducing the Steiner problem in four uniform orientations.
   Networks. 35(4)(2000), 287-301.
   (A preliminary version, by the same authors, appears in ISAAC'98, LNCS 1533, pages 327-336.)
   1. —— and G. L. Xue^*.
      The Steiner tree problem in λ₄-geometry.
      In Proceedings of the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98). LNCS 1533, Pages 327-336.

7. ——, D. Z. Du^*, X. D. Hu, and G. L. Xue.
   On rearrangeability of multirate Clos networks.
   SIAM Journal on Computing. 28(4)(1999), 1225-1231.
6. —— and G. L. Xue^*.
   Steiner tree problem with minimum number of Steiner points and bounded edge-length.
   Information Processing Letters. 69(2)(1999), 53-57.

5. —— and G. L. Xue^*.
   K-center and k-median problems in graded distances.
   Theoretical Computer Science. 207(1)(1998), 181-192.
4. ——.
   The exact bound of Lee's MLPT.
   Discrete Applied Mathematics. 85(3)(1998), 251-254.
3. ——^*, E. Y. Yao, and Y. He.
   Parallel machines scheduling to maximize the minimum load with non-simultaneous machine available times.
   Operations Research Letters. 22(2-3)(1998), 75-81.

2. Y. He^* and ——.
   Two worst-case performance bounds of LPT algorithm.
   Journal of Zhejiang University. 31(2)(1997), 135-141.
1. ——^*, Y. He, H. Y. Lu, and Y. J. Yao.
   Exact bounds of the modified LPT algorithms applying to parallel machines scheduling with non-simultaneous machine available times.
   Applied Mathematics - A Journal of Chinese Universities. 12B(1)(1997), 109-116.