Geometric lower bounds for parametric matroid optimization

David Eppstein

*Discrete & Computational Geometry* 20:463–476, 1998

*Mathematical Reviews* 99h:90082, 1999

Reviewed by Jesús A. De Loera

The author deduces some results on matroid optimization by using geometric techniques. For example, the following lower bounds are proved, using their relation to polygon arrangements and lower envelopes of line segments: (1) There can be $\Omega (nr\sp {1/3})$ different minimum weight bases in a matroid with $n$ elements, rank $r$ and element weights linearly varying with time. (2) There can be $\Omega (m \alpha(n))$ different minimum spanning trees in a graph with $m$ edges, $n$ vertices, and edge weights linearly varying with time, where $\alpha(n)$ denotes the inverse Ackermann function. Recently, T. K. Dey [Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 373--382; MR 98k:52018] obtained an $O(nr\sp {1/3})$ upper bound on the number of base changes in a parametric matroid optimization problem, that matches the lower bound presented in this article.