Competitive weighted matching in transversal matroids

DOI10.1007/s00453-010-9457-2zbMath1239.05148OpenAlexW2109969113MaRDI QIDQ2428661

Nedialko B. Dimitrov, C. Greg Plaxton

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9457-2

zbMATH Keywords

matchingonline algorithmtransversal matroidsecretary problem

Mathematics Subject Classification ID

Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

The simulated greedy algorithm for several submodular matroid secretary problems ⋮ Secretary Markets with Local Information ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Constant-competitiveness for random assignment matroid secretary without knowing the matroid ⋮ Secretary and online matching problems with machine learned advice ⋮ 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 ⋮ Online Collaborative Filtering on Graphs ⋮ Size versus truthfulness in the house allocation problem ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem

Cites Work

• Random sampling and greedy sparsification for matroid optimization problems
• Who solved the secretary problem? With comments and a rejoinder by the author
• The Secretary Problem and Its Extensions: A Review
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Dynamic Programming and Decision Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item