Computational Complexity of the Interval Ordering Problem
For researchers in computational complexity and bioinformatics, this work provides a near-complete characterization of the problem's tractability, though the results are incremental as they refine existing complexity bounds.
The paper studies an interval ordering problem from bioinformatics, developing a dynamic programming approach that solves it with O(2^n poly(n)) oracle calls. It yields polynomial-time algorithms for subadditive or superadditive cost functions, answering an open question for f(x)=2^x, and proves a lower bound of 2^{n-1} and NP-hardness for restricted classes, narrowing the complexity gap.
We study an interval ordering problem introduced by Dürr et al. [Discrete Appl. Math. 2012] which is motivated by applications in bioinformatics. The task is to order a given set of n intervals with the goal of minimizing a certain objective which is defined via a given cost function $f$ which assigns a cost to the exposed part of each interval (that is, the pieces not covered by previous intervals). We develop a dynamic programming approach which solves the problem with $O(2^n\text{poly}(n))$ oracle calls to $f$ and arithmetic operations. Moreover, our approach yields polynomial-time algorithms for all cost functions $f$ such that $f-f(0)$ is subadditive or superadditive. This answers an open question for the function $f(x)=2^x$. We contrast these results by proving a running time lower bound of $2^{n-1}$ for any algorithm that solves the problem for every function $f$ (with oracle access only) and further proving NP-hardness for very restricted classes of functions. Thus, we significantly narrow the gap regarding the computational complexity of the problem.