Napoletano, Antonio (2017) On Some Optimization Problems on Dynamic Networks. [Tesi di dottorato]


Download (3MB) | Preview
[error in script] [error in script]
Item Type: Tesi di dottorato
Resource language: English
Title: On Some Optimization Problems on Dynamic Networks
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:
De Giovanni,
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

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 per month over past year

Actions (login required)

View Item View Item