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

DOI10.1016/S0167-6377(98)00038-8zbMath0955.90038MaRDI QIDQ1306356

Jacob Shapiro, Robert R. Goldberg

Publication date: 4 March 2001

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

zbMATH Keywords

Lagrange multipliersscheduling theorymathematical programmingNP-completeworst-case analysis

Mathematics Subject Classification ID

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

Related Items (3)

A note on minimizing the sum of squares of machine completion times on two identical parallel machines ⋮ 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

Cites Work

• A greedy heuristic for 3-partitioning with similar elements
• Tighter bounds on a heuristic for a partition problem
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
• Bounds on Multiprocessing Timing Anomalies
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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