论文标题
热带基尔chhoff的配方和术后术中的术后优化
Tropical Kirchhoff's Formula and Postoptimality in Matroid Optimization
论文作者
论文摘要
鉴于将真实权重分配给原始元素的地面元素，因此，地面元素$ e $的最小值是最低的，对于所有包含$ e $的电路，该电路中元素的最大重量是该电路中元素$ e $的最大权重。我们使用此概念来回答以下结构性问题，以解决最小重量基础问题。在给定的加权下（属于全部或不属于最佳基础）的哪些元素持续存在？在保留最佳基础最优性的同时，允许使用哪些重量？当单个接地元件的重量更改或接地元素被签约或删除时，基本的最小重量如何变化？我们对后一个问题的回答给出了Kirchhoff的算术（+，X，/）的热带（最小，+， - ）类似物的有效电导公式。
Given an assignment of real weights to the ground elements of a matroid, the min-max weight of a ground 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 answer the following structural questions for the minimum weight basis problem. Which elements are persistent under a given weighting (belong to all or to none of the optimal bases)? What changes of the weights are allowed while preserving optimality of optimal bases? How does the minimum weight of a basis change when the weight of a single ground element is changed, or when a ground element is contracted or deleted? Our answer to this latter question gives the tropical (min,+,-) analogue of Kirchhoff's arithmetic (+,x,/) effective conductance formula for electrical networks.
