|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Matroid Secretary Problem in the Random Assignment Model | | José A. Soto
; | | Date: |
13 Jul 2010 | | Abstract: | In the Matroid Secretary Problem, introduced by Babaioff et al. [SODA 2007],
the elements of a given matroid are presented to an online algorithm in random
order. When an element is revealed, the algorithm learns its weight and decides
whether or not to select it under the restriction that the selected elements
form an independent set in the matroid. The objective is to maximize the total
weight of the chosen elements. In the most studied version of this problem, the
algorithm has no information about the weights beforehand. We refer to this as
the zero information model. In this paper we study a different model, also
proposed by Babaioff et al., in which the relative order of the weights is
random in the matroid. To be precise, in the random assignment model, an
adversary selects a collection of weights that are randomly assigned to the
elements of the matroid. Later, the elements are revealed to the algorithm in a
random order independent of the assignment.
Our main result is the first constant competitive algorithm for the matroid
secretary problem in the random assignment model. This solves an open question
of Babaioff et al. Our algorithm achieves a competitive ratio of $2e^2/(e-1)$.
It exploits the notion of principal partition of a matroid, its decomposition
into uniformly dense minors, and a $2e$-competitive algorithm for uniformly
dense matroids we also develop. As additional results, we present simple
constant competitive algorithms in the zero information model for various
classes of matroids including cographic, low density and the case when every
element is in a small cocircuit. In the same model, we also give a
$ke$-competitive algorithm for $k$-column sparse linear matroids, and a new
$O(log r)$-competitive algorithm for general matroids of rank $r$ which only
uses the relative order of the weights seen and not their numerical value, as
previously needed. | | Source: | arXiv, 1007.2152 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER