Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

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

Sklikas Alexandros

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/B85BEFFC-C0E7-4A4D-8891-E4986F9DD5B1-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.19971-
Γλώσσαen-
Μέγεθος48 pagesen
ΤίτλοςMaximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN)en
ΔημιουργόςSklikas Alexandrosen
ΔημιουργόςΣκληκας Αλεξανδροςel
Συντελεστής [Επιβλέπων Καθηγητής]Karystinos Georgiosen
Συντελεστής [Επιβλέπων Καθηγητής]Καρυστινος Γεωργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Bletsas Aggelosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Μπλετσας Αγγελοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Samoladas Vasilisen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Σαμολαδας Βασιληςel
ΕκδότηςTechnical University of Creteen
ΕκδότηςΠολυτεχνείο Κρήτης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 Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2014-07-21-
Ημερομηνία Δημοσίευσης2014-
Θεματική ΚατηγορίαMaximization of a quadratic formen
Βιβλιογραφική Αναφορά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, 2014en
Βιβλιογραφική ΑναφοράΑλέξανδρος Σκλήκας, "Maximization of a rank-4 quadratic form by a binary vector with complexity O(N^3logN)", Διπλωματική Εργασία, Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2014el

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά