Competitive Weighted Matching in Transversal Matroids

DOI10.1007/978-3-540-70575-8_33MaRDI QIDQ3521935zbMATH OpenOpenAlexFDO

Authors Nedialko B. Dimitrov, C. Greg Plaxton

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_33

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Competitive weighted matching in transversal matroids
• Online Weighted Matching
• Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
• scientific article; zbMATH DE number 176778

Cited in

(6)

• Near optimal algorithms for online weighted bipartite matching in adversary model
• Matroid prophet inequalities and applications to multi-dimensional mechanism design
• Competitive weighted matching in transversal matroids
• Improved competitive ratios for submodular secretary problems (extended abstract)
• Improved competitive ratio for the matroid secretary problem
• Beating competitive ratio 4 for graphic matroid secretary

This page was built for publication: Competitive Weighted Matching in Transversal Matroids

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