Approximating the Interval Constrained Coloring Problem

Lade...
Vorschaubild
Dateien
Karrenbauer etal.pdf
Karrenbauer etal.pdfGröße: 423.11 KBDownloads: 591
Datum
2008
Autor:innen
Althaus, Ernst
Canzar, Stefan
Elbassioni, Khaled
Mestre, Julián
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
GUDMUNDSSON, Joachim, ed.. Algorithm Theory – SWAT 2008. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 210-221. Lecture Notes in Computer Science. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-69900-2. Available under: doi: 10.1007/978-3-540-69903-3_20
Zusammenfassung

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 develop a quasi-polynomial-time approximation scheme for a variant of our problem where we are asked to find a coloring satisfying as many fragments as possible.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690ALTHAUS, Ernst, Stefan CANZAR, Khaled ELBASSIONI, Andreas KARRENBAUER, Julián MESTRE, 2008. Approximating the Interval Constrained Coloring Problem. In: GUDMUNDSSON, Joachim, ed.. Algorithm Theory – SWAT 2008. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 210-221. Lecture Notes in Computer Science. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-69900-2. Available under: doi: 10.1007/978-3-540-69903-3_20
BibTex
@inproceedings{Althaus2008Appro-6068,
  year={2008},
  doi={10.1007/978-3-540-69903-3_20},
  title={Approximating the Interval Constrained Coloring Problem},
  isbn={978-3-540-69900-2},
  issn={0302-9743},
  publisher={Springer Berlin Heidelberg},
  address={Berlin, Heidelberg},
  series={Lecture Notes in Computer Science},
  booktitle={Algorithm Theory – SWAT 2008},
  pages={210--221},
  editor={Gudmundsson, Joachim},
  author={Althaus, Ernst and Canzar, Stefan and Elbassioni, Khaled and Karrenbauer, Andreas and Mestre, Julián}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6068">
    <dc:creator>Elbassioni, Khaled</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Elbassioni, Khaled</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6068"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6068/1/Karrenbauer%20etal.pdf"/>
    <dcterms:issued>2008</dcterms:issued>
    <dc:contributor>Canzar, Stefan</dc:contributor>
    <dc:format>application/pdf</dc:format>
    <dc:rights>terms-of-use</dc:rights>
    <dc:creator>Canzar, Stefan</dc:creator>
    <dc:language>eng</dc:language>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
    <dc:contributor>Althaus, Ernst</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6068/1/Karrenbauer%20etal.pdf"/>
    <dc:creator>Karrenbauer, Andreas</dc:creator>
    <dcterms:abstract xml:lang="eng">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).&lt;br /&gt;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 develop a quasi-polynomial-time approximation scheme for a variant of our problem where we are asked to find a coloring satisfying as many fragments as possible.</dcterms:abstract>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:09:10Z</dcterms:available>
    <dc:contributor>Mestre, Julián</dc:contributor>
    <dc:contributor>Karrenbauer, Andreas</dc:contributor>
    <dcterms:bibliographicCitation>First publ. in: Algorithm theory - SWAT 2008 : 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4, 2008 ; proceedings / Joachim Gudmundsson (ed.). - Berlin [u.a.] : Springer, 2008, pp. 210-221</dcterms:bibliographicCitation>
    <dc:creator>Althaus, Ernst</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Mestre, Julián</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:09:10Z</dc:date>
    <dcterms:title>Approximating the Interval Constrained Coloring Problem</dcterms:title>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen