An Approximation Algorithm for Combinatorial Optimization Problems with Two Parameters
David Blokh, Gregory Gutin · 1995
We call a minimum cost restricted time combinatorial optimization (MCRT) problem any problem that has a finite set P , finite family S of subsets of P , nonnegative threshold h, and two non-negative real-valued functions y : P!R+ (say, cost) and x : P!R+ (say, time). One seeks a solution F 2 S with y(F ) = minfy(F ) : F 2 S; x(F ) hg, where z(G) = P g2G z(g) for every z 2 fx; yg and G 2 S. We also assume that for the corresponding minimum cost problem there is an efficient exact or approximation algorithm. We describe an approximation algorithm for any MCRT problem. Though our algorithm is not polynomial in general, we provide some theoretical and practical evidence that the algorithm may be fairly fast in many cases.