A note on the average-case behavior of a simple differencing method for partitioning

DOI10.1016/0167-6377(87)90044-7zbMATH Open0631.90053OpenAlexW1990990015MaRDI QIDQ1095035FDOQ1095035

Authors: George S. Lueker 

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0167-6377(87)90044-7

Recommendations

• The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
• scientific article; zbMATH DE number 1962846
• Randomized methods for the number partitioning problem
• Probabilistic analysis of optimum partitioning
• Computer-assisted proof of performance ratios for the differencing method

zbMATH Keywords

average-case analysispartition problemdifferencing algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilistic analysis of optimum partitioning
• Title not available (Why is that?)
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics

Cited In (9)

• Algorithmic obstructions in the random number partitioning problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computer-assisted proof of performance ratios for the differencing method
• Performance ratios of the Karmarkar-Karp differencing method
• A note on the complexity of a partition algorithm
• The modified differencing method for the set partitioning problem with cardinality constraints
• Probabilistic analysis of optimum partitioning
• Worst-case analysis of the differencing method for the partition problem

This page was built for publication: A note on the average-case behavior of a simple differencing method for partitioning

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