Max-min greedy matching problem: hardness for the adversary and fractional variant
DOI10.1007/978-3-031-39344-0_7zbMATH Open1547.68559MaRDI QIDQ6535803
T.-H. Hubert Chan, Zhihao Gavin Tang, Quan Xue
Publication date: 28 February 2024
Analysis of algorithms (68W40) Applications of game theory (91A80) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Matching models (91B68) Online algorithms; streaming algorithms (68W27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pricing multi-unit markets
- 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
- 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
