%0 Journal Article %A Goyal, Vineet %A Ravi, Ramamoorthi %D 2009 %T An FPTAS for Minimizing a Class of Low-Rank Quasi-Concave Functions over a Convex Set %U https://kilthub.cmu.edu/articles/journal_contribution/An_FPTAS_for_Minimizing_a_Class_of_Low-Rank_Quasi-Concave_Functions_over_a_Convex_Set/6703709 %R 10.1184/R1/6703709.v1 %2 https://kilthub.cmu.edu/ndownloader/files/12232709 %K Quasi-concave programming %K non-linear programming %K non-convex programming %K polynomial approximation schemes %X 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. %I Carnegie Mellon University