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

Fayez F. Boctor

doi:10.1016/S0305-0548(99)00058-1

Return

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

2000-04-01

PRE

Fayez F. Boctor *

Jacques Renaud

DOI：10.1016/S0305-0548(99)00058-1

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

routing

scheduling

complexity

set-covering

set-packing

set-partitioning

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.