Tighter bounds on a heuristic for a partition problem

DOI10.1016/0020-0190(95)00099-XzbMath0875.68460MaRDI QIDQ1350239

O. Diekmann

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

AlgorithmsNP-hardApproximation algorithmsPartitionDiscrete minimizationStorage allocationWorst-case bound

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (13)

A note on minimizing the sum of squares of machine completion times on two identical parallel machines ⋮ Partitioning ideal sets ⋮ A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines ⋮ The benefit of preemption with respect to the \(\ell_p\) norm ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines ⋮ A new model for selfish routing ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ Load balancing of temporary tasks in the \(\ell _{p}\) norm ⋮ Partitioning under the \(L_p\) norm ⋮ A tight upper bound for the \(k\)-partition problem on ideal sets ⋮ Extending Graham's result on scheduling to other heuristics ⋮ An analysis of the LPT algorithm for the max-min and the min-ratio partition problems

Cites Work

• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
• Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Tighter bounds on a heuristic for a partition problem