Constant-competitiveness for random assignment matroid secretary without knowing the matroid

DOI10.1007/978-3-031-32726-1_30zbMath1528.91023arXiv2305.05353OpenAlexW4377200020MaRDI QIDQ6086020

Richard Santiago, Rico Zenklusen, Ivan Sergeev

Publication date: 9 November 2023

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

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

Mathematics Subject Classification ID

Probabilistic games; gambling (91A60) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random sampling and greedy sparsification for matroid optimization problems
• On variants of the matroid secretary problem
• Competitive weighted matching in transversal matroids
• Matroid Secretary Problem in the Random-Assignment Model
• An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
• Matroid Secretary Problems
• Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
• Matroid Secretary for Regular and Decomposable Matroids
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Algorithms for Secretary Problems on Graphs and Hypergraphs

This page was built for publication: Constant-competitiveness for random assignment matroid secretary without knowing the matroid