caa a22 4500 445805471 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9406-0 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9406-0 Approximation Algorithms for the Interval Constrained Coloring Problem [Elektronische Daten] [Ernst Althaus, Stefan Canzar, Khaled Elbassioni, Andreas Karrenbauer, Julián Mestre] We consider the interval constrained coloring problem, which appears in the interpretation of experimental data in biochemistry. Monitoring hydrogen-deuterium exchange rates via mass spectroscopy experiments is a method used to obtain information about protein tertiary structure. The output of these experiments provides data about the exchange rate of residues in overlapping segments of the protein backbone. These segments must be re-assembled in order to obtain a global picture of the protein structure. The interval constrained coloring problem is the mathematical abstraction of this re-assembly process. The objective of the interval constrained coloring problem is to assign a color (exchange rate) to a set of integers (protein residues) such that a set of constraints is satisfied. Each constraint is made up of a closed interval (protein segment) and requirements on the number of elements that belong to each color class (exchange rates observed in the experiments). We show that the problem is NP-complete for arbitrary number of colors and we provide algorithms that given a feasible instance find a coloring that satisfies all the coloring requirements within ±1 of the prescribed value. In light of our first result, this is essentially the best one can hope for. Our approach is based on polyhedral theory and randomized rounding techniques. Furthermore, we consider a variant of the problem where we are asked to find a coloring satisfying as many fragments as possible. If we relax the coloring requirements by a small factor of (1+ε), we propose an algorithm that finds a coloring "satisfying” this maximum number of fragments and that runs in quasi-polynomial time if the number of colors is polylogarithmic. Springer Science+Business Media, LLC, 2010 Approximation algorithms nationallicence Coloring problems nationallicence LP rounding nationallicence Althaus Ernst Johannes Gutenberg-Universität, Mainz, Germany aut Canzar Stefan Centrum Wiskunde & Informatica, Amsterdam, The Netherlands aut Elbassioni Khaled Max-Planck-Institut für Informatik, Saarbrücken, Germany aut Karrenbauer Andreas Institute of Mathematics, EPFL, Lausanne, Switzerland aut Mestre Julián Max-Planck-Institut für Informatik, Saarbrücken, Germany aut Algorithmica Springer-Verlag 61/2(2011-10-01), 342-361 0178-4617 61:2<342 2011 61 453 https://doi.org/10.1007/s00453-010-9406-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9406-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Althaus Ernst Johannes Gutenberg-Universität, Mainz, Germany aut NATIONALLICENCE 700 1- Canzar Stefan Centrum Wiskunde & Informatica, Amsterdam, The Netherlands aut NATIONALLICENCE 700 1- Elbassioni Khaled Max-Planck-Institut für Informatik, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Karrenbauer Andreas Institute of Mathematics, EPFL, Lausanne, Switzerland aut NATIONALLICENCE 700 1- Mestre Julián Max-Planck-Institut für Informatik, Saarbrücken, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 342-361 0178-4617 61:2<342 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer