Informal publications at arXiv:

Qiaojun Shu and
——^{*}.
Planar graphs are acyclically edge (Δ+5)colorable.
(2023) CoRR abs/2306.15813.

Mingyang Gong,
ZhiZhong Chen^{*},
——, and
Zhaohui Zhan.
An approximation algorithm for covering vertices by 4^{+}paths.
(2023) CoRR abs/2304.12779.
Abstract: This paper deals with the problem of finding a collection of vertexdisjoint 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 NPhard and admits an approximation algorithm which achieves a ratio of 2 and runs in O(V^{8}) time.
The known algorithm is based on timeconsuming 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^{2}V^{2}, V^{5}}) 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 maximumweight pathcycle cover in a suitably constructed graph.

Jianming Dong,
Ruyan Jin,
——,
Bing Su,
Weitian Tong^{*}, and
Yao Xu^{*}.
An efficient polynomialtime approximation scheme for parallel multistage open shops.
(2022) CoRR abs/2205.14407.

Yao Xu,
Yong Chen,
Taibo Luo, and
——^{*}.
A local search 2.917approximation algorithm for duopreservation string mapping.
(2017) CoRR abs/1702.01877.
Note: Both the design and analysis of our 2.917approximation was superseded by the work presented in CoRR abs/1702.02405.

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 (22/k)approximation.

Weitian Tong,
ZhiZhong Chen,
Lusheng Wang,
Yinfeng Xu,
Jiuping Xu,
Randy Goebel, and
——^{*}.
An approximation algorithm for the Bandpass2 problem.
(2013) CoRR abs/1307.7089.

In press:

Kenya Kobayashi,
——,
Eiji Miyano^{*},
Toshiki Saitoh,
Akira Suzuki,
Tadatoshi Utashima, and
Tsuyoshi Yagita.
Path cover problems with length cost.
Algorithmica (SI for WALCOM 2022).
Accepted on February 7, 2023.

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 396408.


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 1821, 2023.
Accepted on July 17, 2023.

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). MarnelaVallée, France, June 26–28, 2023.
LIPIcs 259, pages 2:12:12.

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 1316, 2023.
LNCS 13898, pages 3751.

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:153:14.
Abstract: Given a graph, the general problem to cover the maximum number of vertices by a collection of vertexdisjoint 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 NPcomplete.
For a fixed k ≥ 4, the problem is NPhard and the best known approximation algorithm for the weighted set packing problem
implies a kapproximation 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 4approximation algorithm which was presented recently.
We propose the first (0.4394k + O(1))approximation algorithm for the general problem and an improved 2approximation 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.

Yuichi Asahiro,
Jesper Jansson,
——,
Eiji Miyano^{*},
Hirotaka Ono, and
Tadatoshi Utashima.
Polynomialtime 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:115:17.

Yong Chen,
ZhiZhong 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 (IJTCSFAW 2021). Beijing, China.
LNCS 12874, pages 2336.
Abstract: Given a digraph G = (V, E), the kpath partition problem aims
to find a minimum collection of vertexdisjoint 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 NPhard 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⁄2approximation algorithm, for any k ≥ 3,
based on a novel concept of enlarging walk to minimize the number of singletons in the kpath partition.
Secondly, for k = 3, we define the second novel kind of enlarging walks to greedily reduce the number of 2paths in the 3path partition and
propose an improved 13⁄9approximation algorithm.
Lastly, for any k ≥ 7, we present an improved (k+2)⁄3approximation algorithm built on the maximum pathcycle cover followed by
a careful 2cycle elimination process.

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 237239.

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 (FAWAAIM 2012).
LNCS 7285, Pages 351358.
Abstract: The general BandpassB problem is NPhard and can be approximated by a reduction into the Bset packing problem,
with a worst case performance ratio of O(B^{2}).
When B = 2, a maximum weight matching gives a 2approximation to the problem.
The Bandpass2 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⁄19approximation algorithm for the Bandpass problem,
which is the first improvement over the simple maximum weight matching based 2approximation algorithm.

2023:

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) 123144].
Theoretical Computer Science.
975(2023), Article 114114.


Yunong Li,
Hao Li,
Taibo Luo,
——, and
Liang Li^{*}.
Intensitydependent mass search for improving metabolite database matches in chemical isotope labeling LCQTOFMSbased metabolomics.
Analytica Chimica Acta.
1272(2023), 341467 (9 pages).

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 multiscale timeseries data.
Computational and Structural Biotechnology Journal.
21(2023), 31833195.

2022:

Yong Chen,
Randy Goebel,
——^{*},
Longcheng Liu,
Bing Su^{*},
Weitian Tong,
Yao Xu, and
An Zhang.
A local search 4/3approximation algorithm for the minimum 3path partition problem.
Journal of Combinatorial Optimization.
44(2022), 35953610.
Abstract: Given a graph G = (V, E), the 3path partition problem is to find a minimum collection of vertexdisjoint paths
each of order at most 3 to cover all the vertices of V.
It is different from but closely related to the wellknown 3set cover problem.
The best known approximation algorithm for the 3path 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/3approximation.
This ratio matches up to the best approximation ratio for the 3set cover problem.

