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

We consider minimizing a class of low rank quasi-concave functions over a convex set and give a fully polynomial time approximation scheme (FPTAS) for the problem. The algorithm is based on a binary search for the optimal objective value which is guided by solving a polynomial number of linear minimization problems over the convex set with appropriate objective functions. Our algorithm gives a (1 + ∈)-approximate solution that is an extreme point of the convex set and therefore, has direct applications 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. Our results also extend to maximization of low-rank quasi-convex functions over a convex set.