Archives: Publications
Archives: Publications
Given two matroids and on a common ground set with base sets and , some integer , and two cost functions , we consider the optimization problem to find a basis and a basis minimizing cost subject to either a lower bound constraint , an upper bound constraint , or an equality constraint on the […]
Archives: Publications
We study the Recoverable Selection problem, a generalization of the well-studied classic Selection problem. Given an element set , two cost vectors and two parameters , we want to find sets such that and minimizing the cost . We show that a simple greedy algorithm solves this problem to optimality. By a detailed mathematical analysis […]
Archives: Publications
We present linear time algorithms for the Steiner path cover and Steiner cycle problems on interval graphs given as endpoint sorted lists. The main contribution is a lemma showing that backward steps to non-Steiner intervals are never necessary. Furthermore, we show how to integrate this modification to the deferred-query technique of Chang et al.