Napoletano, Antonio (2017) On Some Optimization Problems on Dynamic Networks. [Tesi di dottorato]
Preview |
Text
Thesis-Antonio-Napoletano.pdf Download (3MB) | Preview |
| Item Type: | Tesi di dottorato |
|---|---|
| Resource language: | English |
| Title: | On Some Optimization Problems on Dynamic Networks |
| Creators: | Creators Email Napoletano, Antonio antonio.napoletano2@unina.it |
| Date: | 6 December 2017 |
| Number of Pages: | 136 |
| Institution: | Università degli Studi di Napoli Federico II |
| Department: | dep12 |
| Dottorato: | phd090 |
| Ciclo di dottorato: | 30 |
| Coordinatore del Corso di dottorato: | nome email De Giovanni, Francesco francesco.degiovanni2@unina.it |
| Tutor: | nome email Festa, Paola UNSPECIFIED |
| Date: | 6 December 2017 |
| Number of Pages: | 136 |
| Keywords: | reoptimization, networks, GRASP |
| Settori scientifico-disciplinari del MIUR: | Area 01 - Scienze matematiche e informatiche > MAT/09 - Ricerca operativa |
| Date Deposited: | 18 Dec 2017 14:03 |
| Last Modified: | 10 Apr 2019 10:45 |
| URI: | http://www.fedoa.unina.it/id/eprint/12063 |
Collection description
The basic assumption of re-optimization consists in the need of eiciently managing huge quantities of data in order to reduce the waste of resources, both in terms of space and time. Re-optimization refers to a series of computational strategies through which new problem instances are tackled analyzing similar, previously solved, problems, reusing existing useful information stored in memory from past computations. Its natural collocation is in the context of dynamic problems, with these latter accounting for a large share of the themes of interest in the multifaceted scenario of combinatorial optimization, with notable regard to recent applications. Dynamic frameworks are topic of research in classical and new problems spanning from routing, scheduling, shortest paths, graph drawing and many others. Concerning our speciic theme of investigation, we focused on the dynamical characteristics of two problems deined on networks: re-optimization of shortest paths and incremental graph drawing. For the former, we proposed a novel exact algorithm based on an auction approach, while for the latter, we introduced a new constrained formulation, Constrained Incremental Graph Drawing, and several meta-heuristics based prevalently on Tabu Search and GRASP frameworks. Moreover, a parallel branch of our research focused on the design of new GRASP algorithms as eicient solution strategies to address further optimization problems. Speciically, in this research thread, will be presented several GRASP approaches devised to tackle intractable problems such as: the Maximum-Cut Clique, p-Center, and Minimum Cost Satisiability.
Downloads
Downloads per month over past year
Actions (login required)
 |
View Item |
