Complexity and Approximation in Reoptimization
Escoffier, Bruno; Bonifaci, Vicenzo; Ausiello, Giorgio (2011), Complexity and Approximation in Reoptimization, in Cooper, Barry; Sorbi, Andrea, Computability in Context: Computation and Logic in the Real World, Imperial College Press : Londres
TypeCommunication / Conférence
Conference titleCiE 2007: Logic and Computation and Logic in the Real World
Book titleComputability in Context: Computation and Logic in the Real World
Book authorCooper, Barry; Sorbi, Andrea
Number of pages420
MetadataShow full item record
Abstract (EN)In this survey the following model is considered. We assume that an instance I of a computationally hard optimization problem has been solved and that we know the optimum solution of such instance. Then a new instance I′ is proposed, obtained by means of a slight perturbation of instance I. How can we exploit the knowledge we have on the solution of instance I to compute a (approximate) solution of instance I′ in an efficient way? This computation model is called reoptimization and is of practical interest in various circumstances. In this article we ﬁrst discuss what kind of performance we can expect for speciﬁc classes of problems and then we present some classical optimization problems (i.e. Max Knapsack, Min Steiner Tree, Scheduling) in which this approach has been fruitfully applied. Subsequently, we address vehicle routing problems and we show how the reoptimization approach can be used to obtain good approximate solution in an efficient way for some of these problems.
Subjects / Keywordsoptimization problems
Showing items related by title and author.
Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié