[Theory Lunch 03/19] Shaddin Dughmi: Matroid Secretary is Equivalent to Contention Resolution

[Haoming Li]

USC CS Theory Lunch:

Matroid Secretary is Equivalent to Contention Resolution
Speaker: Shaddin Dughmi (https://viterbi-web.usc.edu/~shaddin/)
Time: 03/19/21 11:45am PST
Location: https://usc.zoom.us/j/94386654763

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.

Our proof is the composition of three reductions. First, we use duality arguments to reduce the matroid secretary problem to the matroid prophet secretary problem with arbitrarily correlated distributions. Second, we introduce a generalization of contention resolution we term labeled contention resolution, to which we reduce the correlated matroid prophet secretary problem. Finally, we combine duplication of elements with limiting arguments to reduce labeled contention resolution to classical contention resolution.

[Shaddin Dughmi]

Thanks Haoming! And here's a link to the (unpublished) paper as well: https://arxiv.org/abs/2103.04205

--
You received this message because you are subscribed to the Google Groups "USC Theory Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to usc-theory-gro...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/usc-theory-group/CAJ58JEJjo5DKhtSVPmqoAZk3uy1%2Bevm%2BhrsBKo29f-mB_ne4Ag%40mail.gmail.com.

--

Shaddin Dughmi

Associate Professor

Computer Science Department

University of Southern California (USC)
Email: sha...@usc.edu

Web: https://viterbi-web.usc.edu/~shaddin/