Search

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. [ABSTRACT FROM AUTHOR]

Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which has attracted attention of many scientists in algorithm design. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns out to be NP-Hard and Max-SNP-Hard. The best known approximation algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting which can achieve a asymptotic performance ratio 1.375. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 . [ABSTRACT FROM AUTHOR]