Matroid Secretary Problem in the Random-Assignment Model

DOI10.1137/110852061zbMath1311.68197arXiv1007.2152OpenAlexW2052130355MaRDI QIDQ2839176

Jose A. Soto

Publication date: 4 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.2152

zbMATH Keywords

matroidsprincipal partitionsecretary problemsonline selection

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial aspects of matroids and geometric lattices (05B35) Online algorithms; streaming algorithms (68W27)

Related Items (15)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ The simulated greedy algorithm for several submodular matroid secretary problems ⋮ Secretary Markets with Local Information ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Constant-competitiveness for random assignment matroid secretary without knowing the matroid ⋮ Generalized laminar matroids ⋮ The best-or-worst and the postdoc problems with random number of candidates ⋮ The Submodular Secretary Problem Goes Linear ⋮ Laminar matroids ⋮ Secretary markets with local information ⋮ The Matroid Secretary Problem for Minor-Closed Classes and Random Matroids ⋮ A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem ⋮ Secretary problem: graphs, matroids and greedoids ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems

This page was built for publication: Matroid Secretary Problem in the Random-Assignment Model