Randomized online interval scheduling

DOI10.1016/S0167-6377(98)00019-4zbMath0914.90168OpenAlexW2028234874MaRDI QIDQ1273096

Steven S. Seiden

Publication date: 23 June 1999

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(98)00019-4

zbMATH Keywords

analysis of algorithmsonline interval schedulingoptimal 4-competitive deterministic algorithm

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (14)

Online interval scheduling on a single machine with finite lookahead ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Primal-dual analysis for online interval scheduling problems ⋮ Approximation algorithms for stochastic online matching with reusable resources ⋮ Online interval scheduling with a bounded number of failures ⋮ Improved Randomized Results for That Interval Selection Problem ⋮ Online C-benevolent job scheduling on multiple machines ⋮ Improved randomized online scheduling of intervals and jobs ⋮ Interval scheduling on related machines ⋮ Improved randomized results for the interval selection problem ⋮ Improved Randomized Online Scheduling of Unit Length Intervals and Jobs ⋮ Online interval scheduling to maximize total satisfaction ⋮ Online interval scheduling: Randomized and multiprocessor cases ⋮ Online scheduling of jobs with fixed start times on related machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Competitive snoopy caching
• On the competitiveness of on-line real-time task scheduling
• On the power of randomization in on-line algorithms
• Randomized competitive algorithms for the list update problem
• On-line scheduling of jobs with fixed start and end times
• Note on scheduling intervals on-line

This page was built for publication: Randomized online interval scheduling