### 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(n^{1∕4}log^{2}n), where n is the total number of sequences.

Original language | English |
---|---|

Pages (from-to) | 101-117 |

Number of pages | 17 |

Journal | Discrete Applied Mathematics |

Volume | 235 |

DOIs | |

Publication status | Published - Jan 30 2018 |

### Fingerprint

### Keywords

- Approximation algorithms
- Border length minimization
- NP-hardness

### ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

### Cite this

*Discrete Applied Mathematics*,

*235*, 101-117. https://doi.org/10.1016/j.dam.2017.08.025

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

Research output: Contribution to journal › Article

*Discrete Applied Mathematics*, vol. 235, pp. 101-117. https://doi.org/10.1016/j.dam.2017.08.025

}

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 -