On the solution bound of two-sided scaffold filling

Abstract In this paper, we propose an algorithm which approximates the Two-Sided Scaffold Filling problem to a performance ratio 1.4 + e . 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 + e is obtained by comparing the bound of such an optimal solution with the solution of our algorithm.