Goyal, Vineet Ravi, Ramamoorthi 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. Quasi-concave programming;non-linear programming;non-convex programming;polynomial approximation schemes 2009-10-01
    https://kilthub.cmu.edu/articles/journal_contribution/An_FPTAS_for_Minimizing_a_Class_of_Low-Rank_Quasi-Concave_Functions_over_a_Convex_Set/6703709
10.1184/R1/6703709.v1