Improved bounds for randomized preemptive online matching

DOI10.1016/J.IC.2017.12.002MaRDI QIDQ1706142zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(9)

• The expected asymptotical ratio for preemptive stochastic online problem
• Improved Bounds for Online Stochastic Matching
• 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

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)