Yong Chen,
Randy Goebel,
——^{*},
Longcheng Liu,
Bing Su,
Weitian Tong,
Yao Xu^{*}, and
An Zhang.
A local search 4/3approximation algorithm for the minimum 3path partition problem.
In Proceedings of the 13th International Frontiers of Algorithmics Workshop (FAW 2019).
LNCS 11458, pages 1425.

Guangting Chen,
Yong Chen,
ZhiZhong Chen,
——^{*},
Tian Liu, and
An Zhang.
Approximation algorithms for the maximally balanced connected tripartition problem.
Journal of Combinatorial Optimization.
44(2022), 17531773.

Bing Su,
Wyatt Carlson,
Jiabin Fan,
Arthur Gao,
Yanjun Shao, and
——^{*}.
Sharing bicycle relocating with minimum carbon emission.
Operations Research Transactions.
26(3)(2022), 7591.

An Zhang,
Yong Chen,
Guangting Chen,
Zhanwen Chen,
Qiaojun Shu, and
——^{*}.
Maximum matching based approximation algorithms for precedence constrained openshop and flowshop scheduling.
Operations Research Transactions.
26(3)(2022), 5774.

Mingyang Gong,
Randy Goebel,
——^{*}, and
Eiji Miyano.
Improved approximation algorithms for nonpreemptive multiprocessor scheduling with testing.
Journal of Combinatorial Optimization (SI for FAW 2021).
44(2022), 877893.

Mingyang Gong and
——^{*}.
Improved approximation algorithms for multiprocessor scheduling with testing.
In Proceedings of the 15th International Workshop on Frontiers of Algorithmics (IJTCSFAW 2021). Beijing, China.
LNCS 12874, pages 6577.

Wenchang Luo,
Rylan Chin,
Alexander Cai,
——^{*},
Bing Su^{*}, and
An Zhang.
A tardinessaugmented approximation scheme for rejectionallowed multiprocessor rescheduling.
Journal of Combinatorial Optimization.
44(2022), 690722.

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 twomachine flowshop scheduling with a conflict graph.
Journal of Combinatorial Optimization.
43(2022), 571588.

Yinhui Cai^{†},
Guangting Chen,
Yong Chen^{*},
Randy Goebel,
——^{*},
Longcheng Liu^{†}, and
An Zhang.
Approximation algorithms for twomachine flowshop scheduling with a conflict graph.
In Proceedings of the 24th International Computing and Combinatorics Conference (COCOON 2018).
LNCS 10976, pages 205217.


2021:

Yong Chen,
ZhiZhong Chen,
——^{*},
Yao Xu, and
An Zhang.
Approximation algorithms for maximally balanced connected graph partition.
Algorithmica.
83(2021), 37153740.
Abstract: Given a connected graph G = (V, E),
we seek to partition the vertex set V into k nonempty 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 minmax balanced connected graph partition into k parts and denote it as kBGP.
The vertexweighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm.
The vertexweighted 2BGP and 3BGP admit a 5/4approximation and a 3/2approximation, respectively.
When k ≥ 4, no approximability result exists for kBGP, i.e., the vertex unweighted variant, except a trivial kapproximation.
In this paper, we present another 3/2approximation for the 3BGP and then extend it to become a k/2approximation for kBGP,
for any fixed k ≥ 3.
Furthermore, for 4BGP, we propose an improved 24/13approximation.
To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems.

Yong Chen,
ZhiZhong 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 130141.

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), 77108.

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 426438.

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 multipletask parallelmachine 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 twostage flowshop 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 nonpreemptive 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_{1} + m_{2})time
(9  3⁄ m_{1})approximation algorithm, where n and N are the number of jobs and the total number of tasks, respectively,
m_{1} and m_{2} are the numbers of map and reduce machines, respectively, and they can even be part of the input.
Our algorithm improves the previous best 12approximation, 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.

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), 1019.

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 8596.

Yong Chen,
ZhiZhong Chen^{*},
——^{*},
Lusheng Wang, and
An Zhang.
A randomized approximation algorithm for metric triangle packing.
Journal of Combinatorial Optimization (SI for COCOA 2019).
41(2021), 1227.

Yong Chen,
ZhiZhong 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 119129.


——^{*} and
Weitian Tong.
An improved approximation algorithm for the minimum common integer partition problem.
Information and Computation.
281(2021), 104784 (13 pages).
Abstract: Given a collection of multisets {X_{1}, X_{2}, ..., 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 (kMCIP) problem is defined as to find a CIP for
{X_{1}, X_{2}, ..., X_{k}} with the minimum cardinality.
We present a 6⁄5approximation algorithm for the 2MCIP 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.6kapproximation algorithm for kMCIP when k is even
(when k is odd, the approximation ratio is 0.6k+0.4).

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 353364.

Yuichi Asahiro,
Hiroshi Eto,
Tesshu Hanaka,
——,
Eiji Miyano^{*}, and
Ippei Terabaru.
Parameterized algorithms for the happy set problem.
Discrete Applied Mathematics.
304(2021), 3244.

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 323328.

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), 123144.

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 335346.

