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

Given n positive values x 1, x 2,…, x n , we wish to partition them into two subsets such that the difference between the sums of the subsets is minimized. Karp and Karmarkar have shown that a fairly complicated linear-time differencing algorithm achieves, for a broad class of probability distributi...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 1987-12, Vol.6 (6), p.285-287
Main Author: Lueker, George S
Format: Article
Language:English
Subjects:
Applied sciences
average-case analysis
Exact sciences and technology
Flows in networks. Combinatorial problems
Operational research and scientific management
Operational research. Management science
optimization algorithms
partition problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given n positive values x 1, x 2,…, x n , we wish to partition them into two subsets such that the difference between the sums of the subsets is minimized. Karp and Karmarkar have shown that a fairly complicated linear-time differencing algorithm achieves, for a broad class of probability distributions, a difference of O( n −alog n), for some α > 0, with probability approaching 1 as n → ∞. Their work left open the question of how two simple and more natural implementations of the algorithm behaved. In this paper, under the assumption that the input values are uniformly distributed, we show that one of these algorithms is not nearly so effective, confirming empirical observations of Karp.
ISSN:0167-6377
1872-7468
DOI:10.1016/0167-6377(87)90044-7