Max-min greedy matching

DOI10.4086/TOC.2022.V018A006MaRDI QIDQ5077148zbMATH OpenOpenAlexFDO

Authors Alon Eden, Michal Feldman, Uriel Feige

Publication date 18 May 2022

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

marketsonline matchingpricing mechanism

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Theory of computing (68Qxx) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• scientific article; zbMATH DE number 7650074
• Greedy matching: guarantees and limitations
• Max-min greedy matching problem: hardness for the adversary and fractional variant
• scientific article; zbMATH DE number 6469133
• Rank-maximal matchings

Cites work

• Approximation hardness of edge dominating set problems
• College Admissions and the Stability of Marriage
• Combinatorial auctions via posted prices
• Computing Walrasian equilibria: fast algorithms and structural properties
• scientific article; zbMATH DE number 6850371 (Why is no real title available?)
• scientific article; zbMATH DE number 7650074 (Why is no real title available?)
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions
• Online matching and ad allocation
• Short Tours through Large Linear Forests

Cited in

(7)

• Greedy Matching on the Line
• Greedy matching: guarantees and limitations
• scientific article; zbMATH DE number 7650074 (Why is no real title available?)
• A Dual Approach for Dynamic Pricing in Multidemand Markets
• Max-min greedy matching problem: hardness for the adversary and fractional variant
• Max-min greedy matching problem: hardness for the adversary and fractional variant
• On inner independence systems

This page was built for publication: Max-min greedy matching

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