A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program (Q1821694)

This paper deals with the problem P of minimizing a quasiconcave function over a given feasible region. We first introduce an auxiliary problem P(\(\lambda)\) with a parametric vector \(\lambda\) such that, for an appropriate \(\lambda\), its optimal solution is also optimal to the original problem. Based on this, an approximation scheme for P is developed. If P(\(\lambda)\) is polynomially solvable, this becomes a polynomial time approximation scheme. In particular, we show that fully polynomial time approximation schemes can be developed for a large class of stochastic programming problems with 0-1 variables in which cost coefficients are subject to independent normal distributions, if their deterministic versions obtained by replacing cost coefficients by constants have polynomial time algorithms or fully polynomial time approximation schemes (e.g., problems of shortest path, assignment, minimum cut, 0-1 knapsack and minimum directed spanning tree).