Ranking on arbitrary graphs: rematch via continuous linear programming

DOI10.1137/140984051MaRDI QIDQ4581907zbMATHOpenAlexWikidataFDO

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

Publication date 21 August 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/140984051

zbMATH Keywords

continuous linear programmingranking algorithmoblivious matching problem

Mathematics Subject Classification ID

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

Recommendations

• Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Tighter bounds for online bipartite matching
• Randomized primal-dual analysis of RANKING for online bipartite matching
• Online bipartite matching with unknown distributions

Cites work

• scientific article; zbMATH DE number 5764830 (Why is no real title available?)
• A Duality Theorem for a Class of Continuous Linear Programming Problems
• A class of continuous linear programming problems
• Beating ratio 0.5 for weighted oblivious matching problems
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions
• Online matroid intersection: beating half for random arrival
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Pairwise kidney exchange
• Randomized greedy matching
• Randomized greedy matching. II
• Resource augmentation for weighted flow-time explained by dual fitting
• Two-sided online bipartite matching and vertex cover: beating the greedy algorithm

Cited in

(3)

• Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints
• Analyzing node-weighted oblivious matching problem via continuous LP with jump discontinuity
• Greedy matching in bipartite random graphs

This page was built for publication: Ranking on arbitrary graphs: rematch via continuous linear programming

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