Beating ratio 0.5 for weighted oblivious matching problems

DOI10.4230/LIPICS.ESA.2016.3MaRDI QIDQ4606268zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

linear programmingoblivious algorithmsrankingweighted matching

Mathematics Subject Classification ID

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

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

Cited in

(9)

• 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
• Analyzing node-weighted oblivious matching problem via continuous LP with jump discontinuity
• Ranking on arbitrary graphs: rematch via continuous linear programming
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
• scientific article; zbMATH DE number 7376006 (Why is no real title available?)
• Online Submodular Maximization Problem with Vector Packing Constraint.

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)