A tight upper bound for the k-partition problem on ideal sets

DOI10.1016/S0167-6377(98)00038-8MaRDI QIDQ1306356zbMATH OpenFDO

Authors Robert R. Goldberg, Jacob Shapiro

Publication date 4 March 2001

Published in Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

mathematical programmingLagrange multipliersNP-completeworst-case analysisscheduling theory

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Partitioning ideal sets
• Partitioning under the \(L_p\) norm
• Tighter bounds on a heuristic for a partition problem

Cites work

• scientific article; zbMATH DE number 52589 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161371 (Why is no real title available?)
• scientific article; zbMATH DE number 6472625 (Why is no real title available?)
• A greedy heuristic for 3-partitioning with similar elements
• Bounds on Multiprocessing Timing Anomalies
• Tighter bounds on a heuristic for a partition problem
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation

Cited in

(6)

• Partitioning under the \(L_p\) norm
• A tight bound for 3-partitioning
• A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
• A note on minimizing the sum of squares of machine completion times on two identical parallel machines
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
• scientific article; zbMATH DE number 1472145 (Why is no real title available?)

This page was built for publication: A tight upper bound for the \(k\)-partition problem on ideal sets

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