Guohui Lin

I&C Journal 2026 Journal Article

Approximation algorithms for non-sequential star packing problems

• Mengyuan Hu
• An Zhang
• Yong Chen
• Mingyang Gong
• Guohui Lin

For a positive integer k ≥ 1, a k-star ( k + -star, k − -star, respectively) is a connected graph containing a degree-ℓ vertex and ℓ degree-1 vertices, where ℓ = k ( ℓ ≥ k, 1 ≤ ℓ ≤ k, respectively). The k + -star packing problem is to cover as many vertices of an input graph G as possible using vertex-disjoint k + -stars in G; and given k > t ≥ 1, the k − / t -star packing problem is to cover as many vertices of G as possible using vertex-disjoint k − -stars but no t-stars in G. Both problems are NP-hard for any fixed k ≥ 2. We present a ( 1 + k 2 2 k + 1 ) - and a 3 2 -approximation algorithms for the k + -star packing problem when k ≥ 3 and k = 2, respectively, and a ( 1 + 1 t + 1 + 1 / k ) -approximation algorithm for the k − / t -star packing problem when k > t ≥ 2. They are all local search algorithms and they improve the best known approximation algorithms for the problems, respectively.

TCS Journal 2026 Journal Article

Single machine controllable scheduling with bounded makespan

• Yanjie Guo
• Wenchang Luo
• Guohui Lin

In a controllable scheduling environment, the processing time of a job can be shortened by allocating extra resource at a cost, or the job can be declined for processing by paying a penalty. We investigate the single machine controllable scheduling to minimize the sum of the total resource consumption cost, the total job rejection cost, and the makespan of the accepted jobs, where the makespan is upper bounded and the job processing time is a decreasing linear function in the amount of allocated resource. We first show that the studied problem is polynomial solvable if the makespan is unbounded, but otherwise is NP-hard, and characterize important structural properties for the optimal solution; we then take advantage of the structural properties to design several algorithms for the problem, including a pseudo-polynomial time dynamic programming exact algorithm, an O(n 2)-time n-approximation algorithm where n is the number of jobs, and building on top of the dynamic programming exact algorithm, the n-approximation algorithm and the bound improvement procedure, two fully polynomial time approximation schemes.

I&C Journal 2025 Journal Article

Approximation algorithms for the maximum path cover problem using long paths

• Mingyang Gong
• Yong Chen
• Zhi-Zhong Chen
• Guohui Lin
• Bing Su
• Lusheng Wang

The problem studied in this paper is to find a collection of vertex-disjoint paths in a given graph G = ( V, E ) such that each path has length at least k, called a long path, and the total number of edges on these paths is maximized. The problem is NP-hard for any fixed k or when k is part of the input, by a reduction from the Hamiltonian path problem. Berman and Karpinski presented a 7/6-approximation algorithm for k = 1, but for a general k ≥ 2, there is no approximation algorithm directly for the problem. We present the first local search ( 0. 4394 k + O ( 1 ) ) -approximation algorithm for any fixed k ≥ 1, and a 1. 4254-approximation algorithm for k = 2 built on top of a maximum triangle-free path-cycle cover.

TCS Journal 2025 Journal Article

Path cover using only short paths

• Mingyang Gong
• Guangting Chen
• Zhi-Zhong Chen
• Guohui Lin
• Riki Uchida

We study a variant of the well-known Path Cover problem where the candidate paths in a solution have orders up to a fixed integer k. In Path Cover, one finds a minimum number of vertex-disjoint paths in an input graph to cover all the vertices; in our variant, not all paths but only those short ones, i. e. , containing up to k vertices, can be used as candidates. The problem is NP-hard when k ≥ 3; in the literature, there exist quite a number of approximation algorithms, especially for small k's. We present an improved k 3 -approximation algorithm for k ∈ { 6, 7, 8 }, an improved 55 31 -approximation algorithm for k = 5, and an improved 8 5 -approximation algorithm for k = 4. The novelty inside these improved algorithms is observing a close connection between an optimal path cover and a certain polynomial-time computed edge set.

