Improved randomized results for the interval selection problem

DOI10.1016/J.TCS.2010.04.042zbMath1196.68323OpenAlexW2055364146MaRDI QIDQ986549

Leah Epstein, Asaf Levin

Publication date: 11 August 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.04.042

zbMATH Keywords

competitive analysisonline algorithmsinterval schedulingYao's principle

Mathematics Subject Classification ID

Stochastic scheduling theory in operations research (90B36) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (10)

Online selection of intervals and \(t\)-intervals ⋮ Online interval scheduling on two related machines: the power of lookahead ⋮ On-line scheduling of equal-length intervals on parallel machines ⋮ Improved bounds for randomized preemptive online matching ⋮ Online interval scheduling with a bounded number of failures ⋮ Online C-benevolent job scheduling on multiple machines ⋮ Improved randomized online scheduling of intervals and jobs ⋮ An Improved Online Algorithm for the Online Preemptive Scheduling of Equal-Length Intervals on a Single Machine with Lookahead ⋮ Online interval scheduling to maximize total satisfaction ⋮ Online scheduling of jobs with fixed start times on related machines

Cites Work

• Unnamed Item
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Online interval scheduling: Randomized and multiprocessor cases
• Randomized online interval scheduling
• On-line scheduling of jobs with fixed start and end times
• Note on scheduling intervals on-line
• On the \(k\)-coloring of intervals
• An improved randomized on-line algorithm for a weighted interval selection problem
• Interval scheduling: A survey
• Improved Randomized Results for That Interval Selection Problem
• Improved Randomized Online Scheduling of Unit Length Intervals and Jobs
• Bounding the Power of Preemption in Randomized Scheduling

This page was built for publication: Improved randomized results for the interval selection problem