Analyzing node-weighted oblivious matching problem via continuous LP with jump discontinuity

DOI10.1145/3168008MaRDI QIDQ4554339zbMATH OpenOpenAlexWikidataFDO

Authors T.-H. Hubert Chan, Fei Chen, Xiaowei Wu

Publication date 13 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3168008

zbMATH Keywords

linear programmingrankingoblivious algorithmsweighted matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Beating ratio 0.5 for weighted oblivious matching problems
• Ranking on arbitrary graphs: rematch via continuous linear programming
• Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints
• scientific article; zbMATH DE number 7376006
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs

Cited in

(4)

• Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints
• Toward a better understanding of randomized greedy matching
• Beating ratio 0.5 for weighted oblivious matching problems
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals

This page was built for publication: Analyzing node-weighted oblivious matching problem via continuous LP with jump discontinuity

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