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

DOI10.1016/j.tcs.2023.114329OpenAlexW4389454839MaRDI QIDQ6138832

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

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

zbMATH Keywords

marketsfractional matchingonline matchingpricing mechanismadversarial hardnessmax-min greedy matching

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Bayesian Mechanism Design
• Graph expansion and the unique games conjecture
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
• Edge Dominating Sets in Graphs
• Combinatorial Auctions via Posted Prices
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals
• An Experimental Study of Algorithms for Online Bipartite Matching

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