Abstract
The three-partition problem is one of the most famous strongly NP-complete combinatorial problems. We introduce properties which, in many cases, can allow either a quick solution of an instance or a reduction of its size. The average effectiveness of the properties proposed is tested through computational experiments.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Dell'Amico and S. Martello “Optimal scheduling of tasks on identical parallel processors,” ORSA Journal on Computing, vol. 7, pp. 191–200, 1995.
M.R. Garey and D.S. Johnson, “Complexity results for multiprocessors scheduling under resource constraints,” SIAM Journal on Computing, vol. 4, pp. 397–411, 1975.
M.R. Garey, D.S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Mathematics of Operations Research, vol. 1, pp. 117–129, 1976.
M.R. Garey and D.S. Johnson, “Strong” NP-completeness results: Motivation, examples and implications,” Journal of ACM, vol. 25, pp. 499–508, 1978.
M.R. Garey and D.S. Johnson, Computers and Intractability: AGuide to the Theory of NP-Completeness, Freeman: San Francisco, 1979.
J.A. Hoogeveen, J.K. Lenstra, and S.L. van de Velde, “Sequencing and scheduling,” in Annotated Bibliographies in Combinatorial Optimization, M. Dell'Amico, F. Maffioli, and S. Martello (Eds.), Wiley: Chichester, 1997.
J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker, “Complexity of machine scheduling problems,” Annals of Discrete Mathematics, vol. 1, pp. 343–362, 1977.
S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley: Chichester, 1990.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Dell'Amico, M., Martello, S. Reduction of the Three-Partition Problem. Journal of Combinatorial Optimization 3, 17–30 (1999). https://doi.org/10.1023/A:1009856820553
Issue Date:
DOI: https://doi.org/10.1023/A:1009856820553