License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.2
URN: urn:nbn:de:0030-drops-175051
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17505/
Go to the corresponding LIPIcs Volume Portal

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

Matroid Partition Property and the Secretary Problem

pdf-format:
LIPIcs-ITCS-2023-2.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{abdolazimi_et_al:LIPIcs.ITCS.2023.2,
  author =	{Abdolazimi, Dorna and Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan},
  title =	{{Matroid Partition Property and the Secretary Problem}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{2:1--2:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17505},
  URN =		{urn:nbn:de:0030-drops-175051},
  doi =		{10.4230/LIPIcs.ITCS.2023.2},
  annote =	{Keywords: Online algorithms, Matroids, Matroid secretary problem}
}

Keywords: Online algorithms, Matroids, Matroid secretary problem
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI