Formal barriers to simple algorithms for the matroid secretary problem

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

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

Recommendations

• On variants of the matroid secretary problem
• On variants of the matroid secretary problem
• 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

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)

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms.
• Title not available (Why is that?)
• A Knapsack Secretary Problem with Applications
• Matroids, secretary problems, and online mechanisms
• Online Contention Resolution Schemes
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Matroid prophet inequalities
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Matroids and the greedy algorithm
• Title not available (Why is that?)
• Optimal assignments in an ordered set: An application of matroid theory
• Prophet Inequalities with Limited Information
• Advances on matroid secretary problems: free order model and laminar case
• Note on Independence Functions
• Title not available (Why is that?)
• Matroid Secretary Problems
• Title not available (Why is that?)
• A simple PTAS for weighted matroid matching on strongly base orderable matroids
• 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)