An approach for proving lower bounds: solution of Gilbert-Pollak´s conjecture on Steiner ratio

A family of finitely many continuous functions on a polytope X , namely {g_i(x)}_i∈I, is considered, and the problem of minimizing the function f(x)=max_i∈Ig_i( x) on X is treated. It is shown that if every g _i(x) is a concave function, then the minimum value of f(x) is achieved at finitely many special points in X. As an application, a long-standing problem about Steiner minimum trees and minimum spanning trees is solved. In particular, if P is a set of n points on the Euclidean plane and L_s(P) and L_m( P) denote the lengths of a Steiner minimum tree and a minimum spanning tree on P, respectively, it is proved that, for any P, L_S(P)⩾√3L _m(P)/2, as conjectured by E.N. Gilbert and H.O. Pollak (1968)