کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7543469 | 1489488 | 2018 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the approximability of the maximum interval constrained coloring problem
ترجمه فارسی عنوان
در تقریبی بودن حداکثر فاصله رنگی مشکل محدود شده است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
چکیده انگلیسی
In the Maximum Interval Constrained Coloring problem, we are given a set of vertices and a set of intervals on a line and a k-dimensional requirement vector for each interval, specifying how many vertices of each of k colors should appear in the interval. The objective is to color the vertices of the line with k colors so as to maximize the total weight of intervals for which the requirement is satisfied. This NP-hard combinatorial problem arises in the interpretation of data on protein structure emanating from experiments based on hydrogen/deuterium exchange and mass spectrometry. For constant k, we give a factor O(|Opt|)-approximation algorithm, where Opt is the smallest cardinality maximum-weight solution. We show further that, even for k=2, the problem remains APX-hard.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 27, February 2018, Pages 57-72
Journal: Discrete Optimization - Volume 27, February 2018, Pages 57-72
نویسندگان
Stefan Canzar, Khaled Elbassioni, Amr Elmasry, Rajiv Raman,