An approximate algorithm for combinatorial optimization problems with two parameters

Abstract

We call a minimum time combinatorial optimization (MCRT) problem any problem that has a finite set P, finite family S of subsets of P, non-negative threshold h, and two non-negative real-valued functions y: P - R+ (say, cost) and x:P - R+ (say, time). We describe a very simple approximate algorithm for any MCRT problem. Though our algorithm is not polynomial in general, we provide some evidence that the algorithm may be fairly fast in many cases.