Hardness and approximation of the asynchronous border minimization problem



Li, Cindy Y, Popa, Alexandru, Wong, Prudence WH ORCID: 0000-0001-7935-7245 and Yung, Fencol CC
(2018) Hardness and approximation of the asynchronous border minimization problem. Discrete Applied Mathematics, 235. pp. 101-117.

[img] Text
border-journal-revised-v2.pdf - Author Accepted Manuscript

Download (287kB)

Abstract

We study a combinatorial problem arising from the microarray synthesis. The objective of the Border Minimization Problem (BMP) is to place a set of sequences in the array and to find an embedding of these sequences into a common supersequence such that the sum of the “border length” is minimized. A variant of the problem, called P-BMP, is that the placement is given and the concern is simply to find the embedding. An exponential time algorithm has been proposed for the problem but it is unknown whether the problem is NP-hard or not. In this paper, we give a comprehensive study of different variations of BMP by presenting NP-hardness proofs and approximation algorithms. We show that BMP, P-BMP, and 1D-BMP are all NP-hard and 1D-BMP is polynomial time solvable. The interesting implications include (i) the BMP is NP-hard regardless of the dimension (1D or 2D) of the array; (ii) the array dimension differentiates the complexity of the P-BMP; and (iii) for 1D array, whether placement is given differentiates the complexity of the BMP. Another contribution of the paper is devising approximation algorithms, and in particular, we present a randomized approximation algorithm for BMP with approximation ratio O(n1∕4log2n), where n is the total number of sequences.

Item Type: Article
Depositing User: Symplectic Admin
Date Deposited: 29 Aug 2017 07:51
Last Modified: 19 Jan 2023 06:56
DOI: 10.1016/j.dam.2017.08.025
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3009204