Max-min greedy matching problem: hardness for the adversary and fractional variant

DOI10.1007/978-3-031-39344-0_7MaRDI QIDQ6535803zbMATH OpenFDO

Authors T.-H. Hubert Chan, Zhihao Gavin Tang, Quan Xue

Publication date 28 February 2024

Full work available at URL https://doi.org/10.1007/978-3-031-39344-0_7

zbMATH Keywords

adversarial hardnessfractional matchingmax-min greedy matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26) Matching models (91B68)

Recommendations

• Max-min greedy matching problem: hardness for the adversary and fractional variant
• scientific article; zbMATH DE number 7650074
• Max-min greedy matching
• Greedy matching: guarantees and limitations
• Near optimal algorithms for online weighted bipartite matching in adversary model

Cites work

• An Experimental Study of Algorithms for Online Bipartite Matching
• Combinatorial auctions via posted prices
• Graph expansion and the unique games conjecture
• scientific article; zbMATH DE number 5764830 (Why is no real title available?)
• scientific article; zbMATH DE number 6850371 (Why is no real title available?)
• Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
• Max-min greedy matching
• 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
• Pricing multi-unit markets
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• Tight approximation ratio for Minimum Maximal Matching

Cited in

(2)

• Max-min greedy matching
• Max-min greedy matching problem: hardness for the adversary and fractional variant

This page was built for publication: Max-min greedy matching problem: hardness for the adversary and fractional variant

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