Napoletano, Antonio
(2017)
On Some Optimization Problems on Dynamic Networks.
[Tesi di dottorato]
| Tipologia del documento: |
Tesi di dottorato
|
| Lingua: |
English |
| Titolo: |
On Some Optimization Problems on Dynamic Networks |
| Autori: |
| Autore | Email |
|---|
| Napoletano, Antonio | antonio.napoletano2@unina.it |
|
| Data: |
6 Dicembre 2017 |
| Numero di pagine: |
136 |
| Istituzione: |
Università degli Studi di Napoli Federico II |
| Dipartimento: |
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 | [non definito] |
|
| Data: |
6 Dicembre 2017 |
| Numero di pagine: |
136 |
| Parole chiave: |
reoptimization, networks, GRASP |
| Settori scientifico-disciplinari del MIUR: |
Area 01 - Scienze matematiche e informatiche > MAT/09 - Ricerca operativa |
[error in script]
[error in script]
| Depositato il: |
18 Dic 2017 14:03 |
| Ultima modifica: |
10 Apr 2019 10:45 |
| URI: |
http://www.fedoa.unina.it/id/eprint/12063 |
Abstract
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 per month over past year
Actions (login required)
 |
Modifica documento |
