Improved bounds for randomized preemptive online matching

DOI10.1016/j.ic.2017.12.002zbMath1388.68314OpenAlexW2772037640MaRDI QIDQ1706142

Danny Segev, Oren Weimann, Leah Epstein, Asaf Levin

Publication date: 21 March 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2017.12.002

zbMATH Keywords

competitive analysislower boundsonline matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Online algorithms for maximum cardinality matching with edge arrivals ⋮ Online Submodular Maximization with Preemption

Cites Work

• Unnamed Item
• Unnamed Item
• Online scheduling of jobs with fixed start times on related machines
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• On a local protocol for concurrent file transfers
• On the max coloring problem
• Randomized algorithms for online bounded bidding
• Improved randomized results for the interval selection problem
• Optimal online-list batch scheduling
• Online interval scheduling: Randomized and multiprocessor cases
• Weighted sum coloring in batch scheduling of conflicting jobs
• On the competitiveness of on-line real-time task scheduling
• An improved approximation ratio for the minimum latency problem
• On-line scheduling of jobs with fixed start and end times
• On-line algorithms for weighted bipartite matching and stable marriages
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Weighted matching in the semi-streaming model
• Incremental medians via online bidding
• On graph problems in a semi-streaming model
• Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
• Efficient On-Line Call Control Algorithms
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
• A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
• Online Weighted Matching
• Improved bounds for scheduling conflicting jobs with minsum criteria
• Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
• 75.9 Euler’s Constant
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Improved bounds for randomized preemptive online matching