The column-circular, subsets-selection problem: Complexity and solutions

In this paper we study the complexity of a new class of a problem that we call the column-circular, subsets-selection problem and we show that, under a special condition, it is a polynomially solvable problem. First, we show that the column-circular set-partitioning, the column-circular set-covering, and the column-circular set-packing problems, among others, are special cases of the problem considered here. Then we present some of its applications. It is also shown that the optimal solution of some of the special cases of the column-circular subsets-selection problem can be obtained by solving a bounded number of totally-unimodular, linear-programming, sub-problems. In the case of column-circular set-partitioning, set-packing and set-packing with under-cover penalties problems, each of these linear sub-problems can be transformed into a shortest path problem. We provide some dynamic programming algorithms to solve the sub-problems of the column-circular subsets-selection problem and its special cases. Finally, a procedure to minimize the number of sub-problems to be solved is described.