2020:

Jianming Dong,
Joshua Chang,
Bing Su,
Jueliang Hu, and
——^{*}.
Twostage openshop scheduling with a twomachine flowshop as a stage:
approximation algorithms and empirical experiments.
Journal of Scheduling.
23(2020), 595608.

An Zhang,
Yong Chen,
ZhiZhong Chen, and
——^{*}.
Improved approximation algorithms for path vertex covers in regular graphs.
Algorithmica.
82(2020), 30413064.

Wenchang Luo,
Miaomiao Jin,
Bing Su^{*}, and
——^{*}.
An approximation scheme for rejectionallowed singlemachine rescheduling.
Computers & Industrial Engineering.
146(2020), Article 106574.

Yong Chen,
Randy Goebel, and
——^{*},
Bing Su, and
An Zhang.
Openshop scheduling for unit jobs under precedence constraints.
Theoretical Computer Science (SI for COCOA 2018).
803(2020), 144151.
Abstract: We study openshop 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 threemachine openshop to minimize the makespan,
we first present a simple 5/3approximation 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 singletonjob layers, resulting in an improved partition,
which leads to a 4/3approximation.
Both approximation algorithms apply to the general mmachine openshops too.

An Zhang,
Yong Chen,
Randy Goebel, and
——^{*}.
Openshop 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 329340.

Longcheng Liu,
Yong Chen,
Jianming Dong,
Randy Goebel,
——^{*},
Yue Luo,
Guanqun Ni,
Bing Su,
Yao Xu, and
An Zhang.
Approximation algorithms for the threemachine proportionate mixedshop scheduling.
Theoretical Computer Science (SI for AAIM 2018).
803(2020), 5770.
Abstract: A mixed shop is a manufacturing infrastructure designed to process a mixture of a set of flowshop jobs and a set of openshop jobs.
Mixed shops are in general much more complex to schedule than flowshops and openshops, 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:7074,2015] showed that
the problem is solvable in polynomial time in some very special cases;
for the nonsolvable case, they proposed a 5/3approximation algorithm.
In this paper, we present an improved 4/3approximation algorithm and show that this ratio of 4/3 is asymptotically tight;
when the largest job is a flowshop job, we present a fully polynomialtime approximation scheme (FPTAS).
On the negative side, while the F3  prpt  C_{max} problem is polynomialtime solvable,
we show an interesting hardness result that adding one openshop job to the job set makes the problem NPhard
if this openshop job is larger than any flowshop job.
We are able to design an FPTAS for this special case too.

Longcheng Liu,
Guanqun Ni,
Yong Chen,
Randy Goebel,
Yue Luo,
An Zhang, and
——^{*}.
Approximation algorithms and a hardness result for the threemachine proportionate mixedshop problem.
In Proceedings of the 12th International Conference on Algorithmic Aspects in Information and Management (AAIM 2018).
LNCS 11343, pages 268280.


Yong Chen,
——^{*},
Tian Liu,
Taibo Luo,
Bing Su,
Yao Xu, and
P. Zhang.
A (1.4 + ε)approximation algorithm for the 2MaxDuo problem.
Journal of Combinatorial Optimization.
40(3)(2020), 806824.

Yao Xu,
Yong Chen,
——^{*},
Tian Liu,
Taibo Luo, and
Peng Zhang^{*}.
A (1.4 + ε)approximation algorithm for the 2MaxDuo problem.
In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017).
LIPIcs 92, pages 66:166:12.

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), 238249.

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 112.

2019:

Wenchang Luo,
Yao Xu,
Weitian Tong, and
——^{*}.
Single machine scheduling with jobdependent machine deterioration.
Journal of Scheduling.
22(6)(2019), 691707.
Abstract: We consider the single machine scheduling problem with jobdependent machine deterioration.
In the problem, we are given a single machine with an initial nonnegative maintenance level,
and a set of jobs each with a nonpreemptive 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 nonnegative 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 NPhard;
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 NPhard, thus settling the open problem;
we then design a 2approximation algorithm and a branchandbound exact search algorithm.
Computational experiments have been conducted for the two algorithms to examine their practical performance.

Wenchang Luo,
Yao Xu,
Weitian Tong, and
——^{*}.
Single machine scheduling with jobdependent machine deterioration.
In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016).
LIPIcs 64, pages 55:155:13.

ZhiZhong Chen^{*},
——^{*},
Lusheng Wang,
Yong Chen, and
Dan Wang.
Approximation algorithms for the maximum weight internal spanning tree problem.
Algorithmica.
81(1112)(2019), 41674199.
Abstract: Given a vertexweighted 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 NPhard and APXhard,
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 clawfree graphs, a special case been previously studied, we design a 7/12approximation algorithm.

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 124136.

