Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN)Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN) Διπλωματική Εργασία Diploma Work 2014-07-212014enWe consider the problem of maximizing a quadratic form over the binary alphabet. This problem is known as the unconstrained (−1,1)-quadratic maximization problem or binary quadratic programming (in computer science terminology) and is an NP-hard combinatorial problem that can be solved through an exponential-complexity exhaustive search. Recently, it has been shown that the exhaustive search is not necessary and this problem is polynomially solved, if the rank of the quadratic form is constant (which is a case that is met is certain optimization problems in communication theory). A few polynomial-time algorithms have been reported from several research groups that differ in their actual space and/or time complexity. In this thesis, we focus on the case where the rank of the form is 4 and present an optimal algorithm with complexity O(N^3*log(N)) that is based on novel ideas that combine the auxiliary-angle framework developed in TUC and a few elements from computational geometry. For completeness, we present our method for the cases of rank-2 and rank-3 quadratic forms, with complexity O(N*log(N)) and O(N^2*log(N)), respectively. For all three cases, we show that our algorithm is the fastest known implementable one among the several choices in the literature. Finally, we also comment on how our approach can be generalized to any rank-D quadratic form and lead to an algorithm of complexity O(N^(D-1)*log(N)).Submitted to the Department of Electronic and Computer Engineering in partial fulfilment of the requirements for the ECE Diploma Degree.http://creativecommons.org/licenses/by/4.0/Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών ΥπολογιστώνSklikas_Alexandros_Dip_2014.pdfChania [Greece]Library of TUC2014-07-21application/pdf3.7 MBfree Sklikas Alexandros Σκληκας Αλεξανδρος Karystinos Georgios Καρυστινος Γεωργιος Bletsas Aggelos Μπλετσας Αγγελος Samoladas Vasilis Σαμολαδας Βασιλης Technical University of Crete Πολυτεχνείο Κρήτης Maximization of a quadratic form