Matroid secretary problem in the random-assignment model
From MaRDI portal
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 . It exploits the notion of principal partition of a matroid, its decomposition into uniformly dense minors, and a -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 -competitive algorithm for -column sparse linear matroids, and a new -competitive algorithm for general matroids of rank which only uses the relative order of the weights seen and not their numerical value, as previously needed.
Recommendations
Cited in
(29)- Secretary markets with local information
- Secretary problem: graphs, matroids and greedoids
- Formal barriers to simple algorithms for the matroid secretary problem
- Online matroid intersection: beating half for random arrival
- Generalized laminar matroids
- The best-or-worst and the postdoc problems with random number of candidates
- Approximation algorithms for stochastic combinatorial optimization problems
- The simulated greedy algorithm for several submodular matroid secretary problems
- Matroids, secretary problems, and online mechanisms
- Secretary markets with local information
- Strong algorithms for the ordinal matroid secretary problem
- Matroid Secretary Problems
- The submodular secretary problem goes linear
- Advances on matroid secretary problems: free order model and laminar case
- Strong algorithms for the ordinal matroid secretary problem
- A Framework for the Secretary Problem on the Intersection of Matroids
- Laminar matroids
- The matroid secretary problem for minor-closed classes and random matroids
- A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
- A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
- Matroid secretary problem in the random assignment model
- Improved competitive ratio for the matroid secretary problem
- Online contention resolution schemes with applications to Bayesian selection problems
- Constant-competitiveness for random assignment matroid secretary without knowing the matroid
- Non-adaptive prophet inequalities for minor-closed classes of matroids
- Matroid secretary via labeling schemes
- Single sample prophet inequality for uniform matroids of rank 2
- Constant-competitiveness for random assignment matroid secretary without knowing the matroid
- Pairwise-independent contention resolution
This page was built for publication: Matroid secretary problem in the random-assignment model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2839176)
