Exponentially small bounds on the expected optimum of the partition and subset sum problems

DOI<51::AID-RSA3>3.0.CO;2-S 10.1002/(SICI)1098-2418(199801)12:1<51::AID-RSA3>3.0.CO;2-SzbMath0894.90125OpenAlexW4250106264MaRDI QIDQ4379728

George S. Lueker

Publication date: 31 March 1998

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199801)12:1<51::aid-rsa3>3.0.co;2-s

zbMATH Keywords

probabilistic analysispartition problemsubset sum problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (5)

Lattice-based algorithms for number partitioning in the hard phase ⋮ Phase transition and finite-size scaling for the integer partitioning problem ⋮ A physicist's approach to number partitioning ⋮ Random knapsack in expected polynomial time ⋮ Proof of the local REM conjecture for number partitioning. II. Growing energy scales

This page was built for publication: Exponentially small bounds on the expected optimum of the partition and subset sum problems