On Variants of the Matroid Secretary Problem

Details On Variants of the Matroid Secretary Problem On Variants of the Matroid Secretary Problem

2011-04-20

arxiv.org/abs/1104.4081v2

Computer Science

Data Structures and Algorithms

Scientific paper

We present a number of positive and negative results for variants of the matroid secretary problem. Most notably, we design a constant-factor competitive algorithm for the "random assignment" model where the weights are assigned randomly to the elements of a matroid, and then the elements arrive on-line in an adversarial order (extending a result of Soto \cite{Soto11}). This is under the assumption that the matroid is known in advance. If the matroid is unknown in advance, we present an $O(\log r \log n)$-approximation, and prove that a better than $O(\log n / \log \log n)$ approximation is impossible. This resolves an open question posed by Babaioff et al. \cite{BIK07}. As a natural special case, we also consider the classical secretary problem where the number of candidates $n$ is unknown in advance. If $n$ is chosen by an adversary from $\{1,...,N\}$, we provide a nearly tight answer, by providing an algorithm that chooses the best candidate with probability at least $1/(H_{N-1}+1)$ and prove that a probability better than $1/H_N$ cannot be achieved (where $H_N$ is the $N$-th harmonic number).

Affiliated with

Also associated with

No associations

Rating

On Variants of the Matroid Secretary Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Variants of the Matroid Secretary Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Variants of the Matroid Secretary Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-433561