TR94-16

Easily Searched Encodings for Number Partitioning

    •  Wheeler Ruml, J. Thomas Ngo, Joe Marks, Stuart Shieber, "Easily Searched Encodings for Number Partitioning", Tech. Rep. TR94-16, Mitsubishi Electric Research Laboratories, Cambridge, MA, July 1994.
      BibTeX TR94-16 PDF
      • @techreport{MERL_TR94-16,
      • author = {Wheeler Ruml, J. Thomas Ngo, Joe Marks, Stuart Shieber},
      • title = {Easily Searched Encodings for Number Partitioning},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR94-16},
      • month = jul,
      • year = 1994,
      • url = {https://www.merl.com/publications/TR94-16/}
      • }
Abstract:

Can stochastic search algorithms outperform existing deterministic heuristics for the NP-hard problem NUMBER PARTITIONING if given a sufficient, but practically realizable amount of time? In a thorough empirical investigation using a straightforward implementation of one such algorithm, simulated annealing, Johnson et al. (1991) concluded tentatively that the answer is \"no.\" Keywords & Phrases: Number partitioning, NP-complete, representation, encoding, empirical comparison, stochastic optimization, parameterized arbitration, parameterized constraint, parameterized greediness.