The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp

DOI10.1287/moor.21.1.85zbMath0846.90057OpenAlexW2040513782WikidataQ123361106 ScholiaQ123361106MaRDI QIDQ4880878

Benjamin Yakir

Publication date: 23 June 1996

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.21.1.85

zbMATH Keywords

makespanbalanced partitioninglargest differencing method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (10)

Performance ratios of the Karmarkar-Karp differencing method ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Computer-assisted proof of performance ratios for the differencing method ⋮ Pattern minimisation in cutting stock problems ⋮ Phase transition and finite-size scaling for the integer partitioning problem ⋮ Proof of the local REM conjecture for number partitioning. II. Growing energy scales ⋮ A complete anytime algorithm for number partitioning ⋮ Unnamed Item ⋮ Heuristics and exact methods for number partitioning

This page was built for publication: The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp