Formal barriers to simple algorithms for the matroid secretary problem

DOI10.1007/978-3-030-94676-0_16OpenAlexW4225640671MaRDI QIDQ2152122

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

Publication date: 6 July 2022

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

zbMATH Keywords

graph theorymatroidsgreedy algorithmssecretary 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A simple PTAS for Weighted Matroid Matching on Strongly Base Orderable Matroids
• Note on Independence Functions
• A Knapsack Secretary Problem with Applications
• Online Contention Resolution Schemes
• Matroid Secretary Problems
• Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
• The Matroid Secretary Problem for Minor-Closed Classes and Random Matroids
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Prophet Inequalities with Limited Information
• Matroid prophet inequalities
• Optimal assignments in an ordered set: An application of matroid theory
• Matroids and the greedy algorithm
• Combinatorial optimization. Theory and algorithms.

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