Beating ratio 0.5 for weighted oblivious matching problems

DOI10.4230/LIPICS.ESA.2016.3zbMATH Open1397.68219OpenAlexW2531043207MaRDI QIDQ4606268FDOQ4606268

Authors: Melika Abolhassani, T.-H. Hubert Chan, Fei Chen, H. Esfandiari, Mahini Hamid, Xiaowei Wu, Mohammad T. Hajiaghayi 

Publication date: 2 March 2018

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.3

Recommendations

• Analyzing node-weighted oblivious matching problem via continuous LP with jump discontinuity
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
• Online Weighted Matching
• scientific article; zbMATH DE number 7376006
• Tighter bounds for online bipartite matching

zbMATH Keywords

linear programmingrankingoblivious algorithmsweighted matching

Mathematics Subject Classification ID

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

Cited In (8)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606268)