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.2022.58
URN: urn:nbn:de:0030-drops-156540
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15654/
Go to the corresponding LIPIcs Volume Portal

Dughmi, Shaddin

Matroid Secretary Is Equivalent to Contention Resolution

pdf-format:
LIPIcs-ITCS-2022-58.pdf (0.8 MB)

Abstract

We show that the matroid secretary problem is equivalent to correlated contention resolution in the online random-order model. Specifically, the matroid secretary conjecture is true if and only if every matroid admits an online random-order contention resolution scheme which, given an arbitrary (possibly correlated) prior distribution over subsets of the ground set, matches the balance ratio of the best offline scheme for that distribution up to a constant. We refer to such a scheme as universal. Our result indicates that the core challenge of the matroid secretary problem lies in resolving contention for positively correlated inputs, in particular when the positive correlation is benign in as much as offline contention resolution is concerned.
Our result builds on our previous work which establishes one direction of this equivalence, namely that the secretary conjecture implies universal random-order contention resolution, as well as a weak converse, which derives a matroid secretary algorithm from a random-order contention resolution scheme with only partial knowledge of the distribution. It is this weak converse that we strengthen in this paper: We show that universal random-order contention resolution for matroids, in the usual setting of a fully known prior distribution, suffices to resolve the matroid secretary conjecture in the affirmative.

BibTeX - Entry

@InProceedings{dughmi:LIPIcs.ITCS.2022.58,
  author =	{Dughmi, Shaddin},
  title =	{{Matroid Secretary Is Equivalent to Contention Resolution}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{58:1--58:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15654},
  URN =		{urn:nbn:de:0030-drops-156540},
  doi =		{10.4230/LIPIcs.ITCS.2022.58},
  annote =	{Keywords: Contention Resolution, Secretary Problems, Matroids}
}

Keywords: Contention Resolution, Secretary Problems, Matroids
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

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