Abstract
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(root vertical bar OPT vertical bar)-approximation algorithm, where OPT is the smallest cardinality maximum-weight solution. We show further that, even for k = 2, the problem remains APX-hard.
Item Type: | Journal article |
---|---|
Faculties: | Chemistry and Pharmacy > Department of Biochemistry |
Subjects: | 500 Science > 540 Chemistry |
ISSN: | 1572-5286 |
Language: | English |
Item ID: | 67191 |
Date Deposited: | 19. Jul 2019, 12:22 |
Last Modified: | 04. Nov 2020, 13:49 |