Solving the bi-dimensional two-way number partitioning problem with heuristic algorithms

Author

Hacibeyoglu, Mehmet ; Tongur, Vahit ; Alaykiran, Kemal

Author_Institution

Dept. of Comput. Eng., Necmettin Erbakan Univ., Konya, Turkey

fYear

2014

fDate

15-17 Oct. 2014

Firstpage

1

Lastpage

5

Abstract

The two-way number partitioning problem is to divide set of numbers into two subsets. As a result of the dividing process the sums of numbers in subsets must be as nearly equal as possible. The two-way number partitioning problem problem is NP-complete. The bi-dimensional two-way number partitioning problem is a kind of number partitioning problem. The sets have only two coordinates and the aim is minimized the differences of the sum of the numbers for both coordinates. This work presents two heuristic algorithm for solving bi-dimensional two-way number partitioning problem. Fist algorithm is best known and most used greedy algorithm. The other one is a novel genetic algorithm approach. These algorithms are analyzed, implemented and tested on randomly different 20 datasets.

Keywords

computational complexity; genetic algorithms; greedy algorithms; NP-complete; bidimensional two-way number partitioning problem; genetic algorithm; greedy algorithm; heuristic algorithm; Biological cells; Genetic algorithms; Heuristic algorithms; Linear programming; Partitioning algorithms; Sociology; Statistics; Greedy algorithm; combinatorial optimization; genetic algorithm; two-way number partitioning problem;

fLanguage

English

Publisher

ieee

Conference_Titel

Application of Information and Communication Technologies (AICT), 2014 IEEE 8th International Conference on

Conference_Location

Astana

Print_ISBN

978-1-4799-4120-9

Type

conf

DOI

10.1109/ICAICT.2014.7035916

Filename

7035916