Online-bounded analysis

DOI10.1007/s10951-017-0536-yzbMath1406.90034OpenAlexW2737179428MaRDI QIDQ1617274

Kim S. Larsen, Leah Epstein, Asaf Levin, Joan. Boyar, Lene Monrad Favrholdt

Publication date: 7 November 2018

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://portal.findresearcher.sdu.dk/da/publications/b778cdc6-109d-4258-8162-daa6373c7916

zbMATH Keywords

machine schedulingonline algorithmsbin packingquality measures

Mathematics Subject Classification ID

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

Related Items

Relative Worst-Order Analysis: A Survey, Comparing the costs of any fit algorithms for bin packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Competitive analysis of maintaining frequent items of a stream
• Fair versus unrestricted bin packing
• On the relative dominance of paging algorithms
• Competitive snoopy caching
• Online algorithms for a dual version of bin packing
• On competitive on-line paging with lookahead
• A new measure for the study of on-line algorithms
• On the influence of lookahead in competitive paging algorithms
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Extending the accommodating function
• Competitive paging with locality of reference
• List factoring and relative worst order analysis
• The seat reservation problem
• Separating online scheduling algorithms with the relative worst order ratio
• Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem
• Tight bounds for bandwidth allocation on two links
• The Accommodating Function: A Generalization of the Competitive Ratio
• The Santa Claus problem
• The relative worst order ratio for online algorithms
• Sleep Management on Multiple Machines for Energy and Flow Time
• Improving the Competitive Ratios of the Seat Reservation Problem
• Bounds for List Schedules on Uniform Processors
• Speed is as powerful as clairvoyance
• Beyond Competitive Analysis
• Markov Paging
• Bounds for Certain Multiprocessing Anomalies
• On-line machine covering
• On paging with locality of reference
• Randomized on-line scheduling on two uniform machines
• On-line bin-stretching