A simple O((rank))-competitive algorithm for the matroid secretary problem

DOI10.1137/1.9781611973730.79MaRDI QIDQ5363101zbMATH OpenOpenAlexFDO

Authors Moran Feldman, Ola Svensson, Rico Zenklusen

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

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

Abstract: Only recently progress has been made in obtaining $o(log(mathrmrank))$-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a $O(sqrtlog(mathrmrank))$-competitive procedure, and Lachish (2014) later presented a $O(loglog(mathrmrank))$-competitive algorithm. Both these algorithms and their analyses are very involved, which is also reflected in the extremely high constants in their competitive ratios. Using different tools, we present a considerably simpler $O(loglog(mathrmrank))$-competitive algorithm for the matroid secretary problem. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms which are easy to analyze. Due to the simplicity of our procedure, we are also able to vastly improve on the hidden constant in the competitive ratio.

Recommendations

• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Improved competitive ratio for the matroid secretary problem
• Matroid secretary problem in the random-assignment model
• Matroid secretary problem in the random assignment model
• Matroid Secretary Problems

Cited in

(33)

• Scheduling In the random-order model
• Stable secretaries
• Secretary markets with local information
• Improved online algorithm for fractional knapsack in the random order model
• Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property
• Formal barriers to simple algorithms for the matroid secretary problem
• Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
• Prior independent mechanisms via prophet inequalities with limited information
• Generalized laminar matroids
• New results for the \(k\)-secretary problem
• Approximation algorithms for stochastic combinatorial optimization problems
• The simulated greedy algorithm for several submodular matroid secretary problems
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• Secretary markets with local information
• The Temp Secretary Problem
• Online appointment scheduling in the random order model
• The submodular secretary problem goes linear
• Submodular secretary problems: cardinality, matching, and linear constraints
• Maximizing profit with convex costs in the random-order model
• 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
• Prophet secretary
• scientific article; zbMATH DE number 7651221 (Why is no real title available?)
• Secretary and online matching problems with machine learned advice
• Matroid-constrained vertex cover
• Prophet secretary for combinatorial auctions and matroids
• Knapsack secretary with bursty adversary
• Scheduling in the random-order model
• The outer limits of contention resolution on matroids and connections to the secretary problem
• Improved truthful mechanisms for combinatorial auctions with submodular bidders
• From contention resolution to matroid secretary and back

This page was built for publication: A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363101)