Improved bounds for randomized preemptive online matching

DOI10.1016/J.IC.2017.12.002zbMATH Open1388.68314OpenAlexW2772037640MaRDI QIDQ1706142FDOQ1706142

Authors: Leah Epstein, Asaf Levin, Danny Segev, Oren Weimann 

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

Recommendations

• Improved bounds for online preemptive matching
• On randomized algorithms for matching in the online preemptive model
• Maximum matching on trees in the online preemptive and the incremental dynamic graph models
• Maximum matching on trees in the online preemptive and the incremental graph models
• scientific article; zbMATH DE number 6850371

zbMATH Keywords

lower boundscompetitive analysisonline matching

Mathematics Subject Classification ID

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

Cites Work

• Online interval scheduling: Randomized and multiprocessor cases
• On the competitiveness of on-line real-time task scheduling
• 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)
• Online scheduling of jobs with fixed start times on related machines
• 75.9 Euler’s Constant
• Improved randomized results for the interval selection problem
• Data streams: algorithms and applications.
• An improved approximation ratio for the minimum latency problem
• Incremental medians via online bidding
• On graph problems in a semi-streaming model
• Improved approximation guarantees for weighted matching in the semi-streaming model
• Weighted matching in the semi-streaming model
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Online Weighted Matching
• On the max coloring problem
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• Buyback problem -- approximate matroid intersection with cancellation costs
• On a local protocol for concurrent file transfers
• Improved bounds for scheduling conflicting jobs with minsum criteria
• Efficient On-Line Call Control Algorithms
• Optimal online-list batch scheduling
• Weighted sum coloring in batch scheduling of conflicting jobs
• Randomized algorithms for online bounded bidding
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Improved streaming algorithms for weighted matching, via unweighted matching
• A \((2 + \epsilon)\)-approximation for maximum weight matching in the semi-streaming model
• Maximum matching in two, three, and a few more passes over graph streams

Cited In (9)

• The expected asymptotical ratio for preemptive stochastic online problem
• Online algorithms for maximum cardinality matching with edge arrivals
• Improved bounds for online preemptive matching
• On randomized algorithms for matching in the online preemptive model
• Maximum matching on trees in the online preemptive and the incremental dynamic graph models
• Maximum matching on trees in the online preemptive and the incremental graph models
• Improved online algorithms for jumbled matching
• Online submodular maximization with preemption
• Improved Bounds for Online Stochastic Matching

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

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