Aristotle University Of Thessaloniki (AUTH)
Algorithms for exact solutions to combinatorial optimization problems
Abstract
dc:descriptionThe Shortest Superstring Problem (SSP) is a combinatorial optimization problem which has attracted the interest of many researchers due to its applications. It can be applied in computational molecular biology problems such as DNA sequencing, and in computer science problems such as string compression. A concise survey for the SSP is presented in the first chapter of this dissertation covering the whole relevant literature, revealing the knowledge that is already conquered, and paving the path for further development in the study of shortest superstrings.A Greedy Randomized Adaptive Search Procedure (GRASP) is an iterative meta-heuristic for combinatorial optimization. Path Relinking (PR) is an approach to integrate intensification and diversification strategies in search for optimal solutions. In this dissertation, an implementation of GRASP with PR for solving the SSP is presented. It solves large scale SSP instances and outperforms the natural greedy algorithm in the majority of the tested instances. The proposed method is able to provide multiple near-optimum solutions that is of practical importance for the DNA sequencing, and admits a natural parallel implementation. A benchmark set of the instances with known optimal solutions was constructed using a new Integer Programming (IP) formulation of the SSP, and used to indicate that the new method finds the optimum in most of the cases, and its average error relative to the optimum is close to zero.The class of the Overlap Graphs is an appropriate data structure for the SSP and other problems that comprise overlapping segments. A weighted directed graph is an overlap graph if there exists a set of strings that is with one-to-one correspondence to the vertices of the graph, such that each weight in the edges of the graph equals the overlap between the corresponding strings. In this dissertation, a characterization theorem for overlap graphs is established, and a polynomial time recognition algorithm is presented.The Quadratic Assignment Problem (QAP) is one of the hardest combinatorial optimization problems. The QAP is NP-hard and even finding an ε-approximation solution for the QAP is a hard problem. The classical greedy algorithm for discrete optimization problems where the optimal solution is a maximal independent subset of a finite ground set of weighted elements, can be defined in two ways which are dual to each other. The greedy-in where a solution is constructed from the empty set by adding the next best element, one at a time, until infeasibility is reached, and the greedy-out where starting from the ground set the next worst element is deleted, one at a time, until feasibility is reached. It is known that while the former provides an approximation ratio for maximization problems, its worst-case performance is not bounded for minimization problems, and vice-versa for the latter. However the greedy-out algorithm requires an oracle for checking the existence of a maximal independent subset which for most discrete optimization problems is a difficult task by itself. In this dissertation, a greedy-out algorithm for the QAP is presented by providing a combinatorial characterization of its solutions.
Degree
thesis:*- Grantor dc:publisher
- Aristotle University Of Thessaloniki (AUTH)
- Year dc:date
- 2013
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Gevezes, Theodoros
- Γκεβεζές, Θεόδωρος
Subjects
dc:subject × 22- Συνδυαστική βελτιστοποίηση
- Υπολογιστική μοριακή βιολογία
- Πρόβλημα βραχύτερης υπερακολουθίας
- Τετραγωνικό πρόβλημα ανάθεσης
- Αλληλούχιση DNA
- Συμπίεση δεδομένων
- Γράφοι επικάλυψης
- Άπληστος αλγόριθμος
- COMBINATORIAL OPTIMIZATION
- Computational molecular biology
- Shortest superstring problem
- Quadratic assignment problem
- DNA sequencing
- Data compression
- Overlap graphs
- Greedy algorithm
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Βιολογία
- Natural Sciences
- Computer and Information Sciences
- Biological Sciences
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/34605