Beating ratio 0.5 for weighted oblivious matching problems

DOI10.4230/LIPIcs.ESA.2016.3zbMath1397.68219OpenAlexW2531043207MaRDI 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

zbMATH Keywords

linear programmingrankingoblivious algorithmsweighted matching

Mathematics Subject Classification ID

Linear programming (90C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (8)

The longest processing time rule for identical parallel machines revisited ⋮ Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming ⋮ On approximating the incremental knapsack problem ⋮ A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem ⋮ Unnamed Item ⋮ Approximating the 3-period incremental knapsack problem ⋮ Online Vertex-Weighted Bipartite Matching ⋮ Online Submodular Maximization Problem with Vector Packing Constraint.

This page was built for publication: Beating ratio 0.5 for weighted oblivious matching problems