TY - GEN

T1 - On the approximability of the maximum interval constrained coloring problem

AU - Canzar, Stefan

AU - Elbassioni, Khaled

AU - Elmasry, Amr

AU - Raman, Rajiv

N1 - Funding Information:
Part of the work was done while the first, third and forth authors were members of Max-Planck Institute. A. Elmasry is on leave from Alexandria University of Egypt. R. Raman’s research is supported by the Centre for Discrete Mathematics and its Applications (DIMAP) at University of Warwick, EPSRC award EP/D063191/1.

PY - 2010

Y1 - 2010

N2 - In the Maximum Interval Constrained Coloring problem, we are given 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.

AB - In the Maximum Interval Constrained Coloring problem, we are given 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.

UR - http://www.scopus.com/inward/record.url?scp=78650894343&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650894343&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17514-5_15

DO - 10.1007/978-3-642-17514-5_15

M3 - Conference contribution

AN - SCOPUS:78650894343

SN - 3642175163

SN - 9783642175169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 168

EP - 179

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -