Tighter bounds on a heuristic for a partition problem

DOI10.1016/0020-0190(95)00099-XMaRDI QIDQ1350239zbMATH OpenFDO

Authors O. Diekmann

Publication date 27 February 1997

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

Full work available at URL https://doi.org/10.1016/0020-0190(95)00099-X

zbMATH Keywords

AlgorithmsApproximation algorithmsDiscrete minimizationNP-hardPartitionStorage 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

(15)

• 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
• A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
• Partitioning ideal sets
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• Price of anarchy of scheduling games on hierarchical machines with quadratic social cost
• Title not available (Why is no real title available?)
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
• A new model for selfish routing

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)