Development of Instances Indicators Applicable to the Algorithms Selection in the 2-Partition Problem

  • Ruiz-Vanoye, Jorge A.
  • Pérez-Ortega, Joaquín
  • R., Rodolfo A. Pazos
Abstract:
In this work we approach the problem of transforming instances and complexity indicators between the problems discovered being Bin-Packing and 2-Partition. Several researchers have reductions and polynomial transformations between NP-complete problems, the main ones Garey & Johnson, Karp and Cook. The transformation of 2-Partition into Bin-Packing exists in literature. Nevertheless, does not exist the transformation of Bin-Packing into 2-Partition, nor the transformation of indicators with the purpose of to be used in the selection of algorithms that better solves an instance of the 2-Partition problem. In this thesis a new approach of solution is proposed to transform instances, to develop complexity indicators and to solve the Bin-Packing problem to the 2-Partition problem, by means of a methodology and formal languages to express the instances of both problems.
Research areas:
Year:
2009
Type of Publication:
Article
Journal:
Computación y Sistemas
Volume:
13
Number:
1
Pages:
111-119
ISSN:
1405-5546
Hits: 54