An FPTAS for Minimizing a Class of Low-Rank Quasi-Concave Functions over a Convex Set ∗

We consider the problem of minimizing a class of quasi-concave functions over a convex set. Quasi-concave functions are a generalization of concave functions and thus, NP-hard to minimize in general. We present a simple fully polynomial time approximation scheme (FPTAS) for minimizing a fairly gen-eral class of low-rank quasi-concave functions. Our algorithm is based on solving a polynomial number of linear minimization problems with appropriate objectives and computes a near-optimal solution that is an extreme point of the convex set. Therefore, it applies directly to combinatorial 0-1 problems for which the convex hull of feasible solutions is known, such as shortest paths, spanning trees and matchings in undirected graphs. Key words: Quasi-concave programming; non-linear programming; non-convex programming; poly-nomial approximation schemes.