The rate of convergence to optimality of the LPT rule

DOI10.1016/0166-218X(86)90060-0zbMath0611.90058OpenAlexW4213061626MaRDI QIDQ1087469

J. B. G. Frenk, Alexander H. G. Rinnooy Kan

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90060-0

zbMATH Keywords

asymptotic behaviourprobabilistic analysismaximum completion timeheuristic methodspeed of convergenceuniform parallel machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (10)

An introduction to the analysis of approximation algorithms ⋮ List scheduling algorithms to minimize the makespan on identical parallel machines ⋮ Approximate algorithms for the \(P\parallel C_{\max}\) problem ⋮ Performance ratios of the Karmarkar-Karp differencing method ⋮ Ordinal Maximin Share Approximation for Goods ⋮ A note on posterior tight worst-case bounds for longest processing time schedules ⋮ The LPT heuristic for minimizing total load on a proportionate openshop ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ The unbiased black-box complexity of partition is polynomial ⋮ Unnamed Item

Cites Work

• An introduction to the analysis of approximation algorithms
• On Bahadur's representation of sample quantiles
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Bounds on Multiprocessing Timing Anomalies
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The rate of convergence to optimality of the LPT rule