The matroid secretary problem for minor-closed classes and random matroids

DOI10.1137/16M1107899MaRDI QIDQ5208744zbMATH OpenFDO

Authors

Publication date 10 January 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmsmatroidsminorstree decompositions

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Random graphs (graph-theoretic aspects) (05C80) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: We prove that for every proper minor-closed class $M$ of matroids representable over a prime field, there exists a constant-competitive matroid secretary algorithm for the matroids in $M$. This result relies on the extremely powerful matroid minor structure theory being developed by Geelen, Gerards and Whittle. We also note that for asymptotically almost all matroids, the matroid secretary algorithm that selects a random basis, ignoring weights, is $(2+o(1))$-competitive. In fact, assuming the conjecture that almost all matroids are paving, there is a $(1+o(1))$-competitive algorithm for almost all matroids.

Recommendations

• Matroid secretary problem in the random-assignment model
• Matroid secretary problem in the random assignment model
• Improved competitive ratio for the matroid secretary problem

Cites work

• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3383344 (Why is no real title available?)
• A multiple-choice secretary algorithm with applications to online auctions
• 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
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
• Branch-width and well-quasi-ordering in matroids and graphs.
• Competitive weighted matching in transversal matroids
• Decomposition of regular matroids
• Dynamic Programming and Decision Theory
• Graph minors. XVI: Excluding a non-planar graph
• Graph theory
• Improved competitive ratio for the matroid secretary problem
• Laminar matroids
• Matroid Secretary Problems
• Matroid secretary problem in the random-assignment model
• Matroids, secretary problems, and online mechanisms
• On perturbations of highly connected dyadic matroids
• On the asymptotic proportion of connected matroids
• On the number of bases of almost all matroids
• On the number of matroids compared to the number of sparse paving matroids
• Secretary problems: laminar matroid and interval scheduling
• Small cocircuits in matroids
• Solving Rota's conjecture
• Strong algorithms for the ordinal matroid secretary problem
• The highly connected matroids in minor-closed classes
• Who solved the secretary problem

Cited in

(4)

• Algorithms for maximum social welfare of online random trading
• Matroid Secretary Problems
• Formal barriers to simple algorithms for the matroid secretary problem
• A Framework for the Secretary Problem on the Intersection of Matroids

This page was built for publication: The matroid secretary problem for minor-closed classes and random matroids

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