Online matroid intersection: beating half for random arrival

DOI10.1007/978-3-319-59250-3_20zbMath1418.90227arXiv1512.06271OpenAlexW2964293104MaRDI QIDQ2401162

Sahil Singla, Guru Prashanth Guruganesh

Publication date: 31 August 2017

Full work available at URL: https://arxiv.org/abs/1512.06271

zbMATH Keywords

competitive analysisonline algorithmsrandomized algorithmslinear-time algorithmsmatroid intersection

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (4)

Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming ⋮ Online algorithms for maximum cardinality matching with edge arrivals ⋮ Online submodular maximization: beating 1/2 made simple ⋮ Online Algorithms for Maximum Cardinality Matching with Edge Arrivals

This page was built for publication: Online matroid intersection: beating half for random arrival