Tropical Kirchhoff's formula and postoptimality in matroid optimization

DOI10.1016/J.DAM.2020.09.018MaRDI QIDQ2217458zbMATH OpenOpenAlexFDO

Authors Hannes Seiwert, Stasys Jukna

Publication date 29 December 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.07630

zbMATH Keywords

optimizationpersistencypostoptimalitysensitivityweighted matroid

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 62768
• A new exchange property for matroids and its application to max-min-problems
• Algorithms for measuring perturbality in matroid optimization
• On a discrete optimization problem
• Geometric lower bounds for parametric matroid optimization

Cites work

• A THEOREM ON INDEPENDENCE RELATIONS
• Bottleneck extrema
• Comments on bases in dependence structures
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 62768 (Why is no real title available?)
• Matroids and the greedy algorithm
• Optimal assignments in an ordered set: An application of matroid theory
• Persistency in combinatorial optimization problems on matroids
• Some properties of basic families of subsets

This page was built for publication: Tropical Kirchhoff's formula and postoptimality in matroid optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2217458)