On the approximability of the maximum interval constrained coloring problem

Stefan Canzar, Khaled Elbassioni, Amr Elmasry, Rajiv Raman

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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(|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.

Original languageEnglish (US)
Pages (from-to)57-72
Number of pages16
JournalDiscrete Optimization
Volume27
DOIs
StatePublished - Feb 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On the approximability of the maximum interval constrained coloring problem'. Together they form a unique fingerprint.

Cite this