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

Fingerprint

Hardness
Minimization Problem
Approximation
Approximation algorithms
Approximation Algorithms
NP-complete problem
Differentiate
Placement
Computational complexity
NP-hardness
Exponential time
Combinatorial Problems
Randomized Algorithms
Microarrays
Microarray
Polynomial time
Polynomials
Synthesis
Unknown

Keywords

  • Approximation algorithms
  • Border length minimization
  • NP-hardness

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this

Hardness and approximation of the asynchronous border minimization problem. / Li, Cindy Y.; Popa, Alexandru; Wong, Prudence W.H.; Yung, Fencol C.C.

In: Discrete Applied Mathematics, Vol. 235, 30.01.2018, p. 101-117.

Research output: Contribution to journalArticle

Li, Cindy Y. ; Popa, Alexandru ; Wong, Prudence W.H. ; Yung, Fencol C.C. / Hardness and approximation of the asynchronous border minimization problem. In: Discrete Applied Mathematics. 2018 ; Vol. 235. pp. 101-117.
@article{a0c58dd3845d45bba37d99b33c0402ff,
title = "Hardness and approximation of the asynchronous border minimization problem",
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.",
keywords = "Approximation algorithms, Border length minimization, NP-hardness",
author = "Li, {Cindy Y.} and Alexandru Popa and Wong, {Prudence W.H.} and Yung, {Fencol C.C.}",
year = "2018",
month = "1",
day = "30",
doi = "10.1016/j.dam.2017.08.025",
language = "English",
volume = "235",
pages = "101--117",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

TY - JOUR

T1 - Hardness and approximation of the asynchronous border minimization problem

AU - Li, Cindy Y.

AU - Popa, Alexandru

AU - Wong, Prudence W.H.

AU - Yung, Fencol C.C.

PY - 2018/1/30

Y1 - 2018/1/30

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Border length minimization

KW - NP-hardness

UR - http://www.scopus.com/inward/record.url?scp=85030542028&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85030542028&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2017.08.025

DO - 10.1016/j.dam.2017.08.025

M3 - Article

VL - 235

SP - 101

EP - 117

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -