2026-08-10T17:38:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12449 2024-03-06T10:50:10Z ddc:004 open_access

The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem Dughmi, Shaddin Contention Resolution Secretary Problems Matroids 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shaddin Dughmi 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.42 urn:nbn:de:0030-drops-124496 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.42 eng https://creativecommons.org/licenses/by/3.0/legalcode