Tighter bounds on a heuristic for a partition problem

DOI10.1016/0020-0190(95)00099-XzbMATH Open0875.68460MaRDI QIDQ1350239FDOQ1350239

Authors 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)

Recommendations

• A tight upper bound for the \(k\)-partition problem on ideal sets
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
• Partitioning ideal sets

Cites Work

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

Cited In (13)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1350239)