Daming Zhu

TCS Journal 2024 Journal Article

New approximation algorithms for RNA secondary structures prediction problems by local search

• Aizhong Zhou
• Haodi Feng
• Jiong Guo
• Haitao Jiang
• Nan Liu
• Binhai Zhu
• Daming Zhu

This paper investigates two combinatorial problems from RNA secondary structure prediction with arbitrary pseudoknots. Given a RNA sequence and a set of base pairs, two parallel and adjacent base pairs constitute a stacking. The Maximum Stacking Base Pairs problem (MSBP) aims at finding a maximum number of based pairs, all of which form stackings, while the Maximum Base Pair Stackings problem (MBPS) is to find a maximum number of stackings. Both problems are NP-hard. We present two new approximation algorithms for the two problems by local search methods. For MSBP, the approximation factor is improved from 5 2 to 7 3; as for the MBPS, the approximation factor is improved from 8 3 to 5 2.

TCS Journal 2022 Journal Article

Approximation algorithms for sorting by bounded singleton moves

• Shengjun Xie
• Haodi Feng
• Haitao Jiang
• Daming Zhu

Sorting permutations by block moves is a fundamental combinatorial problem in genome rearrangements. The classic block move operation is called transposition, which switches two adjacent blocks, or equivalently, moves a block to some other position. But large blocks movement rarely occurs during real evolutionary events. A natural restriction of transposition is to bound the length of the blocks to be switched. In this paper, we investigate the problem called sorting by bounded singleton moves, where one of the switched blocks is exactly a singleton while the other is of length at most c. This problem generalizes the sorting by short block moves problem proposed by Heath and Vergara [11], which requires the total length of blocks switched bounded by 3. When c = 3, we devise a 9 5 -approximation algorithm for an arbitrary permutation, and a 12 7 -approximation algorithm for a woven double-strip permutation. Our algorithms can be slightly extended to solve the sorting by c-bounded singleton moves problem for any constant c ≥ 3, guaranteeing an approximation factor of 3 c 5 and 4 c 7 for arbitrary permutations and woven double-strip permutations respectively, just by exploiting a new lower bound of sorting by c-bounded singleton moves.

TCS Journal 2021 Journal Article

Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs

• Peiyan Zhou
• Haitao Jiang
• Daming Zhu
• Binhai Zhu

The Maximum Vertex Coverage problem (abbreviated as MVC) is to maximum the number of edges covered by a set of vertices of size exactly K on a graph. This problem is the dual of the vertex cover problem and has attracted a lot of interests in the literature of approximation algorithm. So far, the best approximation factor for the MVC problem is 3/4, which is obtained using an LP-rounding method. The main results of this paper are new approximation algorithms for MVC on cubic graphs and 3-bounded graphs (the vertex degrees are at most 3). The approximation factor on cubic graphs is 79/90 (≈0. 878), which is tight by analyzing the existence of a feasible solution for a linear programming system. This algorithm can also be extended to 3-bounded graphs and guarantees an approximation factor of 19/24 (≈0. 792).

TCS Journal 2021 Journal Article

On the solution bound of two-sided scaffold filling

• Jingjing Ma
• Daming Zhu
• Haitao Jiang
• Binhai Zhu

In this paper, we propose an algorithm which approximates the Two-Sided Scaffold Filling problem to a performance ratio 1. 4 + ε. This is achieved through a deep investigation of the optimal solution structure of Two-Sided Scaffold Filling. We make use of a relevant graph aiming at a solution of a Two-Sided Scaffold Filling instance, and evaluate the optimal solution value by the number of connected components in this graph. We show that an arbitrary optimal solution can be transformed into one whose relevant graph admits connected components that are available to compare with the solution of our algorithm in terms of their values. The performance ratio 1. 4 + ε is obtained by comparing the bound of such an optimal solution with the solution of our algorithm.

TCS Journal 2018 Journal Article

Can a breakpoint graph be decomposed into none other than 2-cycles?

• Lianrong Pu
• Yu Lin
• Daming Zhu
• Haitao Jiang

Breakpoint graph has been widely used as a key data structure in algorithm design for genome rearrangements. The problem of breakpoint graph cycle decomposition, which asks for a largest collection of edge-disjoint cycles, is crucial in computing rearrangement distances between genomes. This problem is NP-hard, and can be approximated to 1. 4193 + ϵ. It is still open for deciding whether a breakpoint graph can admit a cycle decomposition with none other than 2-cycles. In this paper, we present a linear time algorithm to detect whether a breakpoint graph can be decomposed into none other than 2-cycles.

TCS Journal 2018 Journal Article

Preface

• Daming Zhu
• Sergey Bereg

TCS Journal 2017 Journal Article

Approximating Max NAE-k-SAT by anonymous local search

• Aiyong Xian
• Kaiyuan Zhu
• Daming Zhu
• Lianrong Pu
• Hong Liu

A clause is not-all-equal satisfied if it has at least one literal assigned with true and one literal assigned with false. Max NAE-SAT is given by a boolean variable set U and a clause set C, asks to find an assignment of U, such that the number of not-all-equal satisfied clauses in C is maximized. Max NAE-SAT turns into Max NAE-k-SAT if each clause contains exactly k literals. Local search has long been used in various SAT solvers. However, little has been done on local search to approximate Max NAE-k-SAT. Moreover, it is still open for what a quantitative bound could Max NAE-k-SAT be approximated to, at best. In this paper, we propose a local search algorithm which can approximate Max NAE-k-SAT to 2 k − 1 2 k − 1 − 1 for each fixed k ≥ 2. Then we show that Max NAE-k-SAT cannot be approximated within 2 k − 1 2 k − 1 − 1 in polynomial time, if P ≠ NP. The algorithm for Max NAE-k-SAT can be extended to approximate Max NAE-SAT where each clause contains at least k literals to 2 k − 1 2 k − 1 − 1. Using the algorithm for Max NAE-SAT where each clause contains at least k literals, we present a new algorithm to approximate Max-SAT where each clause contains at least k literals to 2 k 2 k − 1.

