OPTIMIZATIONACADEMIC WEBSITE

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 […]

Comments Off on Matroid Bases with Cardinality Constraints on the Intersection

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 […]

Comments Off on Efficient Algorithms for the Recoverable (Robust) Selection Problem

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.

Comments Off on The Steiner Cycle and Path Cover Problem on Interval Graphs