Strong algorithms for the ordinal matroid secretary problem

DOI10.1287/MOOR.2020.1083OpenAlexW3129885107MaRDI QIDQ5000649FDOQ5000649

Abner Turkieltaub, Víctor Verdugo, José A. Soto

Publication date: 15 July 2021

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

Recommendations

• Strong algorithms for the ordinal matroid secretary problem
• Combinatorial secretary problems with ordinal information
• Improved competitive ratio for the matroid secretary problem
• Matroid Secretary Problems
• Matroid secretary problem in the random-assignment model

zbMATH Keywords

online algorithmsmatroidssecretary problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorics in computer science (68R05)

Cites Work

• Frame matroids and biased graphs
• On graphs and rigidity of plane skeletal structures
• Title not available (Why is that?)
• Transversals and matroid partition
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Knapsack Secretary Problem with Applications
• Probability and Computing
• Matroid secretary problem in the random-assignment model
• A multiple-choice secretary algorithm with applications to online auctions
• Title not available (Why is that?)
• Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
• Matroid Secretary for Regular and Decomposable Matroids
• Primal beats dual on online packing LPs in the random-order model
• Title not available (Why is that?)
• Matroid prophet inequalities
• Title not available (Why is that?)
• On variants of the matroid secretary problem
• Competitive weighted matching in transversal matroids
• The simulated greedy algorithm for several submodular matroid secretary problems
• Submodular secretary problem and extensions
• Title not available (Why is that?)
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Natural realizations of sparsity matroids
• Prophet Inequalities with Limited Information
• Dynamic Programming and Decision Theory
• Who solved the secretary problem? With comments and a rejoinder by the author
• Improved algorithms and analysis for secretary problems and generalizations
• Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
• On matroids induced by packing subgraphs
• Secretary Problems via Linear Programming
• Matroids Induced by Packing Subgraphs
• Title not available (Why is that?)
• An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
• Secretary Problems with Non-Uniform Arrival Order
• Beyond matroids: secretary problem and prophet inequality with general constraints
• Polymatroid Prophet Inequalities
• Title not available (Why is that?)
• Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Title not available (Why is that?)
• Combinatorial Prophet Inequalities
• Secretary Problems with Convex Costs

Cited In (4)

• Robust Algorithms for the Secretary Problem
• Formal barriers to simple algorithms for the matroid secretary problem
• Knapsack secretary through boosting
• Partial-order analogue of the secretary problem: The binary tree case

This page was built for publication: Strong algorithms for the ordinal matroid secretary problem

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