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

Algorithms; NP-hard; Approximation algorithms; Partition; Discrete minimization; Storage allocation; Worst-case bound

Mathematics Subject Classification ID

68W10: Parallel algorithms in computer science

Related Items

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

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