Online selection of intervals and \(t\)-intervals

DOI10.1016/j.ic.2013.10.004zbMath1358.68323OpenAlexW1977737452MaRDI QIDQ391644

Magnús M. Halldórsson, Hadas Shachnai, Unnar Th. Bachmann

Publication date: 10 January 2014

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2013.10.004

zbMATH Keywords

competitive analysisonline algorithmsinterval selection

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items

A Randomized Algorithm for Online Scheduling with Interval Conflicts ⋮ Competitive algorithms for multistage online scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using fractional primal-dual to schedule split intervals with demands
• Improved randomized results for the interval selection problem
• Lower bounds for on-line graph coloring
• On-line scheduling of jobs with fixed start and end times
• On the approximability of an interval scheduling problem
• Online independent sets.
• Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms
• An improved randomized on-line algorithm for a weighted interval selection problem
• Optimization problems in multiple-interval graphs
• Bounding the Power of Preemption in Randomized Scheduling
• Interval selection: Applications, algorithms, and lower bounds
• Scheduling Split Intervals