Title: A O(log log (rank) ) - competitive algorithm for the matroid secretary problem - Part 2
| Speaker: | David Aleman |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: In this talk we continue to review a O(log log(rank) ) - competitive algorithm for the matroid secretary problem (MSP) due to Feldman, Svensson and Zenklusen, where rank denotes the rank of the given matroid.
As a recap, in MSP the weighted elements of a matroid arrive one by one in a uniformly random order where an online algorithm observes the value of the element and must make an irrevocable decision of whether or not to include the element in its solution before the arrival of the next element. The goal is to maximize the total value of the chosen elements under the condition that they must constitute an independent set. Other than knowing the cardinality of the ground set and having access to an independence oracle, the algorithm has no further information about the matroid. The weights of the elements are fixed from the start but are otherwise arbitrary.
We'll start this talk by assuming the reduction from sample based MSP (defined below) mentioned last time.
In sample based MSP the goal is again to compute an independent set of maximum weight from a given weighted matroid. Sample based MSP is divided into two stages. The first stage is a sampling phase in which we sample a subset S of the ground set, such that every element is contained in S with probability p independently at random for some fixed p (we may not know the cardinality of the ground set now). We do not include any element from the sample S in our solution. In the second stage the rest of the elements of the matroid arrive uniformly at random revealing their weights upon arrival, and as before, we must decide immediately and irrevocably on whether we include the current element in our solution or not before the next arrival. Furthermore, we assume that
- We are given an upper bound R on the rank of the given matroid.
- The weight of each element is contained in the interval [ W/8R, W] for some W.
The reduction states that a O(loglog R)- competitive algorithm for sampled based MSP implies a O(loglog rank) - competitive algorithm for MSP, where we say that an algorithm is c-competitive if the expected weight of the independent set returned by the algorithm is at least OPT/c, where OPT denotes the weight of the offline optimum. We will see how to get a O(loglog R)- competitive algorithm for sampled based MSP during this talk.