Name
Title | ||
|---|---|---|
An approach for proving lower bounds: solution of Gilbert-Pollak's conjecture on Steiner ratio |
Abstract | ||
|---|---|---|
A family of finitely many continuous functions on a polytope X, namely (g/sub i/(x))/sub i in I/, is considered, and the problem of minimizing the function f(x)=max/sub i in I/g/sub i/(x) on X is treated. It is shown that if every g/sub 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/sub s/(P) and L/sub 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/sub S/(P)or= square root 3L/sub m/(P)/2, as conjectured by E.N. Gilbert and H.O. Pollak (1968). |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1109/FSCS.1990.89526 | St. Louis, MO |
Keywords | Field | DocType |
continuous function,sub i,minimum value,n point,long-standing problem,sub m,euclidean plane,polytope x,steiner minimum tree,concave function,lower bound,steiner ratio,np hard problem,minimum spanning tree,computer science,continuous functions,polytope,steiner trees,minimisation,mathematics | Continuous function,Discrete mathematics,Combinatorics,Steiner tree problem,Concave function,Polytope,Spanning tree,Square root,Conjecture,Mathematics,Minimum spanning tree | Conference |
ISBN | Citations | PageRank |
0-8186-2082-X | 25 | 11.08 |
References | Authors | |
3 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| D.-Z. Du | 1 | 219 | 52.53 |
| F. K. Hwang | 2 | 332 | 100.54 |