Heuristics and exact methods for number partitioning

• Type: Article in International Scientific Journal
• Date: 2010

Authors

Joao Pedro Pedroso (Author) FCUP; Kubo, M (Author) Other

Journal

Title: European Journal of Operational Research

Vol. 202

Pages: 73-81

ISSN: 0377-2217

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 15 Citations

ISI Web of Science

Scopus - 15 Citations

Current Contents

Scientific classification

FOS: Natural sciences > Computer and information sciences

CORDIS: Physical sciences > Computer science

Other information

Authenticus ID: P-003-7RK

DOI: 10.1016/j.ejor.2009.04.027

Abstract (EN): Number partitioning is a classical NP-hard combinatorial optimization problem, whose solution is challenging for both exact and approximative methods. This work presents a new algorithm for number partitioning, based on ideas drawn from tree search, breadth first search, and beam search. A new set of benchmark instances for this problem is also proposed. The behavior of the new method on this and other testbeds is analyzed and compared to other well known heuristics and exact algorithms.

Language: English

Type (Professor's evaluation): Scientific

Notes: Keywords: Number partitioning problem; Tree search; Heuristics; Combinatorial optimization. - Disponível em: http://linkinghub.elsevier.com/retrie...

No. of pages: 9