On complete classes of valuated matroids

Edin Husić; Georg Loho; Ben Smith; László A. Végh

doi:10.1137/1.9781611977073.41

On complete classes of valuated matroids

Edin Husić, Georg Loho, Ben Smith, László A. Végh

Mathematics of Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

9 Downloads (Pure)

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.

Original language	English
Title of host publication	Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Editors	Joseph (Seffi) Naor, Niv Buchbinder
Publisher	Association for Computing Machinery
Pages	945-962
Number of pages	18
ISBN (Electronic)	978-1-61197-707-3
DOIs	https://doi.org/10.1137/1.9781611977073.41
Publication status	Published - 2022
Event	33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States Duration: 9 Jan 2022 → 12 Jan 2022 Conference number: 33

Conference

Conference	33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Abbreviated title	SODA 2022
Country/Territory	United States
City	Alexander
Period	9/01/22 → 12/01/22

Keywords

n/a OA procedure

Access to Document

10.1137/1.9781611977073.41

Cite this

@inproceedings{d995d07fca4c4972883d738533de621f,

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.",

keywords = "n/a OA procedure",

author = "Edin Husi{\'c} and Georg Loho and Ben Smith and V{\'e}gh, {L{\'a}szl{\'o} A.}",

note = "Funding Information: ∗The full version of the paper can be accessed at https://arxiv.org/abs/2107.06961. †London School of Economics and Political Science. This project has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement no. ScaleOpt–757481). ‡University of Twente. §University of Manchester and Heilbronn Institute for Mathematical Research. Publisher Copyright: Copyright c 2022 ; 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, SODA 2022 ; Conference date: 09-01-2022 Through 12-01-2022",

year = "2022",

doi = "10.1137/1.9781611977073.41",

language = "English",

pages = "945--962",

editor = "Naor, {Joseph (Seffi)} and Niv Buchbinder",

booktitle = "Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)",

publisher = "Association for Computing Machinery",

address = "United States",

}

Husić, E, Loho, G, Smith, B & Végh, LA 2022, On complete classes of valuated matroids. in J Naor & N Buchbinder (eds), Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Association for Computing Machinery, pp. 945-962, 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Alexander, United States, 9/01/22. https://doi.org/10.1137/1.9781611977073.41

On complete classes of valuated matroids. / Husić, Edin; Loho, Georg; Smith, Ben et al.
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ed. / Joseph (Seffi) Naor; Niv Buchbinder. Association for Computing Machinery, 2022. p. 945-962.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On complete classes of valuated matroids

AU - Husić, Edin

AU - Loho, Georg

AU - Smith, Ben

AU - Végh, László A.

N1 - Conference code: 33

PY - 2022

Y1 - 2022

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.

KW - n/a OA procedure

UR - http://www.scopus.com/inward/record.url?scp=85130698409&partnerID=8YFLogxK

U2 - 10.1137/1.9781611977073.41

DO - 10.1137/1.9781611977073.41

M3 - Conference contribution

SP - 945

EP - 962

BT - Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

A2 - Naor, Joseph (Seffi)

A2 - Buchbinder, Niv

PB - Association for Computing Machinery

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -

On complete classes of valuated matroids

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this