K-set (geometry) - Matroid Generalizations

Matroid Generalizations

The planar k-level problem can be generalized to one of parametric optimization in a matroid: one is given a matroid in which each element is weighted by a linear function of a parameter λ, and must find the minimum weight basis of the matroid for each possible value of λ. If one graphs the weight functions as lines in a plane, the k-level of the arrangement of these lines graphs as a function of λ the weight of the largest element in an optimal basis in a uniform matroid, and Dey showed that his O(nk1/3) bound on the complexity of the k-level could be generalized to count the number of distinct optimal bases of any matroid with n elements and rank k.

For instance, the same O(nk1/3) upper bound holds for counting the number of different minimum spanning trees formed in a graph with n edges and k vertices, when the edges have weights that vary linearly with a parameter λ. This parametric minimum spanning tree problem has been studied by various authors and can be used to solve other bicriterion spanning tree optimization problems.

However, the best known lower bound for the parametric minimum spanning tree problem is Ω(n α(k)), where α is the inverse Ackermann function, an even weaker bound than that for the k-set problem. For more general matroids, Dey's O(nk1/3) upper bound has a matching lower bound.