Yuichi Asahiro,
——,
Zhilong Liu, and
Eiji Miyano^{*}.
An approximation algorithm for the maximum induced matching problem on C_{5}free regular graphs.
IEICE Transactions.
E102A(9)(2019), 11421149.

Yuichi Asahiro,
——,
Zhilong Liu, and
Eiji Miyano^{*}.
An approximation algorithm for the maximum induced matching problem on C_{5}free regular graphs.
Presented in The 12th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC 2019).

Yong Chen,
Randy Goebel,
——^{*},
Bing Su,
Yao Xu, and
An Zhang.
An improved approximation algorithm for the minimum 3path partition problem.
Journal of Combinatorial Optimization.
38(1)(2019), 150164.

Jianming Dong,
Ruyan Jin,
Jueliang Hu, and
——^{*}.
A fully polynomial time approximation scheme for scheduling on parallel identical twostage openshops.
Journal of Combinatorial Optimization.
37(2)(2019), 668648.

Huili Zhang^{*},
Weitian Tong,
——, and
Yinfeng Xu.
Online minimum latency problem with edge uncertainty.
European Journal of Operational Research.
273(2)(2019), 418429.


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), 11701190.

2018:

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), 565578.
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 pseudopolynomial time exact algorithm and a fully polynomial time approximation scheme.

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), 31583176.

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), 462473.

Weitian Tong,
Eiji Miyano,
Randy Goebel, and
——^{*}.
An approximation scheme for minimizing the makespan of
the parallel identical multistage flowshops.
Theoretical Computer Science.
734(SI on FAW 2016)(2018), 2431.

W. Tong,
E. Miyano,
R. Goebel, and
——^{*}.
A PTAS for multiple parallel identical multistage flowshops to minimize the makespan.
In Proceedings of the 10th International Frontiers of Algorithmics Workshop (FAW 2016). LNCS 9711, pages 227237.

Jianming Dong,
Xueshi Wang,
Jueliang Hu, and
——^{*}.
Single machine scheduling with job delivery to multiple customers.
Journal of Scheduling.
21(3)(2018), 337348.

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), 14121438.


2017:

J. Dong,
J. Hu,
M. Y. Kovalyov,
——^{*},
T. Luo,
W. Tong,
X. Wang, and
Y. Xu.
Corrigendum to "An FPTAS for the parallel twostage flowshop problem.
Theoretical Computer Science, 657: 6472 (2017)".
Theoretical Computer Science.
687(2017), 9394.

J. Dong^{†},
W. Tong^{†},
T. Luo^{†},
X. Wang,
J. Hu,
Y. Xu, and
——^{*}.
An FPTAS for the parallel twomachine flowshop problem.
Theoretical Computer Science.
657(Part A)(2017), 6472.


2016:

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), 16451656.

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 104114.

J. Dong,
X. Wang,
J. Hu, and
——^{*}.
An improved twomachine flowshop scheduling with intermediate transportation.
Journal of Combinatorial Optimization.
31(3)(2016), 13161334.

H. Zhang,
W. Tong,
Y. Xu, and
——^{*}.
The Steiner traveling salesman problem with online advanced edge blockages.
Computers and Operations Research.
70(2016), 2638.

J. Dong,
J. Hu, and
——^{*}.
A note on the algorithm LPTFF for a flowshop scheduling with two batchprocessing machines.
Optimization Letters.
10(1)(2016), 109118.

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), 620626.
 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 94103.



Y. Wu,
F. Streijger,
Y. Wang,
——,
S. Christie,
J.M. MacThiong,
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 postinjury)
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 LCMS) with a universal metabolome standard (UMS)
was applied to the metabolomic profiling of these samples.
This method provided enhanced detection of the amine and phenolcontaining submetabolome.
Metabolic pathway analysis revealed dysregulations in arginineproline 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 pairwise 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.

2015:

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), 455470.

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 283298.

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 oneway trading.
Theoretical Computer Science.
607(Part 1: SI on AAIM 2014)(2015), 3548.

L. Huang,
W. Tong,
R. Goebel,
T. Liu, and
——^{*}.
A 0.5358approximation for Bandpass2.
Journal of Combinatorial Optimization.
30(2015), 612626.

H. Zhang,
W. Tong,
Y. Xu, and
——^{*}.
The Steiner traveling salesman problem with online edge blockages.
European Journal of Operational Research.
243(2015), 3040.
Abstract: We consider the online Steiner Traveling Salesman Problem.
In this problem, we are given an edgeweighted 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 nonrecoverable blocked edges.
The edge blockages are realtime, 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 nonpolynomial running time, we present another online polynomialtime near optimal algorithm for the problem.
Experimental results show that our online polynomialtime algorithm produces solutions very close to the offline optimal solutions.


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 Evidencebased 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.


