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

DOI10.1016/J.TCS.2023.114329OpenAlexW4389454839MaRDI QIDQ6138832FDOQ6138832

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

Publication date: 16 January 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114329

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

zbMATH Keywords

marketsfractional matchingonline matchingpricing mechanismadversarial hardnessmax-min greedy matching

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Edge Dominating Sets in Graphs
• Online matching and ad allocation
• Graph expansion and the unique games conjecture
• Max-min greedy matching
• Combinatorial auctions via posted prices
• Tight approximation ratio for Minimum Maximal Matching
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• An Experimental Study of Algorithms for Online Bipartite Matching
• Title not available (Why is that?)

Cited In (1)

• 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 Q6138832)