Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/B85BEFFC-C0E7-4A4D-8891-E4986F9DD5B1 | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.19971 | - |
| Language | en | - |
| Extent | 48 pages | en |
| Title | Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN) | en |
| Creator | Sklikas Alexandros | en |
| Creator | Σκληκας Αλεξανδρος | el |
| Contributor [Thesis Supervisor] | Karystinos Georgios | en |
| Contributor [Thesis Supervisor] | Καρυστινος Γεωργιος | el |
| Contributor [Committee Member] | Bletsas Aggelos | en |
| Contributor [Committee Member] | Μπλετσας Αγγελος | el |
| Contributor [Committee Member] | Samoladas Vasilis | en |
| Contributor [Committee Member] | Σαμολαδας Βασιλης | el |
| Publisher | Technical University of Crete | en |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών | el |
| Description | Submitted to the Department of Electronic and Computer Engineering in partial fulfilment of the requirements for the ECE Diploma Degree. | en |
| Content Summary | We 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 Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2014-07-21 | - |
| Date of Publication | 2014 | - |
| Subject | Maximization of a quadratic form | en |
| Bibliographic Citation | Alexandros 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, 2014 | en |
| Bibliographic Citation | Αλέξανδρος Σκλήκας, "Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN)", Διπλωματική Εργασία, Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2014 | el |
Copyright © DIAS 2013
