2026-07-23T05:29:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17505 2024-03-06T10:59:45Z ddc:004 open_access

Matroid Partition Property and the Secretary Problem Abdolazimi, Dorna Karlin, Anna R. Klein, Nathan Oveis Gharan, Shayan Online algorithms Matroids Matroid secretary problem A matroid M on a set E of elements has the α-partition property, for some α > 0, if it is possible to (randomly) construct a partition matroid 𝒫 on (a subset of) elements of M such that every independent set of 𝒫 is independent in M and for any weight function w:E → ℝ_{≥0}, the expected value of the optimum of the matroid secretary problem on 𝒫 is at least an α-fraction of the optimum on M. We show that the complete binary matroid, B_d on 𝔽₂^d does not satisfy the α-partition property for any constant α > 0 (independent of d). Furthermore, we refute a recent conjecture of [Kristóf Bérczi et al., 2021] by showing the same matroid is 2^d/d-colorable but cannot be reduced to an α 2^d/d-colorable partition matroid for any α that is sublinear in d. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dorna Abdolazimi and Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.2 urn:nbn:de:0030-drops-175051 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.2 eng https://creativecommons.org/licenses/by/4.0/legalcode