Computer-assisted proof of performance ratios for the differencing method

DOI10.1016/J.DISOPT.2011.10.001MaRDI QIDQ435724zbMATH OpenOpenAlexFDO

Authors J. Van Leeuwen, Frits C. R. Spieksma, W. Michiels, E. Aarts, J. Korst

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

balanced number partitioningcomputer-assisted proofdifferencing methodexact lp solvermixed integer linear programmingworst-case performance

Mathematics Subject Classification ID

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

Recommendations

• Performance ratios of the Karmarkar-Karp differencing method
• scientific article; zbMATH DE number 2119703
• Difference schemes via computerized searches
• scientific article; zbMATH DE number 4713
• scientific article; zbMATH DE number 4020339
• Computational aspects of the technology of computer differentiation
• Computational divided differencing and divided-difference arithmetics
• A test case for nonlinear difference algorithms
• scientific article; zbMATH DE number 4108029

Cites work

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

Cited in

(5)

• A note on the average-case behavior of a simple differencing method for partitioning
• The modified differencing method for the set partitioning problem with cardinality constraints
• scientific article; zbMATH DE number 1962846 (Why is no real title available?)
• A performance guarantee for the greedy set-partitioning algorithm
• Performance ratios of the Karmarkar-Karp differencing method

Describes a project that uses

Uses Software

• kepler98

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

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