T. Huan,
Y. Wu,
C. Tang,
——, and
L. Li^{*}.
DnsID in MyCompoundID for rapid identification of Dansylated Amine and Phenolcontaining metabolites in LCMSbased metabolomics.
Analytical Chemistry.
87(19)(2015), 98389845.


H. Jiang,
——,
W. Tong,
B. Zhu^{*}, and
D. Zhu.
Isomorphism and similarity for 2generation pedigrees.
In Proceedings of the 10th International Symposium on Bioinformatics Research and Applications (ISBRA 2014). LNCS/LNBI 8492, Page 396.

2014:

W. Tong,
R. Goebel,
T. Liu, and
——^{*}.
Approximating the maximum multiple RNA interaction problem.
Theoretical Computer Science.
556(SI on COCOA 2013)(2014), 6370.
 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 4959.

W. Tong,
R. Goebel, and
——^{*}.
Approximating the minimum independent dominating set in perturbed graphs.
Theoretical Computer Science.
554(SI on COCOON 2013)(2014), 275282.
 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 257267.

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), 5965.


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), 35683574.
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 databasesearch 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 LCMS/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 LCMS techniques currently available for
small molecule or metabolome profiling with an added benefit of covering all di/tripeptide chemical space.

2013:


H. Sabaa,
Z. Cai,
Y. Wang,
R. Goebel,
S. Moore, and
——^{*}.
Whole genome identitybydescent determination.
Journal of Bioinformatics and Computational Biology.
11(2)(2013), Article 1350002.

L. Li^{*},
R. Li,
J. Zhou,
A. Zuniga,
A. E. LewisStanislaus,
Y. Wu,
T. Huan,
J. Zheng,
Y. Shi,
D. S. Wishart, and
——.
MyCompoundID: Using an evidencebased metabolome library for metabolite identification.
Analytical Chemistry.
85(6)(2013), 34013408.
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 webbased 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 chromatographymass 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 evidencebased 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.

2012:

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), 493506.

——^{*},
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), 720730.
Abstract: Given two genomic maps G_{1} and G_{2} 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_{1} and
G_{2} such that the resultant subsequences, denoted as G_{1}^{*}
and G_{2}^{*}, 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 NPhard and APXcomplete, and they admit a 4approximation and a 3approximation respectively.
In this paper, we present an improved 7⁄3approximation algorithm for the CMSR problem,
with its worstcase performance analysis done through a local amortization with a reweighting scheme.
(An extended abstract appears in FAWAAIM 2011, LNCS 6681, pages 4657.)
 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 (FAWAIMM 2011).
LNCS 6681, Pages 4657.


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), 638644.


M. Berjanskii,
J. Zhou,
Y. Liang,
——, and
D. S. Wishart^{*}.
Resolutionbyproxy: a simple measure for assessing and comparing the overall quality of NMR protein structures.
Journal of Biomolecular NMR.
53(3)(2012), 167180.

Y. Shi^{*},
M. Hasan,
Z. Cai,
——, and
D. Schuurmans.
Linear coherent biclustering 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 85103, and COCOA 2009, LNCS 5573, Pages 7384.)
 Y. Shi^{*}, M. Hasan, Z. Cai, ——, and D. Schuurmans.
Linear coherent bicluster 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 85103.
 Y. Shi^{*}, Z. Cai, ——, and D. Schuurmans.
Linear coherent bicluster 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 7384.

Y. Cheng and
——^{*}.
Solving haplotype inference problem with nongenotyped founders via integer linear programming.
Journal of Combinatorial Optimization.
23(1)(2012), 5060.

2011:

W. Ding^{*},
——, and
G. Xue.
Diameterconstrained Steiner trees.
Discrete Mathematics, Algorithms and Applications.
3(4)(2011), 491502.
(An extended abstract appears in COCOA 2010, LNCS 6509, pages 243253.)
 W. Ding^{*}, ——, and G. Xue.
Diameterconstrained Steiner tree.
In Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010).
LNCS 6509, Pages 243253.

——.
On the Bandpass problem.
Journal of Combinatorial Optimization.
22(1)(2011), 7177.

Z.Z. Chen^{*},
——, and
L. Wang.
An approximation algorithm for the minimum copath set problem.
Algorithmica.
60(4)(2011), 969986.

Z. Li and
——^{*}.
The three column Bandpass problem is solvable in linear time.
Theoretical Computer Science.
412(45)(2011), 281299.

Z. Cai,
R. Goebel, and
——^{*}.
Sizeconstrained tree partitioning: approximating the multicast ktree routing problem.
Theoretical Computer Science.
412(3; SI for COCOA'09)(2011), 240245.
Abstract: In the multicast ktree 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 worstcase 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.
 Z. Cai, R. Goebel, and ——^{*}.
Sizeconstrained tree partitioning: a story on approximation algorithm design for the multicast ktree routing problem.
In Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA'09).
LNCS 5573, Pages 363374.


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), 413415.

