Standard
On complete classes of valuated matroids. / Husic, Edin; Loho, Georg
; Smith, Ben et al.
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ed. / Nikhil Bansal; Christian Coester; Ravi Kumar; Manish Purohit; Erik Vee. SIAM PUBLICATIONS, 2022. p. 67-89.
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Harvard
Husic, E, Loho, G
, Smith, B & Vegh, LA 2022,
On complete classes of valuated matroids. in N Bansal, C Coester, R Kumar, M Purohit & E Vee (eds),
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM PUBLICATIONS, pp. 67-89.
https://doi.org/10.1137/1.9781611977073.4APA
Husic, E., Loho, G.
, Smith, B., & Vegh, L. A. (2022).
On complete classes of valuated matroids. In N. Bansal, C. Coester, R. Kumar, M. Purohit, & E. Vee (Eds.),
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 67-89). SIAM PUBLICATIONS.
https://doi.org/10.1137/1.9781611977073.4Vancouver
Husic E, Loho G
, Smith B, Vegh LA.
On complete classes of valuated matroids. In Bansal N, Coester C, Kumar R, Purohit M, Vee E, editors, Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM PUBLICATIONS. 2022. p. 67-89 doi: 10.1137/1.9781611977073.4
Author
Husic, Edin ; Loho, Georg
; Smith, Ben et al. /
On complete classes of valuated matroids. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). editor / Nikhil Bansal ; Christian Coester ; Ravi Kumar ; Manish Purohit ; Erik Vee. SIAM PUBLICATIONS, 2022. pp. 67-89
Bibtex
@inproceedings{8dd1721f42544221b1e9f5ae8cd4de1d,
title = "On complete classes of valuated matroids",
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.",
author = "Edin Husic and Georg Loho and Ben Smith and Vegh, {Laszlo A.}",
year = "2022",
month = jan,
day = "5",
doi = "10.1137/1.9781611977073.4",
language = "English",
pages = "67--89",
editor = "Nikhil Bansal and Christian Coester and Ravi Kumar and Purohit, {Manish } and Erik Vee",
booktitle = "Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)",
publisher = "SIAM PUBLICATIONS",
}
RIS
TY - GEN
T1 - On complete classes of valuated matroids
AU - Husic, Edin
AU - Loho, Georg
AU - Smith, Ben
AU - Vegh, Laszlo A.
PY - 2022/1/5
Y1 - 2022/1/5
N2 - 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.
AB - 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.
UR - https://research.manchester.ac.uk/en/publications/40309470-d996-46f0-8074-be58f3e4769a
U2 - 10.1137/1.9781611977073.4
DO - 10.1137/1.9781611977073.4
M3 - Conference contribution/Paper
SP - 67
EP - 89
BT - Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
A2 - Bansal, Nikhil
A2 - Coester, Christian
A2 - Kumar, Ravi
A2 - Purohit, Manish
A2 - Vee, Erik
PB - SIAM PUBLICATIONS
ER -