TCS Journal 2017 Journal Article

Improved algorithms for intermediate dataset storage in a cloud-based dataflow

• Jie Cheng
• Daming Zhu
• Binhai Zhu

In order to run a dataflow with as low cost as possible, it is often faced with deciding which data-sets in a data-set sequence should be stored, with the rest regenerated. The Intermediate Data-set Storage problem arises from this situation. The current best algorithm for this problem takes O ( n 4 ) time. In this paper, we present two improved algorithms for this problem, the first of which can achieve a time complexity O ( n 2 ), the second of which O ( r n ), where n is the number of data-sets in a dataflow, r is a numerical number which indicates how large it is for the maximum storage cost to be divided by the minimum computation cost in the dataflow.

TCS Journal 2015 Journal Article

A factor-(1.408 +ε) approximation for sorting unsigned genomes by reciprocal translocations

• Haitao Jiang
• Lusheng Wang
• Binhai Zhu
• Daming Zhu

Sorting genomes by translocations is a classic combinatorial problem in genome rearrangements. The translocation distance for signed genomes can be computed exactly in polynomial time, but for unsigned genomes the problem becomes NP-hard and the current best approximation ratio is 1. 5 + ε. In this paper, we investigate the problem of sorting unsigned genomes by translocations. Firstly, we propose a tighter lower bound of the optimal solution by analyzing some special sub-permutations; then, by exploiting the two well-known algorithms for approximating the maximum independent set on graphs with a bounded degree and for set packing with sets of bounded size, we devise a new polynomial-time approximation algorithm, improving the approximation ratio to 1. 408 + ε, where ε = O ( 1 / log ⁡ n ).

TCS Journal 2013 Journal Article

Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems

• Hong Liu
• Daming Zhu

Elections are an important preference aggregation model in a variety of areas. Given a pool of n potential voters, the chair may strategically selecting k voters from the pool to feed to an election system, in order to control the final outcome of the election system. This type of control, called control by voter selection, is closely related to two already well-studied types of control, i. e. , control by voter addition and control by voter deletion. This paper studies parameterized complexity of control by voter selection for five election systems, i. e. , Maximin, Copeland α ( 0 ⩽ α ⩽ 1 ), Borda, Bucklin, and Approval. We prove that constructive/destructive control of Maximin, constructive/destructive control of Copeland α, constructive control of Borda, constructive control of Bucklin, and constructive control of Approval are all W[2]-hard, with respect to the parameter “number of selected voters”.

TCS Journal 2013 Journal Article

Sorting genomes by generalized translocations

• Xiao Yin
• Daming Zhu

Translocation is a prevalent rearrangement event in the evolution of multi-chromosomal species which exchanges ends between two chromosomes. A translocation is reciprocal if none of the exchanged ends is empty; otherwise, non-reciprocal. The problem of sorting by translocations asks to find a shortest sequence of translocations transforming one genome into another. The problem of sorting by reciprocal translocations can be solved in polynomial-time. Several algorithms have been developed for reciprocal translocation sorting. They can only be applied to a pair of genomes having the same set of chromosome ends. Such a restriction can be removed if non-reciprocal translocations are also allowed. In this paper, we show how to extend the algorithm for sorting by reciprocal translocations to include non-reciprocal translocations, allowing us to compare genomes containing different chromosome ends. We call this problem sorting by generalized translocations. We present a polynomial algorithm for this problem. At a conceptual level, there is some similarity between our algorithm and the algorithm developed by Hannenhalli which is used to sort genomes by reversals and translocations.

TCS Journal 2012 Journal Article

A ( 1 + ε )-approximation algorithm for sorting by short block-moves

• Haitao Jiang
• Daming Zhu
• Binhai Zhu

Sorting permutations by operations such as reversals and block-moves has received much attention because of its applications in the study of genome rearrangements. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. In this paper, we investigate the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation, and devise a ( 1 + ε )-approximation algorithm for this problem, where ε is the number of elements divided by the number of inversions in the permutation. The algorithm mostly relies on a new structure in the permutation graph called an umbrella, which can be optimally sorted in O ( n 2 ) time.

TCS Journal 2009 Journal Article

Parameterized computational complexity of control problems in voting systems

• Hong Liu
• Haodi Feng
• Daming Zhu
• Junfeng Luan

Voting systems are common tools in a variety of areas. This paper studies parameterized computational complexity of control of Plurality, Condorcet and Approval voting systems, respectively. The types of controls considered include adding or deleting candidates or voters, under constructive or destructive setting. We obtain the following results: (1) constructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter “number of added candidates”, (2) destructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter “number of added candidates”, (3) constructive control by adding voters in Condorcet voting is W[1]-hard with respect to the parameter “number of added voters”, (4) constructive control by deleting voters in Condorcet voting is W[1]-hard with respect to the parameter “number of deleted voters”, (5) constructive control by adding voters in Approval voting is W[1]-hard with respect to the parameter “number of added voters”, and (6) constructive control by deleting voters in Approval voting is W[2]-hard with respect to the parameter “number of deleted voters”.

TCS Journal 2006 Journal Article

On the complexity of unsigned translocation distance

• Daming Zhu
• Lusheng Wang

Translocation is one of the basic operations for genome rearrangement. Translocation distance is the minimum number of translocations required to transform one genome into the other. In this paper, we show that computing the translocation distance for unsigned genomes is NP-hard. Moreover, we show that approximating the translocation distance for unsigned genomes within ratio 1. 00017 is NP-hard.