Canzar, Stefan; Elbassioni, Khaled; Elmasry, Amr; Raman, Rajiv
(2018):
On the approximability of the maximum interval constrained coloring problem.
In: Discrete Optimization, Vol. 27: pp. 5772

Full text not available from 'Open Access LMU'.
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 kdimensional 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 NPhard 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 maximumweight solution. We show further that, even for k = 2, the problem remains APXhard.