Advances on Matroid Secretary Problems: Free Order Model and Laminar Case

DOI10.1007/978-3-642-36694-9_22zbMath1372.90093arXiv1207.1333OpenAlexW1819914325MaRDI QIDQ4910821

Jose A. Soto, Patrick Jaillet, Rico Zenklusen

Publication date: 19 March 2013

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Probabilistic games; gambling (91A60)

Related Items (13)

Secretary Markets with Local Information ⋮ Formal barriers to simple algorithms for the matroid secretary problem ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Constant-competitiveness for random assignment matroid secretary without knowing the matroid ⋮ Generalized laminar matroids ⋮ Matroid prophet inequalities and applications to multi-dimensional mechanism design ⋮ The Submodular Secretary Problem Goes Linear ⋮ Laminar matroids ⋮ 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 ⋮ A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem

This page was built for publication: Advances on Matroid Secretary Problems: Free Order Model and Laminar Case