2010:

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


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), W633W640.

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), 669680.
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 wellstudied knearest neighbor (knn) 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 knn search methods including MTree, OMNI, SATree, and LAESA.
We demonstrated the use of this method on two biological sequence data sets, one of which is for HIV1 viral strain computational genotyping.

2009:

Z. Cai,
Z.Z. Chen, and
——^{*}.
A 3.4713approximation algorithm for the capacitated multicast tree routing problem.
Theoretical Computer Science.
410(52)(2009), 54155424.
(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 286295.)
 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 286295.

Y. Cheng,
H. Sabaa,
Z. Cai,
R. Goebel, and
——^{*}.
Efficient haplotype inference algorithms in one whole genome scan for pedigree data with nongenotyped founders.
Acta Mathematicae Applicatae Sinica (English Series).
25(3)(2009), 477488.
(SI dedicated to the 30th Anniversary of the Institute of Applied Mathematics within the Chinese Academy of Sciences.)

Y. Cheng^{*},
D.Z. Du, and
——.
On the upper bounds of the minimum number of rows of disjunct matrices.
Optimization Letters.
3(2)(2009), 297302.


Y. Cheng^{*},
D.Z. Du,
K.I. Ko, and
——.
On the parameterized complexity of pooling design.
Journal of Computational Biology.
16(11)(2009), 15291537.

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), 34483456.
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 IPVbased method is a purely computational method for individual spectra analysis and globally optimizes the use of spectral data.

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 NMRbased protein structure determination.
Nucleic Acids Research.
37(Web Server issue)(2009), W670W677.


 Presented at The Seventh AsiaPacific Bioinformatics Conference (APBC'09).

2008:


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.

X.F. Wan^{*},
M. Ozden, and
——.
Ubiquitous reassortments in influenza A viruses.
Journal of Bioinformatics and Computational Biology.
6(5)(2008), 981999.

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), W496W502.
(A poster by Wishart, Arndt, Berjanskii, Tang, Zhou, Shi, and Lin, presented in
PrP Canada'08.)

 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 105112.





2007:


(A preliminary version on HIV1 pure subtyping, by Wu, Goebel, Wan, and Lin, appears in
LSS CSB'06, pages 179190.
)
 X. Wu, R. Goebel, X.F. Wan, and ——^{*}.
Whole genome composition distance for HIV1 genotyping.
In Proceedings of the 2006 LSS Computational Systems Bioinformatics Conference (LSS CSB'06). Pages 179190.

X. Wan and
——^{*}.
CISA: combined NMR resonance connectivity information determination and sequential assignment.
IEEE/ACM Transactions on Computational Biology and Bioinformatics.
4(3)(2007), 336348.

X. Wan and
——^{*}.
GASA: a graphbased automated NMR backbone resonance sequential assignment program.
Journal of Bioinformatics and Computational Biology.
5(2A)(2007), 313333.
(SI for LSS CSB'06: a preliminary version, by the same authors, appears in
LSS CSB'06, pages 5566.
)
 X. Wan and ——^{*}.
A graphbased automated NMR backbone resonance sequential assignment.
In Proceedings of the 2006 LSS Computational Systems Bioinformatics Conference (LSS CSB'06). Pages 5566.

(Preliminary versions, by Cai, Goebel, Salavatipour, Shi, Xu, and Lin, appears in
APBC'07, pages 8190;
and by Cai, Xu, Shi, Salavatipour, Goebel, and Lin, appears in
IEEE BIBE'06, pages 235242.)
 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 AsiaPacific Bioinformatics Conference (APBC'07). Pages 8190.
 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 235242.

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), 434439.
(SI for ISAI'06: an abstract, by Wu, Holton, Shyu, Lin, and Wan, presented as a poster in
ISAI'06, 2006.)

G. Wu,
J. You, and
——^{*}.
Quartet based phylogeny reconstruction with answer set programming.
IEEE/ACM Transactions on Computational Biology and Bioinformatics.
4(1)(2007), 139152.
(Preliminary versions of several parts, by Wu, You, and Lin, appears in
LPNMR'05, LNCS/LNAI 3663, pages 369373;
and by Wu, Lin, You, and Wu, appears in
APBC'05, pages 329338;
and by Wu, Lin, and You, appears in
IEEE ICTAI'04, pages 612619.)
 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 369373.
 G. Wu, ——^{*}, J. You, and X. Wu.
Faster solution to the maximum quartet consistency problem with constrained programming.
In Proceedings of the 3rd AsiaPacific Bioinformatics Conference (APBC'05). Pages 329338.
 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 612619.

J. Zhou,
J. Sander, and
——^{*}.
Efficient composite pattern finding from monad patterns.
International Journal on Bioinformatics Research and Applications.
3(1)(2007), 8699.

2006:

W. Kennedy,
——^{*}, and
G. Y. Yan.
Strictly chordal graphs are leaf powers.
Journal of Discrete Algorithms.
4(4)(2006), 511525.

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), 167171.
(An extended abstract, by the same authors, appears in Posters in
IEEE CSB'05, pages 5556.)

——^{*},
Z. Cai, and
D. Lin.
Path covering on trees with its applications in machine translation.
Information Processing Letters.
97(2)(2006), 7381.


Z. Cai,
M. Heydari, and
——^{*}.
Iterated local least squares imputation for microarray missing values.
Journal of Bioinformatics and Computational Biology.
4(5)(2006), 935957.
(A preliminary version, by the same authors, appears in
APBC'06, pages 159168.)
 Z. Cai, M. Heydari, and ——^{*}.
Microarray missing value imputation by iterated local least squares.
In Proceedings of the Fourth AsiaPacific Bioinformatics Conference (APBC'06). Pages 159168.

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), 10151031.

X. Wu,
X.F. Wan,
G. Wu,
D. Xu, and
——^{*}.
Phylogenetic analysis using complete signature information of whole genomes and clustered NeighborJoining method.
International Journal on Bioinformatics Research and Applications.
2(3)(2006), 219248.

(A preliminary version, by Yang, Li, Cai, and Lin, appears in
IEEE BIBE'05, pages 310.)
 K. Yang, Z. Cai, J. Li and ——^{*}.
A modelfree and stable gene selection in microarray data analysis.
In Proceedings of IEEE The 5th Symposium on Bioinformatics and Bioengineering (IEEE BIBE'05). Pages 310.

——^{*},
X. Wan,
T. Tegos, and
Y. Li.
Statistical evaluation of NMR backbone resonance assignment.
International Journal of Bioinformatics Research and Applications.
2(2)(2006), 147160.

2005:

——.
An improved approximation algorithm for multicast ktree routing.
Journal of Combinatorial Optimization.
9(4)(2005), 349356.

Z. Cai,
M. Heydari, and
——^{*}.
Clustering binary oligonucleotide fingerprint vectors for DNA clone classification analysis.
Journal of Combinatorial Optimization.
9(2)(2005), 199211.


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), 13311350.

Z.Z. Chen,
——,
R. Rizzi,
J.J. Wen,
D. Xu,
Y. Xu, and
T. Jiang^{*}.
More reliable protein NMR peak assignment via improved 2interval scheduling.
Journal of Computational Biology.
12(2)(2005), 129146.
(An extended abstract, by Chen, Jiang, Lin, Rizzi, Wen, Xu, and Xu, appears in
ESA'03, LNCS 2832, pages 580592.)
 Z.Z. Chen^{*}, T. Jiang, ——, R. Rizzi, J. J. Wen, D. Xu, and Y. Xu.
More reliable protein NMR peak assignment via improved 2interval scheduling.
In Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03). LNCS 2832, Pages 580592.

2004:

Z.Z. Chen,
Y. Gao,
——^{*},
R. Niewiadomski,
Y. Wang, and
J. Wu.
A spaceefficient algorithm for sequence alignment with inversions and reversals.
Theoretical Computer Science.
325(3)(2004), 361372.
(SI for COCOON'03: A preliminary version, by Gao, Wu, Niewiadomski, Wang, Chen, and Lin, appears in
COCOON'03, LNCS 2697, pages 5767.)
 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 5767.

——^{*} and
T. Jiang.
A further improved approximation algorithm for breakpoint graph decomposition.
Journal of Combinatorial Optimization.
8(2)(2004), 183194.

T. Jiang,
——^{*},
B. Ma, and
K. Zhang.
The longest common subsequence problem for arcannotated sequences.
Journal of Discrete Algorithms.
2(2)(2004), 257270.
(SI for CPM'00: An extended abstract, by the same authors, appears in
CPM'00, LNCS 1848, pages 154165.)
 T. Jiang, ——^{*}, B. Ma, and K. Zhang.
The longest common subsequence problem for arcannotated sequences.
In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM'00). LNCS 1848, Pages 154165.


X. Wan,
T. Tegos, and
——^{*}.
Histogrambased scoring schemes for protein NMR resonance assignment.
Journal of Bioinformatics and Computational Biology.
2(4)(2004), 747764.
(A preliminary version of one part, by Wan, Xu, Slupsky, and Lin, appears in
IEEE CSB'03, pages 197208.
)
 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 197208.

2003:

Z.Z. Chen,
T. Jiang^{*}, and
——.
Computing phylogenetic roots with bounded degrees and errors.
SIAM Journal on Computing.
32(2003), 864879.
(An extended abstract, by the same authors, appears in
WADS'01, LNCS 2125, pages 377388.)
 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 377388.

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), 131147.
(An extended abstract, by Bach, Boyar, Jiang, Larsen, and Lin, appears in
COCOON'00, LNCS 1858, pages 221231.)
 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 221231.


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(13)(2003), 211229.
(A preliminary version, by Chen, Jiang, Lin, Wen, Xu, and Xu, appears in
WABI'02, LNCS 2452, pages 8296.)
 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 8296.

——^{*},
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), 387410.
(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 165174.
)
 ——^{*}, D. Xu, Z.Z. Chen, T. Jiang, and Y. Xu.
An efficient branchandbound algorithm for the assignment of protein backbone NMR peaks.
In Proceedings of the IEEE Computer Society Bioinformatics Conference 2002 (CSB'02). Pages 165174.

2002:

^{[citations]}
—— and G.L. Xue^{*}.
On the terminal Steiner tree problem.
Information Processing Letters.
84(2)(2002), 103107.

S. P. Chen,
Y. He, and
——^{*}.
3partitioning problems for maximizing the minimum load.
Journal of Combinatorial Optimization.
6(1)(2002), 6780.
(A preliminary version, by Lin and Chen, appears in
CORSC'96, pages 161166.)
 ——^{*} and S. P. Chen.
On worstcase performance of MLPT applying to 3partitioning problem.
In Proceedings of the Fifth Conference of Operations Research Society of China (CORSC'96). Pages 161166.


——^{*},
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), 465480.
(An extended abstract, by the same authors, appears in
ICALP'01, LNCS 2076, pages 444455.)
 ——, 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 444455.

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), 494507.

T. Jiang,
——,
B. Ma^{*}, and
K. Zhang.
A general edit distance between RNA structures.
Journal of Computational Biology.
9(2)(2002), 371388.
(An extended abstract, by Lin, Ma, and Zhang, appears in
ACM RECOMB'01, pages 211220.)
 ——, 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 200209.

2001:

G. L. Xue^{*},
—— and
D. Z. Du.
Grade of service Steiner minimum trees in the Euclidean plane.
Algorithmica.
31(4)(2001), 479500.
(An extended abstract, by the same authors, appears in
IEEE ISCAS'99, pages VI:182185.)
 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, 182185.


—— and
G. L. Xue^{*}.
Signed genome rearrangements by reversals and transpositions: models and approximations.
Theoretical Computer Science.
259(12)(2001), 513531.
(An extended abstract, by the same authors, appears in
COCOON'99, LNCS 1627, pages 7180.)
 —— 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 7180.

2000:

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), 1733.

——,
D. S. Kim, and
D. Z. Du^{*}.
Strictly nonblocking multirate broadcasting Clos networks.
Information.
3(3)(2000), 403413.
(An extended abstract, by the same authors, appears in
PDCS'98, pages 7180.)
 —— 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 417420.

S.X. Gao^{*} and
——.
Decision tree complexity of graph properties with dimension at most 5.
Journal of Computer Science and Technology.
15(5)(2000), 416422.

D. F. Hsu,
X. D. Hu^{*}, and
——.
On minimumweight kedge connected Steiner networks on metric spaces.
Graphs and Combinatorics.
16(3)(2000), 275284.
(A preliminary version, by Cui, Hsu, Hu, and Lin, appears in
ISORA'96, pages 159164.)
 H. Q. Cui, D. F. Hsu, X. D. Hu^{*}, and ——.
Algorithms for constructing kconnected spanning networks.
In Proceedings of the Second International Symposium on Operations Research and its Applications (ISORA'96). Pages 159164.

—— and
G. L. Xue^{*}.
Reducing the Steiner problem in four uniform orientations.
Networks.
35(4)(2000), 287301.
(A preliminary version, by the same authors, appears in
ISAAC'98, LNCS 1533, pages 327336.)
 —— and G. L. Xue^{*}.
The Steiner tree problem in λ_{4}geometry.
In Proceedings of the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98). LNCS 1533, Pages 327336.


1999:

——,
D. Z. Du^{*},
X. D. Hu, and
G. L. Xue.
On rearrangeability of multirate Clos networks.
SIAM Journal on Computing.
28(4)(1999), 12251231.

—— and
G. L. Xue^{*}.
Steiner tree problem with minimum number of Steiner points and bounded edgelength.
Information Processing Letters.
69(2)(1999), 5357.


1998:

—— and
G. L. Xue^{*}.
Kcenter and kmedian problems in graded distances.
Theoretical Computer Science.
207(1)(1998), 181192.

——.
The exact bound of Lee's MLPT.
Discrete Applied Mathematics.
85(3)(1998), 251254.

——^{*},
E. Y. Yao, and
Y. He.
Parallel machines scheduling to maximize the minimum load with nonsimultaneous machine available times.
Operations Research Letters.
22(23)(1998), 7581.


1997:

Y. He^{*} and
——.
Two worstcase performance bounds of LPT algorithm.
Journal of Zhejiang University.
31(2)(1997), 135141.

——^{*},
Y. He,
H. Y. Lu, and
Y. J. Yao.
Exact bounds of the modified LPT algorithms applying to parallel machines scheduling with nonsimultaneous machine available times.
Applied Mathematics  A Journal of Chinese Universities.
12B(1)(1997), 109116.