I&C Journal 2024 Journal Article

Approximating the directed path partition problem

• Yong Chen
• Zhi-Zhong Chen
• Curtis Kennedy
• Guohui Lin
• Yao Xu
• An Zhang

Given a digraph G = ( V, E ), the k-path partition problem aims to find a minimum collection of vertex-disjoint directed paths, of order at most k, to cover all the vertices. The problem has various applications. 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, based on a novel concept of enlarging walk to minimize the number of singletons. 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.

TCS Journal 2023 Journal Article

Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144]

• Yuichi Asahiro
• Hiroshi Eto
• Tesshu Hanaka
• Guohui Lin
• Eiji Miyano
• Ippei Terabaru

For a graph G = ( V, E ) and a subset S ⊆ V of vertices, a vertex is happy if all its neighbor vertices in G are contained in S. Given a connected undirected graph and an integer k, the Maximum Happy Set Problem (MaxHS) asks to find a set S of k vertices which maximizes the number of happy vertices in S (note that all happy vertices in V belong to S). We proposed an algorithm for MaxHS on proper interval graphs in Theor. Comput. Sci. 866 (2021) 123–144. However, due to a wrong observation made by the authors, it works only on proper interval graphs obeying the observation. In this corrigendum, we propose a new algorithm which runs in O ( k | V | log ⁡ k + | E | ) time for proper interval graphs.

MFCS Conference 2022 Conference Paper

Approximation Algorithms for Covering Vertices by Long Paths

• Mingyang Gong
• Jing Fan
• Guohui Lin
• Eiji Miyano

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. 4394 k + 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 performance analyses are done via amortization.

TCS Journal 2021 Journal Article

Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles

• Qiaojun Shu
• Yong Chen
• Shuguang Han
• Guohui Lin
• Eiji Miyano
• An Zhang

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiamčik (1978) and Alon, Sudakov and Zaks (2001) states that every simple graph with maximum degree Δ is acyclically edge ( Δ + 2 ) -colorable. Despite many milestones, the conjecture remains open even for planar graphs. In this paper, we confirm affirmatively the conjecture on planar graphs without intersecting triangles. We do so by first showing, by discharging methods, that every planar graph without intersecting triangles must have at least one of the six specified groups of local structures, and then proving the conjecture by recoloring certain edges in each such local structure and by induction on the number of edges in the graph.

I&C Journal 2021 Journal Article

An improved approximation algorithm for the minimum common integer partition problem

• Guohui Lin
• Weitian Tong

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 (k-MCIP) problem is defined as to find a CIP for { X 1, X 2, …, 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. 6 k + 0. 4 ).

TCS Journal 2021 Journal Article

Complexity and approximability of the happy set problem

• Yuichi Asahiro
• Hiroshi Eto
• Tesshu Hanaka
• Guohui Lin
• Eiji Miyano
• Ippei Terabaru

In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G = ( V, E ) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G = ( V, E ) and an integer k, the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a ( 2 Δ + 1 ) -approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard.

TCS Journal 2021 Journal Article

Improved hardness and approximation results for single allocation hub location problems

• Xing Wang
• Guangting Chen
• Yong Chen
• Guohui Lin
• Yonghao Wang
• An Zhang

Given a metric graph G = ( V, E, w ) and an integer k, we aim to find a single allocation k-hub location, which is a spanning subgraph consisting of a clique of size k such that every node outside of the clique is adjacent to exactly one node inside the clique. For various objective functions studied in the literature, we present improved hardness and approximation results.

TCS Journal 2020 Journal Article

Approximation algorithms for the three-machine proportionate mixed shop scheduling

• Longcheng Liu
• Yong Chen
• Jianming Dong
• Randy Goebel
• Guohui Lin
• Yue Luo
• Guanqun Ni
• Bing Su

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 M 3 | p r p t | C max, in which by “proportionate” each job has equal processing times on all three machines. Koulamas and Kyparisis (2015) [6] 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 first 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 then present a fully polynomial-time approximation scheme (FPTAS). On the negative side, while the F 3 | p r p t | 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.

TCS Journal 2020 Journal Article

