Beating ratio 0.5 for weighted oblivious matching problems
From MaRDI portal
Publication:4606268
DOI10.4230/LIPIcs.ESA.2016.3zbMath1397.68219MaRDI QIDQ4606268
Mahini Hamid, Hossein Esfandiari, T.-H. Hubert Chan, Melika Abolhassani, Fei Chen, Xiaowei Wu, Mohammad Taghi Hajiaghayi
Publication date: 2 March 2018
Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.3
90C05: Linear programming
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68W25: Approximation algorithms
Related Items
Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming, Unnamed Item, Online Vertex-Weighted Bipartite Matching, Online Submodular Maximization Problem with Vector Packing Constraint., Approximating the 3-period incremental knapsack problem, The longest processing time rule for identical parallel machines revisited, On approximating the incremental knapsack problem, A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem