Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN)

Sklikas Alexandros

Simple record


URIhttp://purl.tuc.gr/dl/dias/B85BEFFC-C0E7-4A4D-8891-E4986F9DD5B1-
Identifierhttps://doi.org/10.26233/heallink.tuc.19971-
Languageen-
Extent48 pagesen
TitleMaximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN)en
CreatorSklikas Alexandrosen
CreatorΣκληκας Αλεξανδροςel
Contributor [Thesis Supervisor]Karystinos Georgiosen
Contributor [Thesis Supervisor]Καρυστινος Γεωργιοςel
Contributor [Committee Member]Bletsas Aggelosen
Contributor [Committee Member]Μπλετσας Αγγελοςel
Contributor [Committee Member]Samoladas Vasilisen
Contributor [Committee Member]Σαμολαδας Βασιληςel
PublisherTechnical University of Creteen
PublisherΠολυτεχνείο Κρήτηςel
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστώνel
DescriptionSubmitted to the Department of Electronic and Computer Engineering in partial fulfilment of the requirements for the ECE Diploma Degree.en
Content SummaryWe 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)).en
Type of ItemΔιπλωματική Εργασίαel
Type of ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2014-07-21-
Date of Publication2014-
SubjectMaximization of a quadratic formen
Bibliographic CitationAlexandros Sklikas, "Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN)", Diploma Work, School of Electronic and Computer Engineering, Technical University of Crete, Chania, Greece, 2014en
Bibliographic CitationΑλέξανδρος Σκλήκας, "Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN)", Διπλωματική Εργασία, Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2014el

Available Files

Services

Statistics