Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling

DOI10.1137/0221007zbMath0743.68081OpenAlexW2021697340MaRDI QIDQ3990102

Li-Hui Tsai

Publication date: 28 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221007

zbMATH Keywords

makespan schedulingprobabilistic algorithm analysis

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 (15)

\(\kappa\)-partitioning problems for maximizing the minimum load ⋮ Comparing the minimum completion times of two longest-first scheduling-heuristics ⋮ Performance ratios of the Karmarkar-Karp differencing method ⋮ Approximating Scheduling Machines with Capacity Constraints ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ An algebraic expression of the number partitioning problem ⋮ An approximation algorithm for scheduling two parallel machines with capacity constraints. ⋮ Computer-assisted proof of performance ratios for the differencing method ⋮ An algorithm for flow time minimization and its asymptotic makespan properties ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ A physicist's approach to number partitioning ⋮ Proof of the local REM conjecture for number partitioning. I: Constant energy scales ⋮ Unnamed Item ⋮ Faster algorithms for \(k\)-subset sum and variations ⋮ An analysis of the LPT algorithm for the max-min and the min-ratio partition problems

This page was built for publication: Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling