Home > Research > Publications & Outputs > On complete classes of valuated matroids

Links

Text available via DOI:

View graph of relations

On complete classes of valuated matroids

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published
Close
Publication date5/01/2022
Host publicationProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
EditorsNikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee
PublisherSIAM PUBLICATIONS
Pages67-89
Number of pages23
ISBN (electronic)9781611977073
<mark>Original language</mark>English

Abstract

We characterize a rich class of valuated matroids, called R-minor valuated matroids that includes the indicator functions of matroids, and is closed under operations such as taking minors, duality, and induction by network. We exhibit a family of valuated matroids that are not R-minor based on sparse paving matroids. Valuated matroids are inherently related to gross substitute valuations in mathematical economics. By the same token we refute the Matroid Based Valuation Conjecture by Ostrovsky and Paes Leme (Theoretical Economics 2015) asserting that every gross substitute valuation arises from weighted matroid rank functions by repeated applications of merge and endowment operations. Our result also has implications in the context of Lorentzian polynomials: it reveals the limitations of known construction operations.