Matroid Partition Property and the Secretary Problem

MaRDI QIDQ6383844zbMATH OpenFDO

Authors Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

Publication date 24 November 2021

Abstract: A matroid $mathcalM$ on a set $E$ of elements has the $alpha$-partition property, for some $alpha>0$, if it is possible to (randomly) construct a partition matroid $mathcalP$ on (a subset of) elements of $mathcalM$ such that every independent set of $mathcalP$ is independent in $mathcalM$ and for any weight function $w:Eomathbb{R}_{geq0}$, the expected value of the optimum of the matroid secretary problem on $mathcalP$ is at least an $alpha$-fraction of the optimum on $mathcalM$. We show that the complete binary matroid, ${calB}_d$ on $mathbb{F}_2^d$ does not satisfy the $alpha$-partition property for any constant $alpha>0$ (independent of $d$). Furthermore, we refute a recent conjecture of B'erczi, Schwarcz, and Yamaguchi by showing the same matroid is $2^d/d$-colorable but cannot be reduced to an $alpha{2}^d/d$-colorable partition matroid for any $alpha$ that is sublinear in $d$.

This page was built for publication: Matroid Partition Property and the Secretary Problem

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