Tropical Kirchhoff's formula and postoptimality in matroid
optimization
S. Jukna and H. Seiwert
Abstract
Given an assignment of real weights to the ground elements of a matroid, the min-max weight of an element e
is the minimum, over all circuits containing e, of the maximum weight of an element in that circuit with the
element e removed. We use this concept to establish structural results for the minimum weight basis problem:
detecting the persistence of elements, determining the new optimal value when the weight of a single element
is arbitrarily perturbed, as well as when an element is contracted or deleted.
This latter result gives the tropical (min,+,-) analogue of the classical arithmetic (+,x,/) Kirchhoff's effective
conductance formula for electrical networks.
Kirchhoff.pdf