Abdolazimi, Dorna
[Verfasser:in];
Karlin, Anna R.
[Verfasser:in];
Klein, Nathan
[Verfasser:in];
Oveis Gharan, Shayan
[Verfasser:in]
;
Dorna Abdolazimi and Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan
[Mitwirkende:r]
Matroid Partition Property and the Secretary Problem
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.