Open AccessANALYSIS OF THE 2-SUM PROBLEM AND THE SPECTRAL ALGORITHM
Author(s) -
Alexander Kolomiychuk
Publication year - 2014
Publication title -
computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.184
H-Index - 11
eISSN - 2312-5381
pISSN - 1727-6209
DOI - 10.47839/ijc.8.2.676
Subject(s) - algorithm , heuristic , mathematics , quadratic equation , computation , computer science , mathematical optimization , combinatorics , geometry
This paper presents the analysis of the 2-sum problem and the spectral algorithm. The spectral algorithm was proposed by Barnard, Pothen and Simon in [1]; its heuristic properties have been advocated by George and Pothen in [4] by formulation of the 2-sum problem as a Quadratic Assignment Problem. In contrast to that analysis another approach is proposed: permutations are considered as vectors of Euclidian space. This approach enables one to prove the bound results originally obtained in [4] in an easier way. The geometry of permutations is considered in order to explain what are ‘good’ and ‘pathological’ situations for the spectral algorithm. Upper bounds for approximate solutions generated by the spectral algorithm are proved. The results of numerical computations on (graphs of) large sparse matrices from real-world applications are presented to support the obtained results and illustrate considerations related to the ‘pathological’ cases.