Online Appointment Scheduling in the Random Order Model

DOI10.1007/978-3-662-48350-3_57zbMath1466.90033OpenAlexW2240329227MaRDI QIDQ3452831

Thomas Kesselheim, Oliver Göbel, Andreas Tönnis

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48350-3_57

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items

New results for the \(k\)-secretary problem ⋮ Machine covering in the random-order model ⋮ Relative Worst-Order Analysis: A Survey ⋮ Improved Online Algorithms for Knapsack and GAP in the Random Order Model ⋮ Scheduling In the random-order model ⋮ Improved online algorithms for Knapsack and GAP in the random order model

Cites Work

• Unnamed Item
• Unnamed Item
• Competitive analysis of preemptive single-machine scheduling
• On-line scheduling to minimize average completion time revisited.
• LP-based online scheduling: From single to parallel machines
• On-line scheduling on a single machine: Minimizing the total completion time
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• Improved Algorithms and Analysis for Secretary Problems and Generalizations
• Geometry of Online Packing Linear Programs
• Appointment Scheduling with Discrete Random Durations
• A Dynamic Near-Optimal Algorithm for Online Linear Programming
• Online Primal-Dual Algorithms for Covering and Packing
• AdWords and generalized online matching
• Online Stochastic Packing Applied to Display Ad Allocation
• Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
• A Tight 2-Approximation for Preemptive Stochastic Scheduling
• Primal beats dual on online packing LPs in the random-order model
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Models and Algorithms for Stochastic Online Scheduling
• Matroid prophet inequalities