Reusing optimal TSP solutions for locally modified input instances : Extended abstract

Given an instance of an optimization problem together with an optimal solution, we consider the scenario in which this instance is modified locally. In graph problems, e. g., a singular edge might be removed or added, or an edge weight might be varied, etc. For a problem U and such a local modificat...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Hromkovič, Juraj, Böckenhauer, Hans-Joachim, Forlizzi, Luca, Kneis, Joachim, Kupke, Joachim, Proietti, Guido, Widmayer, Peter
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2006
Materias:
Ciencias Informáticas
Optimization
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/24414
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-24414
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Optimization
spellingShingle Ciencias Informáticas
Optimization
Hromkovič, Juraj
Böckenhauer, Hans-Joachim
Forlizzi, Luca
Kneis, Joachim
Kupke, Joachim
Proietti, Guido
Widmayer, Peter
Reusing optimal TSP solutions for locally modified input instances : Extended abstract
topic_facet Ciencias Informáticas
Optimization
description Given an instance of an optimization problem together with an optimal solution, we consider the scenario in which this instance is modified locally. In graph problems, e. g., a singular edge might be removed or added, or an edge weight might be varied, etc. For a problem U and such a local modification operation, let lm-U (local-modification- U) denote the resulting problem. The question is whether it is possible to exploit the additional knowledge of an optimal solution to the original instance or not, i. e., whether lm-U is computationally more tractable than U. Here, we give non-trivial examples both of problems where this is and problems where this is not the case
format Objeto de conferencia
Objeto de conferencia
author Hromkovič, Juraj
Böckenhauer, Hans-Joachim
Forlizzi, Luca
Kneis, Joachim
Kupke, Joachim
Proietti, Guido
Widmayer, Peter
author_facet Hromkovič, Juraj
Böckenhauer, Hans-Joachim
Forlizzi, Luca
Kneis, Joachim
Kupke, Joachim
Proietti, Guido
Widmayer, Peter
author_sort Hromkovič, Juraj
title Reusing optimal TSP solutions for locally modified input instances : Extended abstract
title_short Reusing optimal TSP solutions for locally modified input instances : Extended abstract
title_full Reusing optimal TSP solutions for locally modified input instances : Extended abstract
title_fullStr Reusing optimal TSP solutions for locally modified input instances : Extended abstract
title_full_unstemmed Reusing optimal TSP solutions for locally modified input instances : Extended abstract
title_sort reusing optimal tsp solutions for locally modified input instances : extended abstract
publishDate 2006
url http://sedici.unlp.edu.ar/handle/10915/24414
work_keys_str_mv AT hromkovicjuraj reusingoptimaltspsolutionsforlocallymodifiedinputinstancesextendedabstract
AT bockenhauerhansjoachim reusingoptimaltspsolutionsforlocallymodifiedinputinstancesextendedabstract
AT forlizziluca reusingoptimaltspsolutionsforlocallymodifiedinputinstancesextendedabstract
AT kneisjoachim reusingoptimaltspsolutionsforlocallymodifiedinputinstancesextendedabstract
AT kupkejoachim reusingoptimaltspsolutionsforlocallymodifiedinputinstancesextendedabstract
AT proiettiguido reusingoptimaltspsolutionsforlocallymodifiedinputinstancesextendedabstract
AT widmayerpeter reusingoptimaltspsolutionsforlocallymodifiedinputinstancesextendedabstract
bdutipo_str Repositorios
_version_ 1764820466038472704

Ejemplares similares