Exact algorithms for the repetition-bounded longest common subsequence problem

• Yuichi Asahiro
• Jesper Jansson
• Guohui Lin
• Eiji Miyano
• Hirotaka Ono
• Tadatoshi Utashima

In this paper, we study exact, exponential-time algorithms for a variant of the classic Longest Common Subsequence problem called the Repetition-Bounded Longest Common Subsequence problem (or RBLCS, for short): Let an alphabet S be a finite set of symbols and an occurrence constraint C o c c be a function C o c c: S → N, assigning an upper bound on the number of occurrences of each symbol in S. Given two sequences X and Y over the alphabet S and an occurrence constraint C o c c, the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s ∈ S appears at most C o c c ( s ) times in the obtained subsequence. The special case where C o c c ( s ) = 1 for every symbol s ∈ S is known as the Repetition-Free Longest Common Subsequence problem (RFLCS) and has been studied previously; e. g. , in [1], Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS. However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that | X | ≤ | Y | and | X | = n. In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O ( 1. 44225 n ). Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O ( 1. 44225 n ) for any occurrence constraint C o c c, and even less in certain special cases. In particular, for RFLCS, our DP-based algorithm runs in O ( 1. 41422 n ) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances.

TCS Journal 2020 Journal Article

Open-shop scheduling for unit jobs under precedence constraints

• Yong Chen
• Randy Goebel
• Guohui Lin
• Bing Su
• An Zhang

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 algorithm based on a partition of the job set into agreeable layers using the natural layered representation of the precedence graph, which is directed acyclic. 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 algorithm. Both approximation algorithms apply to the general m-machine open-shops too.

TCS Journal 2018 Journal Article

An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops

• Weitian Tong
• Eiji Miyano
• Randy Goebel
• Guohui Lin

In the parallel k-stage flow-shops problem, we are given m identical k-stage flow-shops and a set of jobs. Each job can be processed by any one of the flow-shops but switching between flow-shops is not allowed. The objective is to minimize the makespan, which is the finishing time of the last job. This problem generalizes the classical parallel identical machine scheduling (where k = 1 ) and the classical flow-shop scheduling (where m = 1 ) problems, and thus it is NP-hard. We present a polynomial-time approximation scheme (PTAS) for the problem, when m and k are fixed constants. The key technique is to partition the jobs into big jobs and small jobs, enumerate over all feasible schedules for the big jobs, and handle the small jobs by solving a linear program and employing a “sliding” method. Such a technique has been used in the design of PTAS for several flow-shop scheduling variants. Our main contributions are the non-trivial application of this technique and a valid answer to the open question in the literature.

TCS Journal 2017 Journal Article

An FPTAS for the parallel two-stage flowshop problem

• Jianming Dong
• Weitian Tong
• Taibo Luo
• Xueshi Wang
• Jueliang Hu
• Yinfeng Xu
• Guohui Lin

We consider the NP-hard m-parallel two-stage flowshop problem, abbreviated as the ( m, 2 ) -PFS problem, where we need to schedule n jobs to m parallel identical two-stage flowshops in order to minimize the makespan, i. e. the maximum completion time of all the jobs on the m flowshops. The ( m, 2 ) -PFS problem can be decomposed into two subproblems: to assign the n jobs to the m parallel flowshops, and for each flowshop to schedule the jobs assigned to the flowshop. We first present a pseudo-polynomial time dynamic programming algorithm to solve the ( m, 2 ) -PFS problem optimally, for any fixed m, based on an earlier idea for solving the ( 2, 2 ) -PFS problem. Using the dynamic programming algorithm as a subroutine, we design a fully polynomial-time approximation scheme (FPTAS) for the ( m, 2 ) -PFS problem.

TCS Journal 2017 Journal Article

Corrigendum to “An FPTAS for the parallel two-stage flowshop problem” [Theoret. Comput. Sci. 657 (2017) 64–72]

• Jianming Dong
• Jueliang Hu
• Mikhail Y. Kovalyov
• Guohui Lin
• Taibo Luo
• Weitian Tong
• Xueshi Wang
• Yinfeng Xu

