Computer-assisted proof of performance ratios for the differencing method

DOI10.1016/j.disopt.2011.10.001zbMath1245.90072OpenAlexW2156172303MaRDI QIDQ435724

Jan van Leeuwen, Frits C. R. Spieksma, Wil Michiels, Jan H. M. Korst, Emile H. L. Aarts

Publication date: 12 July 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2011.10.001

zbMATH Keywords

worst-case performancemixed integer linear programmingcomputer-assisted proofbalanced number partitioningdifferencing methodexact lp solver

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27)

Uses Software

• kepler98

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance ratios of the Karmarkar-Karp differencing method
• A note on the average-case behavior of a simple differencing method for partitioning
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• A complete anytime algorithm for number partitioning
• The \(k\)-partitioning problem
• A tight bound for 3-partitioning
• The modified differencing method for the set partitioning problem with cardinality constraints
• Pattern minimisation in cutting stock problems
• A proof of the Kepler conjecture
• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
• Worst-case analysis of the differencing method for the partition problem
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• Every Planar Map is Four Colorable
• An Application of Bin-Packing to Multiprocessor Scheduling
• The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
• Markov chains, computer proofs, and average-case analysis of best fit bin packing
• Bounds on Multiprocessing Timing Anomalies
• A 7/6–Approximation Algorithm For 3-Partitioning And Its Application To Multiprocessor Scheduling
• Min-max subsequence problems in multi-zone disk recording

This page was built for publication: Computer-assisted proof of performance ratios for the differencing method