Matroid Secretary for Regular and Decomposable Matroids

DOI10.1137/13094030XzbMath1320.68226arXiv1207.5146OpenAlexW4214843198MaRDI QIDQ5173256

Michael Dinitz, Guy Kortsarz

Publication date: 9 February 2015

Published in: SIAM Journal on Computing, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmsregular matroidsmatroid secretary

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Online algorithms; streaming algorithms (68W27)

Related Items (16)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ The simulated greedy algorithm for several submodular matroid secretary problems ⋮ Secretary Markets with Local Information ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ Regular Matroids Have Polynomial Extension Complexity ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Advances on strictly \(\varDelta \)-modular IPs ⋮ Constant-competitiveness for random assignment matroid secretary without knowing the matroid ⋮ Matroid prophet inequalities and applications to multi-dimensional mechanism design ⋮ The Submodular Secretary Problem Goes Linear ⋮ 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 ⋮ On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)

This page was built for publication: Matroid Secretary for Regular and Decomposable Matroids