Mathematical Reviews 99h:90082

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.

Fano Experimental Web Server, D. Eppstein, School of Information & Computer Science, UC Irvine
Made on a Mac Valid XHTML 1.0!