Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/B85BEFFC-C0E7-4A4D-8891-E4986F9DD5B1 | - |
| Αναγνωριστικό | https://doi.org/10.26233/heallink.tuc.19971 | - |
| Γλώσσα | en | - |
| Μέγεθος | 48 pages | en |
| Τίτλος | Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN) | en |
| Δημιουργός | Sklikas Alexandros | en |
| Δημιουργός | Σκληκας Αλεξανδρος | el |
| Συντελεστής [Επιβλέπων Καθηγητής] | Karystinos Georgios | en |
| Συντελεστής [Επιβλέπων Καθηγητής] | Καρυστινος Γεωργιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Bletsas Aggelos | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Μπλετσας Αγγελος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Samoladas Vasilis | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Σαμολαδας Βασιλης | el |
| Εκδότης | Technical University of Crete | en |
| Εκδότης | Πολυτεχνείο Κρήτης | el |
| Ακαδημαϊκή Μονάδα | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών | el |
| Περιγραφή | Submitted to the Department of Electronic and Computer Engineering in partial fulfilment of the requirements for the ECE Diploma Degree. | en |
| Περίληψη | 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 |
| Τύπος | Διπλωματική Εργασία | el |
| Τύπος | Diploma Work | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2014-07-21 | - |
| Ημερομηνία Δημοσίευσης | 2014 | - |
| Θεματική Κατηγορία | Maximization of a quadratic form | en |
| Βιβλιογραφική Αναφορά | 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 |
| Βιβλιογραφική Αναφορά | Αλέξανδρος Σκλήκας, "Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN)", Διπλωματική Εργασία, Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2014 | el |
Copyright © DIAS 2013