TCS Journal 2016 Journal Article

Smoothed heights of tries and patricia tries

• Weitian Tong
• Randy Goebel
• Guohui Lin

Tries and patricia tries are two popular data structures for storing strings. Let H n denote the height of the trie (the patricia trie, respectively) on a set of n strings. Under the uniform distribution model on the strings, it is well known that H n / log ⁡ n → 2 for tries and H n / log ⁡ n → 1 for patricia tries, when n approaches infinity. Nevertheless, in the worst case, the height of a trie can be unbounded and the height of a patricia trie is in Θ ( n ). To better understand the practical performance of both tries and patricia tries, we investigate these two classical data structures in a smoothed analysis model. Given a set S = { s 1, s 2, …, s n } of n binary strings, we perturb the set by adding an i. i. d. Bernoulli random noise to each bit of every string. We show that the resulting smoothed heights of the trie and the patricia trie are both in Θ ( log ⁡ n ).

TCS Journal 2015 Journal Article

Competitive algorithms for unbounded one-way trading

• Francis Y.L. Chin
• Bin Fu
• Jiuling Guo
• Shuguang Han
• Jueliang Hu
• Minghui Jiang
• Guohui Lin
• Hing-Fung Ting

In the one-way trading problem, a seller has L units of product to be sold to a sequence σ of buyers u 1, u 2, …, u σ arriving online and he needs to decide, for each u i, the amount of product to be sold to u i at the then-prevailing market price p i. The objective is to maximize the seller's revenue. We note that all previous algorithms for the problem need to impose some artificial upper bound M and lower bound m on the market prices, and the seller needs to know either the values of M and m, or their ratio M / m, at the outset. This paper gives a one-way trading algorithm that does not impose any bounds on market prices and whose performance guarantee depends directly on the input. In particular, we give a class of one-way trading algorithms such that for any positive integer h and any positive number ϵ, we have an algorithm A h, ϵ that has competitive ratio O ( log ⁡ r ⁎ ( log ( 2 ) ⁡ r ⁎ ) … ( log ( h − 1 ) ⁡ r ⁎ ) ( log ( h ) ⁡ r ⁎ ) 1 + ϵ ) if the value of r ⁎ = p ⁎ / p 1, the ratio of the highest market price p ⁎ = max i ⁡ p i and the first price p 1, is large and satisfies log ( h ) ⁡ r ⁎ > 1, where log ( i ) ⁡ x denotes the application of the logarithm function i times to x; otherwise, A h, ϵ has a constant competitive ratio Γ h. We also show that our algorithms are near optimal by showing that given any positive integer h and any one-way trading algorithm A, we can construct a sequence of buyers σ with log ( h ) ⁡ r ⁎ > 1 such that the ratio between the optimal revenue and the revenue obtained by A is Ω ( log ⁡ r ⁎ ( log ( 2 ) ⁡ r ⁎ ) … ( log ( h − 1 ) ⁡ r ⁎ ) ( log ( h ) ⁡ r ⁎ ) ). A special case of the one-way trading is also studied, in which the L units of product are comprised of L items, each of which must be sold atomically (or equivalently, the amount of product sold to each buyer must be an integer). Furthermore, a complementary problem to the one-way trading problem, say, the one-way buying problem, is studied in this paper. In the one-way buying problem, a buyer wants to purchase one unit of product through a sequence of n sellers v 1, v 2, …, v n arriving online, and she needs to decide the fraction to purchase from each v i at the then-prevailing market price p i. Her objective is to minimize the cost. The optimal competitive algorithms whose performance guarantees depend only on the lowest market price p ⁎ = min i ⁡ p i, and one of M and φ, the price fluctuation ratio, are presented.

TCS Journal 2015 Journal Article

Improved parameterized and exact algorithms for cut problems on trees

• Iyad Kanj
• Guohui Lin
• Tian Liu
• Weitian Tong
• Ge Xia
• Jinhui Xu
• Boting Yang
• Fenghui Zhang

