A setup heuristic for interval orders (Q1064975)

The setup minimization problem asks to determine a sharp lower bound for the number of incomparable adjacent pairs of elements that may occur in linear extensions of a given ordered set. This problem is known to be difficult in general. In particular, no efficient exact solution method is available for the class of interval orders. Taking advantage of a suitable decomposition property of this class, we present a simple greedy heuristic which can be shown to achieve never worse than twice the optimum. To date, the class of interval orders is the only class known which allows an efficient approximate solution but for which no efficient exact algorithm has been found.