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

DOI10.1137/16M1107899zbMATH Open1431.05033arXiv1603.06822MaRDI QIDQ5208744FDOQ5208744

Authors:

Publication date: 10 January 2020

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

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.

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

Recommendations

• Matroid secretary problem in the random-assignment model
• Matroid secretary problem in the random assignment model
• Matroid secretary for regular and decomposable matroids
• Matroid secretary for regular and decomposable matroids
• Improved competitive ratio for the matroid secretary problem

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)

Cites Work

• Graph theory
• Decomposition of regular matroids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matroid secretary problem in the random-assignment model
• A multiple-choice secretary algorithm with applications to online auctions
• Title not available (Why is that?)
• Matroid Secretary for Regular and Decomposable Matroids
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Who solved the secretary problem
• Competitive weighted matching in transversal matroids
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• The highly connected matroids in minor-closed classes
• On the asymptotic proportion of connected matroids
• Dynamic Programming and Decision Theory
• Graph minors. XVI: Excluding a non-planar graph
• Solving Rota's conjecture
• Branch-width and well-quasi-ordering in matroids and graphs.
• On the number of matroids compared to the number of sparse paving matroids
• Advances on matroid secretary problems: free order model and laminar case
• Laminar matroids
• On the number of bases of almost all matroids
• Title not available (Why is that?)
• Small cocircuits in matroids
• An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
• On perturbations of highly connected dyadic matroids
• Matroid Secretary Problems

Cited In (4)

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

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)