A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

DOI10.1137/1.9781611973730.79zbMath1372.68285arXiv1404.4473OpenAlexW3137340669MaRDI QIDQ5363101

Moran Feldman, Rico Zenklusen, Ola Svensson

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Stopping times; optimal stopping problems; gambling theory (60G40) Combinatorial aspects of matroids and geometric lattices (05B35) Online algorithms; streaming algorithms (68W27)

Related Items (26)

Prophet Secretary ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ The simulated greedy algorithm for several submodular matroid secretary problems ⋮ Secretary Markets with Local Information ⋮ The Temp Secretary Problem ⋮ Online Appointment Scheduling in the Random Order Model ⋮ Formal barriers to simple algorithms for the matroid secretary problem ⋮ New results for the \(k\)-secretary problem ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Generalized laminar matroids ⋮ Secretary and online matching problems with machine learned advice ⋮ Matroid-constrained vertex cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ The Submodular Secretary Problem Goes Linear ⋮ Scheduling In the random-order model ⋮ Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs ⋮ Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents ⋮ Laminar matroids ⋮ Stable secretaries ⋮ Secretary markets with local information ⋮ Prior independent mechanisms via prophet inequalities with limited information ⋮ The Matroid Secretary Problem for Minor-Closed Classes and Random Matroids ⋮ Improved online algorithm for fractional knapsack in the random order model ⋮ Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property

This page was built for publication: A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem