An improved balanced algorithm for the subset-sum problem

Autor(es)

Curtis, V. V. ^[1] ; Sanches, C. A. A. ^[1]

Afiliação do(s) autor(es)

^[1] Inst Tecnol Aeronaut, DCTA, IEC, Praca Mal Eduardo Gomes 50, BR-12228900 Sao Jose Dos Campos, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: European Journal of Operational Research; v. 275, n. 2, p. 460-466, JUN 1 2019.
• Citações Web of Science: 1

Resumo

We present BalsubLast, which is an improved balanced algorithm for the Subset-Sum Problem that was designed to solve benchmarks that require the exhaustion of the search space and where there are many subsets with the same sum. This new algorithm, which spends time O(n(2)w(max)) and space O(n + w(max)), where wmax is the largest of n items, has obtained excellent performance in comparison to other known algorithms. (C) 2018 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 15/18164-5 - Resoluções paralelas de problemas intratáveis em processos industriais
• Beneficiário: Carlos Alberto Alonso Sanches
• Modalidade de apoio: Auxílio à Pesquisa - Regular