On Randomized Algorithms for Matching in the Online Preemptive Model

DOI10.1007/978-3-662-48350-3_28zbMath1466.68081arXiv1412.8615OpenAlexW1514601641MaRDI QIDQ3452797

Sundar Vishwanathan, Sumedh Tirodkar, Ashish Chiplunkar

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (8)

Online maximum matching with recourse ⋮ On Randomized Algorithms for Matching in the Online Preemptive Model ⋮ Online Maximum Matching with Recourse ⋮ Online algorithms for maximum cardinality matching with edge arrivals ⋮ Deferred on-line bipartite matching ⋮ Unnamed Item ⋮ Online Algorithms for Maximum Cardinality Matching with Edge Arrivals ⋮ Maximum matching on trees in the online preemptive and the incremental graph models

Cites Work

• On graph problems in a semi-streaming model
• Improved Bounds for Online Preemptive Matching
• Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
• On Randomized Algorithms for Matching in the Online Preemptive Model
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: On Randomized Algorithms for Matching in the Online Preemptive Model