The interval ordering problem

DOI10.1016/J.DAM.2011.12.020zbMATH Open1243.90271arXiv1112.0534OpenAlexW2130436162MaRDI QIDQ423919FDOQ423919

Fabrice Talla Nobibon, Christoph Dürr, Gerhard J. Woeginger, Maurice Queyranne, Frits C. R. Spieksma

Publication date: 30 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: For a given set of intervals on the real line, we consider the problem of ordering the intervals with the goal of minimizing an objective function that depends on the exposed interval pieces (that is, the pieces that are not covered by earlier intervals in the ordering). This problem is motivated by an application in molecular biology that concerns the determination of the structure of the backbone of a protein. We present polynomial-time algorithms for several natural special cases of the problem that cover the situation where the interval boundaries are agreeably ordered and the situation where the interval set is laminar. Also the bottleneck variant of the problem is shown to be solvable in polynomial time. Finally we prove that the general problem is NP-hard, and that the existence of a constant-factor-approximation algorithm is unlikely.

Full work available at URL: https://arxiv.org/abs/1112.0534

Recommendations

• scientific article; zbMATH DE number 1305428
• On two open problems of 2-interval patterns
• Scheduling Split Intervals
• Interval graphs with side (and size) constraints
• The complexity of gene placement

zbMATH Keywords

NP-hardagreeable intervalsbottleneck problemexposed partlaminar intervals

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Dynamic programming (90C39)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the computation of protein backbones by using artificial backbones of hydrogens

Cited In (4)

• Ranking intervals under visibility constraints^∗
• Title not available (Why is that?)
• Interval Sorting
• Counting interval orders

This page was built for publication: The interval ordering problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q423919)