License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.42
URN: urn:nbn:de:0030-drops-124496
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12449/
Go to the corresponding LIPIcs Volume Portal

Dughmi, Shaddin

The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem

pdf-format:
LIPIcs-ICALP-2020-42.pdf (0.5 MB)

Abstract

Contention resolution schemes have proven to be a useful and unifying abstraction for a variety of constrained optimization problems, in both offline and online arrival models. Much of prior work restricts attention to product distributions for the input set of elements, and studies contention resolution for increasingly general packing constraints, both offline and online. In this paper, we instead focus on generalizing the input distribution, restricting attention to matroid constraints in both the offline and online random arrival models. In particular, we study contention resolution when the input set is arbitrarily distributed, and may exhibit positive and/or negative correlations between elements. We characterize the distributions for which offline contention resolution is possible, and establish some of their basic closure properties. Our characterization can be interpreted as a distributional generalization of the matroid covering theorem. For the online random arrival model, we show that contention resolution is intimately tied to the secretary problem via two results. First, we show that a competitive algorithm for the matroid secretary problem implies that online contention resolution is essentially as powerful as offline contention resolution for matroids, so long as the algorithm is given the input distribution. Second, we reduce the matroid secretary problem to the design of an online contention resolution scheme of a particular form.

BibTeX - Entry

@InProceedings{dughmi:LIPIcs:2020:12449,
  author =	{Shaddin Dughmi},
  title =	{{The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12449},
  URN =		{urn:nbn:de:0030-drops-124496},
  doi =		{10.4230/LIPIcs.ICALP.2020.42},
  annote =	{Keywords: Contention Resolution, Secretary Problems, Matroids}
}

Keywords: Contention Resolution, Secretary Problems, Matroids
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

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