We study the Multicut on Trees and the Generalized Multiway Cut on Trees problems. For the Multicut on Trees problem, we present a parameterized algorithm that runs in time O ⁎ ( ρ k ), where ρ = 2 + 1 < 1. 554 is the positive root of the polynomial x 4 − 2 x 2 − 1. This improves the current-best algorithm of Chen et al. that runs in time O ⁎ ( 1. 619 k ). For the Generalized Multiway Cut on Trees problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the Generalized Multiway Cut on Trees problem to the Multicut on Trees problem, our results give a parameterized algorithm that solves the Generalized Multiway Cut on Trees problem in time O ⁎ ( ρ k ).

TCS Journal 2014 Journal Article

Approximating the maximum multiple RNA interaction problem

• Weitian Tong
• Randy Goebel
• Tian Liu
• Guohui Lin

RNA interactions are fundamental in many cellular processes, where two or more RNA molecules can be involved. Multiple RNA interactions are also believed to be much more complex than pairwise interactions. Recently, multiple RNA interaction prediction has been formulated as a maximization problem. Here we extensively examine this optimization problem under several biologically meaningful interaction models. We present a polynomial time algorithm for the problem when the order of interacting RNAs is known and pseudoknot interactions are allowed; for the general problem without an assumed RNA order, we prove the NP-hardness for both variants (allowing and disallowing pseudoknot interactions), and present a constant ratio approximation algorithm for each of them.

TCS Journal 2014 Journal Article

Approximating the minimum independent dominating set in perturbed graphs

• Weitian Tong
• Randy Goebel
• Guohui Lin

We investigate the minimum independent dominating set in perturbed graphs g ( G, p ) of input graph G = ( V, E ), obtained by negating the existence of edges independently with a probability p > 0. The minimum independent dominating set (MIDS) problem does not admit a polynomial running time approximation algorithm with worst-case performance ratio of n 1 − ϵ for any ϵ > 0. We prove that the size of the minimum independent dominating set in g ( G, p ), denoted as i ( g ( G, p ) ), is asymptotically almost surely in Θ ( log ⁡ | V | ). Furthermore, we show that the probability of i ( g ( G, p ) ) ⩾ 4 | V | p is no more than 2 − | V |, and present a simple greedy algorithm of proven worst-case performance ratio 4 | V | p and with polynomial expected running time.

TCS Journal 2014 Journal Article

On the approximability of the exemplar adjacency number problem for genomes with gene repetitions

• Zhixiang Chen
• Bin Fu
• Randy Goebel
• Guohui Lin
• Weitian Tong
• Jinhui Xu
• Boting Yang
• Zhiyu Zhao

In this paper, we apply a measure, exemplar adjacency number, which complements and extends the well-studied breakpoint distance between two permutations, to measure the similarity between two genomes (or in general, between any two sequences drawn from the same alphabet). For two genomes G and H drawn from the same set of n gene families and containing gene repetitions, we consider the corresponding Exemplar Adjacency Number problem (EAN), in which we delete duplicated genes from G and H such that the resultant exemplar genomes (permutations) G and H have the maximum adjacency number. We obtain the following results. First, we prove that the one-sided 2-repetitive EAN problem, i. e. , when one of G and H is given exemplar and each gene occurs in the other genome at most twice, can be linearly reduced from the Maximum Independent Set problem. This implies that EAN does not admit any O ( n 0. 5 − ϵ ) -approximation algorithm, for any ϵ > 0, unless P = NP. This hardness result also implies that EAN, parameterized by the optimal solution value, is W[1]-hard. Secondly, we show that the two-sided 2-repetitive EAN problem has an O ( n 0. 5 ) -approximation algorithm, which is tight up to a constant factor.

TCS Journal 2013 Journal Article

Preface

• Guohui Lin

TCS Journal 2011 Journal Article

Size-constrained tree partitioning: Approximating the multicast k -tree routing problem

• Zhipeng Cai
• Randy Goebel
• Guohui Lin

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

TCS Journal 2011 Journal Article

The three column Bandpass problem is solvable in linear time

• Zhong Li
• Guohui Lin

