Formal barriers to simple algorithms for the matroid secretary problem

DOI10.1007/978-3-030-94676-0_16MaRDI QIDQ2152122OpenAlexFDO

Authors Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla, S. Matthew Weinberg

Publication date 6 July 2022

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

zbMATH Keywords

graph theorygreedy algorithmsmatroidssecretary problemoptimal stopping theory

Mathematics Subject Classification ID

Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26) Internet topics (68M11)

Recommendations

• A framework for the secretary problem on the intersection of matroids
• A Framework for the Secretary Problem on the Intersection of Matroids
• Matroids, secretary problems, and online mechanisms
• 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
• Strong algorithms for the ordinal matroid secretary problem
• Strong algorithms for the ordinal matroid secretary problem
• Matroid secretary problem in the random-assignment model

Cites work

• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• scientific article; zbMATH DE number 3383344 (Why is no real title available?)
• A Knapsack Secretary Problem with Applications
• A simple PTAS for weighted matroid matching on strongly base orderable matroids
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Advances on matroid secretary problems: free order model and laminar case
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms.
• Combinatorial secretary problems with ordinal information
• Matroid Secretary Problems
• Matroid prophet inequalities
• Matroids and the greedy algorithm
• Matroids, secretary problems, and online mechanisms
• Note on Independence Functions
• Online contention resolution schemes
• Optimal assignments in an ordered set: An application of matroid theory
• Prophet Inequalities with Limited Information
• Strong algorithms for the ordinal matroid secretary problem
• The matroid secretary problem for minor-closed classes and random matroids

Cited in

(1)

• Robust Algorithms for the Secretary Problem

This page was built for publication: Formal barriers to simple algorithms for the matroid secretary problem

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