Hardness and approximation of the asynchronous border minimization problem

Cindy Y. Li, Alexandru Popa, Prudence W.H. Wong, Fencol C.C. Yung

Research output: Contribution to journalArticle

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.

Original languageEnglish
Pages (from-to)101-117
Number of pages17
JournalDiscrete Applied Mathematics
Volume235
DOIs
Publication statusPublished - Jan 30 2018

Keywords

  • Approximation algorithms
  • Border length minimization
  • NP-hardness

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Hardness and approximation of the asynchronous border minimization problem'. Together they form a unique fingerprint.

  • Cite this