The general Bandpass problem is NP-hard and was claimed to be NP-hard when the number of columns is three. Previously we designed a polynomial time row-stacking algorithm for the three column case, to produce a solution that is at most 1 less than the optimum. We show in this paper that for any bandpass number B ≥ 2, an optimal solution is always achievable in linear time.

TCS Journal 2009 Journal Article

A 3.4713-approximation algorithm for the capacitated multicast tree routing problem

• Zhipeng Cai
• Zhi-Zhong Chen
• Guohui Lin

Given an underlying communication network represented as an edge-weighted graph G = ( V, E ), a source node s ∈ V, a set of destination nodes D ⊆ V, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of 2089 + 77 80 + 5 4 ρ, where ρ denotes the best known approximation ratio for the Steiner minimum tree problem. Since ρ is about 1. 55 at the writing of the paper, the ratio achieved by our new algorithm is less than 3. 4713. In comparison, the previously best ratio was 8 5 + 5 4 ρ ≈ 3. 5375.

TCS Journal 2004 Journal Article

A space-efficient algorithm for sequence alignment with inversions and reversals

• Zhi-Zhong Chen
• Yong Gao
• Guohui Lin
• Robert Niewiadomski
• Yang Wang
• Junfeng Wu

A dynamic programming algorithm to find an optimal alignment for a pair of DNA sequences has been described by Schöniger and Waterman. The alignments use not only substitutions, insertions, and deletions of single nucleotides, but also inversions, which are the reversed complements, of substrings of the sequences. With the restriction that the inversions are pairwise non-intersecting, their proposed algorithm runs in O ( n 2 m 2 ) time and consumes O ( n 2 m 2 ) space, where n and m are the lengths of the input sequences, respectively. We develop a space-efficient algorithm to compute such an optimal alignment which consumes only O ( nm ) space within the same amount of time. Our algorithm enables the computation for a pair of DNA sequences of length up to 10, 000 to be carried out on an ordinary desktop computer. Simulation study is conducted to verify some biological facts about gene shuffling across species.

TCS Journal 2003 Journal Article

Approximation algorithms for NMR spectral peak assignment

• Zhi-Zhong Chen
• Tao Jiang
• Guohui Lin
• Jianjun Wen
• Dong Xu
• Jinbo Xu
• Ying Xu

We study a constrained bipartite matching problem where the input is a weighted bipartite graph G=(U, V, E), U is a set of vertices following a sequential order, V is another set of vertices partitioned into a collection of disjoint subsets, each following a sequential order, and E is a set of edges between U and V with non-negative weights. The objective is to find a matching in G with the maximum weight that satisfies the given sequential orders on both U and V, i. e. if u i+1 follows u i in U and if v j+1 follows v j in V, then u i is matched with v j if and only if u i+1 is matched with v j+1. The problem has recently been formulated as a crucial step in an algorithmic approach for interpreting NMR spectral data (IEEE Comput. Sci. Eng. 4 (2002) 50–62). The interpretation of NMR spectral data is known as a key problem in protein structure determination via NMR spectroscopy. Unfortunately, the constrained bipartite matching problem is NP-hard (IEEE Comput. Sci. Eng. 4 (2002) 50–62). We first propose a 2-approximation algorithm for the problem, which follows directly from the recent result of Bar-Noy et al. (Proc. 32nd ACM Symp. on Theory of Computing (STOC’00), 2000, pp. 735–744) on interval scheduling. However, our extensive experimental results on real NMR spectral data illustrate that the algorithm performs poorly in terms of recovering target-matching edges. We then propose another approximation algorithm that tries to take advantage of the “density” of the sequential order information in V. Although we are only able to prove an approximation ratio of 3 log 2 D for this algorithm, where D is the length of a longest string in V, the experimental results demonstrate that this new algorithm performs much better on real data, i. e. it is able to recover a large fraction of target-matching edges and the weight of its output matching is often in fact close to the maximum. We also prove that the problem is MAX SNP-hard, even if the input bipartite graph is unweighted. We further present an approximation algorithm for a nontrivial special case that breaks the ratio 2 barrier.