Improved randomized results for the interval selection problem

DOI10.1016/J.TCS.2010.04.042MaRDI QIDQ986549zbMATH OpenOpenAlexFDO

Authors 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

online algorithmscompetitive analysisinterval schedulingYao's principle

Mathematics Subject Classification ID

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

Recommendations

• Improved Randomized Results for That Interval Selection Problem
• An improved randomized on-line algorithm for a weighted interval selection problem
• Interval selection: Applications, algorithms, and lower bounds
• Randomized algorithms in interval global optimization
• Optimal selection of stochastic intervals under a sum constraint
• Optimal randomized algorithm for the density selection problem
• Improved algorithms for several parameterized problems based on random methods
• A random-size subset approach to the selection problem
• An improved, randomized algorithm for parallel selection with an experimental study

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• An improved randomized on-line algorithm for a weighted interval selection problem
• Bounding the Power of Preemption in Randomized Scheduling
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Improved Randomized Online Scheduling of Unit Length Intervals and Jobs
• Improved Randomized Results for That Interval Selection Problem
• Interval scheduling: A survey
• Note on scheduling intervals on-line
• On the \(k\)-coloring of intervals
• On-line scheduling of jobs with fixed start and end times
• Online interval scheduling: Randomized and multiprocessor cases
• Randomized online interval scheduling

Cited in

(15)

• An improved online algorithm for the online preemptive scheduling of equal-length intervals on a single machine with lookahead
• Online selection of intervals and \(t\)-intervals
• On-line scheduling of equal-length intervals on parallel machines
• Improved Randomized Results for That Interval Selection Problem
• Interval selection: Applications, algorithms, and lower bounds
• Online Interval Scheduling: Randomized and Multiprocessor Cases
• Online selection of intervals and \(t\)-intervals
• Online interval scheduling with a bounded number of failures
• Improved randomized online scheduling of intervals and jobs
• Online interval scheduling on two related machines: the power of lookahead
• Improved bounds for randomized preemptive online matching
• Online C-benevolent job scheduling on multiple machines
• Online interval scheduling to maximize total satisfaction
• Online scheduling of jobs with fixed start times on related machines
• An improved randomized on-line algorithm for a weighted interval selection problem

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

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