کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871656 1440188 2018 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hardness and approximation of the asynchronous border minimization problem
ترجمه فارسی عنوان
سختی و تقریبی مشکل به حداقل رساندن مرز ناهمزمان
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 235, 30 January 2018, Pages 101-117
نویسندگان
, , , ,