Denis Bouhineau
email: denis.bouhineau@imag.fr

Nadine Mandran
email: nadine.mandran@imag.fr

Sébastien Lallé
email: sebastien.lalle@imag.fr

Michael Ortega
email: michael.ortega@imag.fr

Vanda Luengo
email: vanda.luengo@imag.fr

Claire Wajeman
email: claire.wajeman@imag.fr

Share data treatments and analysis processes in Technology enhanced learning

In the context of our research team (multidisciplinary with numerous and various TEL systems), we have been working during the last three years on the design and implementation of an open platform to collect, save and share experimental data drawn from the interaction with TEL systems, which could build, save and share analysis processes executed on these data. From our point of view both data and analysis processes are worth to be stored and shared, and moreover have to be joined in a unique repository to get the whole picture. This communication presents the analysis processes part of the project.

Sharing analysis processes, i.e. the whole complex process, is rather unusual, whereas contemporary platforms or software already propose generic algorithms to work on data (for instance with a statistical point of view or a data mining point of view). Hence, we attempt to model the main concepts of global treatments for experimental data analysis in order to collect, execute, save and then share them in a platform, dedicated to TEL Systems. The execution part is the most difficult and constraining part of our work. This needs to be implemented with a complex architecture. An important part of the communication is so devoted to the description of the architecture, and to the link between the global point of view of the whole process and the local point of view of elementary or specific algorithms used during the process. A short, but realistic, example of application of our platform is given, with the definition of a global process and the definition of an elementary algorithm used in the global process. The process is executed on real data leading to a graphical display of results, which are then briefly analyzed.

INTRODUCTION

The domain of educational data mining and learning analytics has grown in the last decade thanks to the increase accessibility of educational data. Both research domains propose models (like student models), algorithms, methods (like experimental methods) and tools (like visualization tools or data mining tools) built for the treatment and analysis of the data produced during teaching and learning interactions.

In these domains the algorithms have to be reliable. They have to be reusable for other sets of data or experimental situations and more than one set of data could be necessary to validate the algorithm (cross validation). Also the experimental methods have to be validated and replicable. In contrast, sometimes, a given kind of treatment or visualisation can be more justified or more pertinent for a particular situation constrained by the nature of the data.

Besides, the necessity to build tools, methods and/or processes adapted to the educational specificities is recognised [START_REF] Romero | Educational Data Mining: A Survey from 1995 to 2005[END_REF]. For instance, the generic systems like Weka (for data mining task) or R (for statistical task) are not easy to use or not enough specific for the TEL domain.

In conclusion one way to improve our research domain would be to share not only data but also treatments and analysis processes designed to process and analyse our TEL data. However, like explained in the next section, there currently exist platforms to share specific TEL data on one hand, generic platforms to process this data on the other hand, but there is no TEL open platform which associates both (data and analysis processes specific to TEL). Thus, our objective is to mutualise experimental research in TEL Systems, i.e. to mutualise data but also treatments and analysis processes in the domain of TEL Systems. In this paper we will focus on the second part, i.e. build and mutualise treatments and analysis processes.

FRAMEWORK AND RELATED WORKS

The research in TEL is often multidisciplinary (science education, psychology, computer science, statistics, etc...) and the treatment and analysis methods are numerous (symbolic, numeric,..). In the context of our research team, we collect data in classrooms and use it to conduct some research projects. For example, we have collected data in secondary schools using microworlds (TPELEC 1or Aplusix [START_REF] Bouhineau | Two Years Of Use Of The Aplusix System[END_REF]). These data are used to analyse the learner behaviour [START_REF] Croset | Student's Algebraic Knowledge Modelling: Algebraic Context as Cause of Student's Action[END_REF], to test a diagnostic algorithm [START_REF] Michelet | Experimentation and results for calibrating automatic diagnosis belief linked to problem solving modalities: a case study in electricity[END_REF] or to test a teacher monitoring system [START_REF] Guéraud | Teachers need support too: FORMID-Observer, a Flexible Environment for Supervising Simulation-Based Learning Situations[END_REF].

Besides, because these experimental researches are timeconsuming and difficult to organise, we would like to capitalise the derived treatments and analysis processes, for reusing, improving and validating them. One example is the research project Listen [START_REF] Mostow | Some useful tactics to modify, map and mine data from intelligent tutoring systems[END_REF], which starts in 1996. Since one decade this project collects data. It uses it to improve the proposed system and to understand the student behaviour. The data structures have evolved and the functionalities to browse them also. However their analysis are domain-oriented (reading English). A platform, for browsing and mining temporal and educational data, has also been designed, but as there is no constraint on the format of data, analysis processes can be hardly generalized and reused in other domains or data.

In our case we are interested, for example, in the validation of one hypothesis related to the nature of student knowledge across several domains or in the validation of one kind of learner behaviour monitoring (find contradictions in students' behaviour during problem solving activities), for different learning domains. Thus, we are interested to reuse all or a part of one data processes (i.e. data treatment and analysis process) in order to improve and make more efficient our experimental researches in TEL.

There are some projects offering to share data in TEL domains, like the DataShop project [START_REF] Koedinger | A Data Repository for the EDM community: In Handbook of Educational Data Mining[END_REF], in which the analysis is mainly to find and test models about the learner behaviour or learner knowledge in the context of the interaction with tutors belonging to one learning paradigm (cognitive tutors). In this platform the authors propose one learning curve constructing algorithm (learning curves allow measuring the students' acquisition of skills over time), which works with only one kind of formatted data.

Another project, called Mulce (MUltimodal contextualized Learner Corpus Exchange) [START_REF] Reffay | Multimodal learning and teaching corpora exchange: lessons learned in five years by the Mulce project[END_REF], shares experimental corpuses. They defined the Learning & Teaching Corpus (LETEC) as a package containing data issued from a online course, contextual information, and metadata necessary to these data visible, shareable and reusable. Their objective is to better describe the data collect context. In Mulce, analysis tools are described but externalised.

In these two platforms, most of the analysis algorithms or visualisation tools are not included in the platform. Both authors' platforms emphasize the necessity of making connection with analysis tools.

Concerning algorithms, we find implementations in generic platforms (like Weka or R) or implementations of TEL analysis algorithms made available by researchers (Bayes Net Toolbox for Student Modeling [START_REF] Chang | A Bayes Net Toolkit for Student Modeling in Intelligent Tutoring Systems[END_REF], EDM tools2 , a set of data mining algorithms used in ill-defined domains 3 or Tatiana4 , a set of visualisation algorithms to analyse collaborative data). In a review of specific educational data mining [START_REF] Romero | Educational Data Mining: A Survey from 1995 to 2005[END_REF], statistic and visualization tools are presented. In all cases, some manuals steps are necessary to integrate both data and processes for allowing analysis.

Our objective is to propose an open platform that would be interoperable, flexible and where each tools used, during the data treatment and analysis process, would be reusable. In next sections we describe the foundations of the platform and the architecture used to build and capitalise processes. Before conclusion, an example is detailed.

DATA TREATMENTS AND ANALYSIS PROCESSES DESCRIPTION

The treatment and analysis of activity traces, from a global point of view, cannot be reduced to the use of an unique 'advanced' algorithm (SPC, Bayes, ...). It is a complex process where humans are involved and which can include complex algorithms but also, and quite often, small and simple algorithms such as those which clean or anonymize data. These simple algorithms are usually introduced at the beginning of the process. At the end of the process, we can also observe that there are very often important efforts done to give a graphical presentation, in order to make human interpretation of the results easier. We want to stress here that it is the whole process that we aim to describe, manage, save and share.

In this context we defined a data lifecycle to take into account all possible steps during the treatment and analysis of activity traces.

Figure 1. Data Lifecycle

The whole cycle is described with seven phases: preparation, collection, validation, enrichment, analysis, summarization and communication (figure 1). These phases are organized in a sequential order, but going back to a previous phase is often necessary. However not all phases are mandatory. For instance the enrichment phase could be optional. Each product (transformed data, results, processes ...) of each phase has to be capitalized and could be reused.

In the following, we focus on the data processing step, which is made up of the 4 phases: validation, enrichment, analysis and summarization.

Data processing starts with the validation phase (called data preprocessing in [START_REF] Romero | Educational Data Mining: A Survey from 1995 to 2005[END_REF]), and is executed on the raw data obtained from the collection phase. This phase will necessarily generate a new data set, since the raw data must never be directly altered.

analysis will be performed from these validated data. The validation phase includes both checking and correction the raw data. The validation phase of the raw data is essential to guarantee the meaning given to results and to interpretations [START_REF] Berti-Equille | Modelling and measuring data quality for qualityawareness in data mining[END_REF]. It is frequently composed of small actions necessary to check the variables names, format or value, if data are missing, to identify and correct duplications, remove noise and unlikely data... It also includes the checking of consistency between collected data and what has been planned a priori and the accuracy of values of variables, etc. There are various strategies for performing these checking, like listing and comparing values, cross-tabulation, study of distribution of variables or verification using graphical representations. It can be specific strategies that are defined by the experimental design. This checking phase is usually followed by the appropriate data correction or data improvement operations. In all cases all the operations performed and the results have to be reported in the experimental design. If troubles are identified and no remediation is possible, the researcher must consider how to upgrade the research questions and the experimental design in order to ensure consistency with the available data.

The enrichment phase creates new data for analysis, and more specifically new variables. For example patterns of students' actions are created in this step. Various types of variables may be created using different techniques. For instance recoding of data by grouping modalities creates data with the same data type than the initial data and the data format is not modified. On the contrary, quantitative data that are aggregated from sequential data would provide new data type and new format.

The analysis phase leads to results that support scientific interpretation. It consists in analyzing data, therefore in designing analysis processes, in order to interpret results according to research questions. The processes can be complex and composed of a chain of algorithms (i.e. algorithms executed in a sequential way). For example, in the 1980s, [START_REF] Lebart | Traitement des données statistiques[END_REF] proposed to analyze data with chains of treatments called "Filières". Algorithms of this type have been implemented in statistical software like SPAD, SAS, TANAGRA. A "Filière" is a workflow of algorithms: a statistical treatment may produce new data; from these data a new complementary treatment will be made. Algorithms can perform filtering, apply logical rules, compute descriptive statistics, deliver inferential statistics, produce classification, model, give graphical representations.

The summarization phase allows to extract and to organize the relevant results in order to discuss the research questions formalized a priori or to raise new research questions or hypotheses. This phase may include the construction of summary tables, of clear and intelligible graphics… The summarization process has to be described as well as all other processes.

During the validation phase, the enrichment phase or the analysis phase, regarding the results of processed data obtained the researchers can be lead to add other steps in order to explore the data. Thus, the organization of a processing chain can be elaborated in an empirical manner depending on on-oing results. Furthermore the algorithms used to enrich and analyze the data may follow different analysis paths, i.e. build several chains explored in parallel. Some of these paths are complementary. Some will be abandoned. A conclusive path is the one that gives interesting results about the research question. In each conclusive path, relevant results are kept and reshaped to be used in the summarization phase. Even in a "non-empirical" manner, research questions are generally addressed in several ways, and the exploration of various paths can be planned from the very beginning of the experimental process. As the researcher can freely create, explore and merge several paths during the analysis, then the overall process can be viewed as a directed graph.

Finally some kind of tools could be involved in several phases. For example, visualization tools such as histograms or methods of visual data mining will be implemented for each treatment phases (validation, enrichment, analysis and summary).

The seven phases of the complete described and validated process can be reused on other data or by other researchers. The process could be understood like a cycle where the results of the summarize phase could lead to a new analysis of the same kind of data, which is validated in the platform, or could lead to a new experimental process with a new research question.

In the following, we will distinguish two levels in our modeling: first, a global level concerning the whole process and, secondly, a details level associated with each step of the overall process where each algorithm, each treatment or tool will be described. Our objective is to capitalize both: the details steps and the whole process. Thus it is necessary to propose an architecture which allows the description and the archiving for the global and the details level. Because the process design could be empirical, i.e. we test more than one way to address the problem, the platform has to be flexible.

UNDERTRACKS PLATFORM: COLLECT AND EXECUTE PROCESSES

Each level, the global level and the details level, requires a dedicated implementation for collecting, editing, managing and executing the data processes. We call the concrete part of our work: the "UnderTracks" platform.

First, the global level (the design of the analysis process) needs a specific application to build a process (represented as a graph) and to execute it. This application assists the user in defining the associations between either: the raw data (stored in database's tables) and the algorithms involved in the process, or two algorithms in sequence, meaning that the second one uses the results of the first one. These associations allow a flexible use of algorithms. As our goal is to share and reuse both the algorithms and the processes (processes can be considered as sequences of algorithms), we have to guarantee that associations between data tables and algorithms can be expressed in a generic way, i.e. do not depend on a particular experiment or data. For example, an algorithm designed for sorting elements in a data table should be reusable for sorting students as well as actions, exercises… Finally, concerning the details level, all algorithms must be developed in a way so that they can be really executed. All these notions are described in more details in the following sections.

Architecture Overview

GUI (Process Graph)

... The Process part of UnderTracks (for collecting and executing processes) is composed of four main entities (see Figure 2): -A Graphical User Interface (GUI). This entity allows user to create, load, call the process runner, and then see and recover results. A process is represented by a workflow, which can be considered as a directed acyclic graph. It quite often starts with data from UnderTracks databases (raw data from an experimental study) and leads through sequenced operations to final results.

-A process runner: called "Bricoleur". The process description, which is a graph created with the GUI, is sent to the Bricoleur for execution. This program runs through the graph and delivers data to the different algorithms that compose the process.

-Bricks. A brick is an entity of the process's graph. It can be data or algorithm.

-A DataBase. This entity temporally stores data for each bricks, and it's used for data travelling along the graph. It also stores results and processes.

Next sections present bricks and the GUI in details.

Bricks

Bricks are nodes of the process's workflow. There are three kinds of bricks: data bricks (DB), also called Bricoleur's "raw material", and tool bricks (TB) corresponding to algorithms. Lastly, visualization bricks (VB) aim to present results in a graphical way. DB contains data coming from UnderTracks database, or from previous processes. While creating a process, user usually starts from a DB and plugs TB for adding treatments to it. The TB thus modifies data from the DB. Other DB can be plugged along the workflow, like in Figure 3, until VB. DBs and VBs are natural boundaries of the graph (DBs as sources, VBs as sinks). TBs are natural internal nodes of the graph. Some TB can also be sinks of the graph.

Once the process's workflow is created with the GUI, it is sent to the Bricoleur program, which is in charge of running it. This consists of travelling data from DBs through TBs and VBs. The Bricoleur stores each step's results of the described process into the database.

Tool Bricks Description

TBs can be sequenced into the GUI for building a process. They are simple or complex algorithms, encapsulated in a common description (specific to UnderTracks) for allowing their use and their sequential execution by the Bricoleur. Entry data of TBs can be divided into two categories:

-The table-like data on which the algorithm acts. This data category can be considered as the flow, which is modified and which travels along the workflow. This category of data can come from a DB, directly connected upstream of the TB, or from another TB's result, also connected upstream of the current TB.

-The algorithm tuning values. These are the parameters that describe the algorithm way of acting on table-like data. For instance, a tool that applies a threshold can have one parameter: the threshold value.

By using these two data descriptions, the Bricoleur is able to execute the TB's algorithm and thus able to compute the treatment result. The latter is re-injected into the following bricks and temporally stored into the database. Two kinds of results can be obtained:

-Table-like result. Here data is similar to the first kind of entry data, for allowing the re-injection into the following TB. Notice that TB can either modify/extend the input tables, or create an entirely new data table .  -File result. If anticipated by the developer, the TB algorithm can provide a file result. This file is not re-injected into the workflow, but can be an aside result, with its own format VBs and TBs share the same format for the entry. For the results, VBs produces only a file result, with its own graphical format like, for instance, an HTML page with graphical representation of the results.

Adding Tool Bricks into UnderTracks

TBs and VBs can be developed by anyone, and added to the current UnderTracks platform. A web interface is proposed. It first asks for the TB's or VB's code and description (description of the entry data, of the algorithm, and of the data output). Next, both code and description consistency is checked. If no errors are detected, the code is encapsulated into a specific descriptor for enabling communication between the new TB, VB, the Bricoleur and the database. Finally, both, encapsulated code and description are added into the UnderTracks platform for being used into the GUI.

Building the process

The GUI program is executed on the client side, i.e. on the user's computer. It allows him to construct the process workflow by drag-and-dropping bricks and connecting them (see Figure 3). The connection consists in matching the data coming out from upstream TBs or DBs with the entry of the current TB or VB.

Outcoming and incoming data descriptions are table-like data. Then, connecting two bricks consists in linking outcoming and incoming data columns. For instance, Fig 4 shows the connection between two TBs. Four columns of the upstream brick's result are connected to the five entry columns of the following TB.

Technologies

UnderTracks processes part uses different programming languages:

-GUI has to be launch on the user's computer. It's then developed in JAVA, in order to been portable, i.e. usable on all Operating System.

-The "Bricoleur" program and the tools are placed into the UnderTracks server, and so developed in C++ for being efficient in terms of computing performances.

-Communication between the GUI and the Bricoleur is not direct. Php scripts are used in between, and allow communication via the web, for security and log aspects.

-PostGreSQL is used for the database. This technology seems more adapted to our needs (security, data consistency, strong support of SQL functionalities, …) -For now, algorithms in the TBs and VBs can be developed in C++ or JAVA, according to developer needs.

Add one brick

The implementation of the details level is done with an emphasis on Java and C++. Each tool or algorithm must be written in one of these languages with a standard header for the definition of the main function where parameters meets table, see Fig. 5.

The main function of tools has a standard and simple signature, using input and output objects: respectively UTObjectIn and UTObjectOut (Fig 5). The UTObjectIn class contains the incoming data tables represented as a three-dimensional array of string, and a list of parameters. The three-dimensional array allows to store a list of incoming two dimensional data tables (the incoming flow), while the parameters list is for storing the tuning parameters of the algorithm. The UTObjectOut contains one output data table that can be considered as the outcoming flow, and a file if needed.

Fig. 6 shows the code for a renaming tool which parses a table and changes its third column. The values are processed using a list of keywords, given in the parameter uIn.params [START_REF] Romero | Educational Data Mining: A Survey from 1995 to 2005[END_REF]. In that case, the renaming process replace the found keyword with the value of a given parameter uIn.params[0].

Figure 6 JAVA code of the renaming tool

The list of keywords to be renamed, the name of the replacement word, and the incoming table are given by the user while constructing the process with the GUI. This tool is used in the process presented in next section. It is used for grouping some data (actions), semantically roughly equivalent.

Build a Process

The following process is based on simple activity traces with 4 fields: time, user, action, and action parameters.

The analysis process aims to extract student's behavior from data. To do so, we build the sequence of actions for each student, then we extract couples of successive actions depending on what the researcher want to study. For instance some students consult documents before doing an action whereas others use the trial and error approach.

In more details, the overall process (see Fig. 7, on the left) presents three distinct phases: -The validation, with bricks for cleaning superfluous spaces from the data, for filtering the data with observed actions, and for sorting the data by user and date-time, -The enrichment, with bricks for adding data (construct couples of successive actions for one user) as well as bricks with enrichment tools, which regroup and rename the couples of successive actions according to some more semantic information, (consult document or consult result then make some action), -The results display, with brick which provides some facilities to explore the data (see Fig. 7, right)

The algorithms are quite simple, each code fits on one page (see Fig 6). These tools, all but one, have an input table and parameters, and provide as output another table. The processes main actions are: cleaning, sorting, filtering (the parameter is the list of actions to be removed), and renaming (one parameter is the list of actions to be renamed, the other is the new name to be given, see fig. 6 for the code). The last tool, for the graphical display, has an input table but no output table, its only output is an html page, produced by the tool, with a graphical representation of the data. All these tools are not specific to the definition of this current process and can be used for other analysis.

The result of the process is a graphical representation of the student's behavior (on right side of Fig. 7) which allows to identify different kind of learners: learners which loop lengthily on control (each control followed by another control is represented with a bright big yellow bar; consecutives yellow bars mean multiple control, …), learner with unique control during action phases, or reading phases (each control followed by an action is represented with a dark small bar, or a red big bar for readings; two consecutive small dark bars mean one, and only one, control then one or more actions, done twice, id. for readings), learner with small control loop leading to readings, … The researcher could investigate this result and find some more kind of learners. The researcher could continue and tune the parameters of the process to obtain a better vision of the learners' behaviors. Depending on the results, he can also add new bricks in the process, for instance to extract recurrent or unusual students' behaviors, classify students' behaviors, do pairwise comparison between couples of actions…

DISCUSSION

Research in TEL is a multidisciplinary area including several systems (web, adaptive hypermedia, tutoring systems, microworlds, simulators, LMS,...), and rooted in several learning paradigms and in several interactions paradigms, as well as in several computing paradigms. For example, the field of Educational Data Mining uses data mining and several computational paradigms: decision tree construction, rule induction, Bayesian learning, logic programming, statistical algorithms ... Processing and analysis of TEL data need specific requirements that are not present in other domains. So, it is necessary to specialize adapt works in the TEL domain in order to obtain better results [START_REF] Romero | Educational Data Mining: A Survey from 1995 to 2005[END_REF].

The flexibility and the reusability are the two key features we are looking for. The reuse of data, of algorithms and of analysis processes should improve the efficiency, the reliability and the replicability of our research in the TEL domain. Still, we have to prove that the data collected from several systems, corresponding to various learning paradigms and the algorithms used in our analysis processes, and the analysis processes themselves can be reused in different researches.

To conclude, we propose an architecture and a platform in order to improve experimental researches in the TEL area. The usage of the platform is shown here with a short real example. This platform aims to (1) obtain, improve and share data and analysis processes for TEL, (2) propose specific processes for TEL systems, able to combine several computer science paradigms and (3) prepare a structure able to evaluate data, algorithms and processes in our domain.

Figure 2 .

 2 Figure 2. Architecture of the Process part of UnderTracks (collect and execute global processes)

Figure 3

 3 Figure 3 Example of a process's workflow. Data bricks (DB) are in blue and tool bricks (TB) in yellow

Figure 4

 4 Figure 4 Example of connection between two bricks

Figure 5

 5 Figure 5 Tools profile in JAVA 4.5 Example

  public static UTObjectOut rename(UTObjectIn uIn) { UTObjectOut uOut = new UTObjectOut(); ArrayList<Integer> bufOut=new ArrayList<Integer>(); HashSet<String> keywords = new HashSet<String>(); String parametres []= uIn.params[1].split(" "); for(int i=0;i<parametres.length;i++) { keywords.add(parametres[i]);} uOut.table=new String[uIn.

  table[0].length][uIn.table[0][0 ].length]; for (int i =0;i<uIn.table[0].length;i++) { for(int j=0;j<uIn.table[0][0].length;j++) { uOut.table[i][j] = uIn.table[0][i][j];} if (keywords.contains(uIn.table[0][i][2])) { uOut.table[i][2] = uIn.params[0];}} return uOut;}

tpelec.imag.fr/index.html

http://users.wpi.edu/~rsbaker/edmtools.html

http://www.philippe-fournier-viger.com/spmf/index.php

http://code.google.com/p/tatiana/


Bruno Escoffier
email: escoffier@lamsade.dauphine.fr

Martin Milanič
email: mmilanic@rutcor.rutgers.edu

Vangelis Th

Paschos
email: paschos@lamsade.dauphine.fr

Simple and fast reoptimizations for the Steiner tree problem

Keywords: Steiner tree, approximation algorithms, reoptimization

Nous étudions dans cet article le problème de l'arbre de Steiner du point de vue de la problématique appelée réoptimisation. Nous considérons qu'une solution optimale nous est fournie sur une instance du problème, l'objectif étant de maintenir une bonne solution quand l'instance est sujette à des modifications mineures, par exemple l'insertion ou la suppression d'un sommet. Nous proposons des stratégies de réoptimisation rapides pour le cas de l'insertion d'un ou plusieurs sommets, alors que dans le cas de la suppression d'un sommet, le maintient d'une bonne solution semble délicat. Nous présentons également des bornes inférieures pour les rapports d'approximation obtenues par les stratégies de réoptimisation considérées.

Introduction

Given a graph G = (V, E), a subset R ⊆ V of its vertex-set (the so-called terminal vertices), and nonnegative integer weights {w(e) : e ∈ E} on the edges of G, the Steiner tree problem consists in finding a lightest Steiner tree for (G, R), i.e., a subtree T of G with R ⊆ V (T ) (where the weight of a tree is given by the sum of the weights of its edges).

We will assume in the sequel that the graph G is complete, and that the weights on the edges induce a non-negative integer metric on the subsets of size 2 of V , i.e., that for every three vertices x, y, z ∈ V , the triangle inequality: w(xz) w(xy)+w(xz) holds. Therefore, an instance of the Steiner tree problem is of the form (V, R, w) where R ⊆ V and w is a nonnegative integer metric on V . A Steiner tree for (V, R) is a Steiner tree for ((V, V 2 ), R).

The Steiner tree problem is one of the most famous combinatorial optimization problems in network design. The frequency with which it arises in such applications motivates numerous works on this problem, under several assumptions, hypotheses and models. Steiner tree is well known to be NP-hard. The first approximation algorithm for it appeared in [START_REF] Agrawal | When trees collide: an approximation algorithm for the generalized Steiner problem on networks[END_REF] (see also [START_REF] Gröpl | Approximation algorithms for the Steiner tree problem in graphs[END_REF][START_REF] Vazirani | Approximation algorithms[END_REF]). This algorithm is a primal-dual generalization of the following simple heuristic: compute the shortest paths between all pairs of terminal vertices and then compute a minimum-cost spanning tree over the shortest-path weighted complete graph with vertex-set R. Removal of redundant edges might be needed in order to transform the tree so computed to a Steiner tree of G. The approximation ratio achieved by this algorithm is bounded above by 2. If G is metric, then a minimum-cost spanning tree on the induced subgraph G [R] (in what follows, given a subset V ′ of vertices of a graph G, we denote by G[V ′ ] the subgraph of G induced by V ′ ) achieves the same approximation ratio. This result has been improved in [START_REF] Robins | Improved Steiner tree approximation in graphs[END_REF] down to 1.55 in complete metric graphs and to 1.28 for complete graphs with edge costs 1 and 2. A survey of approximation results for Steiner tree problem can be found in [START_REF] Gröpl | Approximation algorithms for the Steiner tree problem in graphs[END_REF].

In this paper we address the reoptimization issue where the following situation is considered. We are given an optimum solution of an initial instance and we wish to maintain a good solution efficiently, when the instance is slightly modified. This working framework has already been adopted for several optimization problems, such as scheduling problems ([4, 5, 10]) for practical applications, and classical polynomial problems, such as the minimum spanning tree, where the goal is to recompute the optimum solution as fast as possible ( [START_REF] Eppstein | Sparsification -a technique for speeding up dynamic graph algorithms[END_REF][START_REF] Henzinger | Maintaining minimum spanning trees in dynamic graphs[END_REF]). It has been also addressed for the minimum traveling salesman problem in [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF] and, recently for both minimum and maximum traveling salesman problems in [START_REF] Ausiello | Reoptimization of minimum and maximum traveling salesman's tours[END_REF].

For the Steiner tree problem handled here, we assume that an optimal solution T opt has already been computed for a metric complete graph G when some minor modification occurs in the graph. This modification may be the arrival of some (one or more) new vertices together with the edges linking them to G (in such a way that the extended graph G ′ remains complete and metric), or the removal of some vertices of G (together with the edges linking them to the surviving graph). Then, the question is: "can one maintain, or at least modify very quickly the existing solution, in order to obtain a good solution for the modified instance without the need to recompute such a solution thoroughly?". The "goodness" of a solution is measured by computing its approximation ratio. More precisely, if T is a Steiner tree for (V, R), then we say that T is a ρ-approximation for (V, R, w) if w(T ) ρw (T opt ) where T opt is a solution to the Steiner tree problem. We say that ρ is the approximation ratio achieved by T .

In what follows, we propose a simple reoptimization strategy, called REOPT, mainly based upon a minimum spanning tree computation adapted for the case studied (terminal, or nonterminal vertices), that efficiently tackles the case of vertex insertions in the graph. Let us note that most of the approximation algorithms known for the Steiner tree problem seem to be hard to adapt in order to tackle dynamic situations such as the ones handled in this paper. In Section 3, we handle insertion of one vertex x in the initial graph. We provide a tight 3/2-approximation ratio in both cases where x is terminal, or nonterminal. In Section 4, we handle insertions of more than one vertex in the graph. In Section 4.1, we study insertion of p 1 nonterminals and we prove, for this case also, a tight 3/2-approximation ratio for REOPT. On the other hand, in Section 4.2, we assume that p vertices are inserted, k of which being terminals. For this case we show that the ratio of REOPT is 2 -1/(k + 2), while its lower bound is 2 -2/(k + 2). In Section 5, we provide a general lower bound on the approximation ratios for a class of solution structures showing, informally, that if one tries to keep a good approximation ratio for the modified solution, she/he must eventually consider vertices that are not contained in the initial optimal solution.

Finally, for the complementary problem of vertex removals from the initial graph, we show in Section 5 that, sometimes, complete recomputation of a new solution for the "shrunk" instance is unavoidable.

Some easy preliminary results

We give in this section some preliminary results linking approximation of reoptimization to approximation of the Steiner tree problem. They can be seen as simple reductions from the reoptimization context to the classical approximation one. Their proofs, being fairly similar to the ones in Sections 3 and 4, are omitted.

Proposition 1 .

Let T be a ρ-approximation for an instance (V, R, w) of the Steiner tree problem. Suppose that a nonterminal vertex, say x, is added to V together with new edges {xy : y ∈ V } and their weights such that the new instance is again metric. Then, T is a ρ ′ -approximation for the extended instance such that:

ρ ′ 2(1 -(1/|R|))ρ.
The result of Proposition 1 is sharp. Indeed, let the weights of edges connecting the new vertex x to the vertices of R be equal to 1, and let all the remaining edge-weights be equal to 2. If we take the current Steiner tree to be an optimal Steiner tree in G, then w(T ) = 2(|R| -1), while the new optimal weight is |R|. Proposition 2. Let T be a ρ-approximation for an instance (V, R, w) of the Steiner tree problem (with |R| 2). Suppose that a terminal vertex, say x, is added to V together with new edges {xy : y ∈ V } and their weights such that the new instance is again metric. Let T ′ denote the tree T , augmented with a lightest edge connecting a vertex of R with x (ties broken arbitrarily). Then, T ′ is a ρ ′ -approximation for the extended instance such that:

ρ ′ (2 -(1/|R|))ρ.
It is easy to verify that the counterexample of Proposition 1 shows the sharpness of Proposition 2 as well.

One vertex is added

In this section, we consider two cases, according to whether the new vertex is terminal or not.

The new vertex is nonterminal

Let T be an optimum solution for an instance (V, R, w) of the Steiner tree problem. Suppose that a nonterminal vertex, say x, is added to V together with new edges {xy : y ∈ V } and their weights such that the new instance is again metric. Let T x denote a minimum spanning tree on the vertex-set R ∪ {x}.

We consider the algorithm REOPT which consists in computing the best solution between T and T x (ties broken arbitrarily). Obviously, its complexity is the one of computation of a minimum spanning tree on the clique induced by R ∪ {x}, i.e., O(|R| 2 log |R|).

Theorem 1. REOPT is a 3/2-approximation algorithm. This bound is tight.

Proof. Let T denote an optimal Steiner tree in the extended graph, and T ′ the solution computed by REOPT. If x / ∈ V ( T ), then T is optimum (and so is T ′ ). So we may assume that

x ∈ V ( T ). Let {x 1 , . . . , x k } be the set of neighbors of x in V ( T ). Removing x from T results in a forest F consisting of k 1 trees T 1 , . . . , T k with x i ∈ V (T i ) for i ∈ [k] (in what follows, we denote by [k]
the set of integers from 1 to k). Note that k |R|, since every tree T i contains at least one terminal vertex. Let T 0 denote the set of edges adjacent to x in T . Then:

w T = k i=0 w (T i )
Now, link the vertices x 1 , . . . , x k with a path P = (x 1 , . . . , x k ). Together with the trees T i (i 1), this is a Steiner tree on the initial graph, the value of which is at least w(T ). By triangle inequality, we get that w(P ) 2w(T 0 ). Therefore:

w T ′ w(T ) 2w (T 0 ) + k i=1 w (T i ) (1)
On the other hand, let i ∈ [k]. Using an Euler tour on T i (and triangle inequalities), we can easily find a path P i = (x i , v 1 i , . . . , v k i i ) starting in x i and containing all the terminal vertices v 1 i , . . . , v k i i of T i such that w(P i ) 2w(T i ). Then, using again the triangle inequality (w

(xx i ) + w(x i v 1 i ) w(xv 1 i )), we get that the path (x, v 1 i , . . . , v k i i ) has value at most w(xx i ) + 2w(T i ). Then, the union of these k paths (x, v 1 i , . . . , v k i i ) if a Steiner tree T ′′ of value at most w(T 0 ) + 2 k i=1 w(T i ).
Since this is a spanning tree on R ∪ {x}, we obtain:

w T ′ w (T x ) w T ′′ w (T 0 ) + 2 k i=1 w (T i ) (2)
The sum of ( 1) and ( 2) leads to: 2w(T ′ ) 3 k i=0 w(T i ) = 3w( T ), which proves the upper bound claimed.

For the tightness of the bound, consider the following instance (see Figure 1). In the initial graph, there are two groups V 1 and V 2 of n terminal vertices, and one nonterminal vertex v. The weight between v and a vertex in V 1 is equal to 1, as well as the weight between the new vertex x and a vertex in V 2 ; also, the weight between x and v is 1. All other weights are equal to 2. Then, on the initial instance, an optimum solution T is given by the union of all edges between v and a vertex in V 1 and a path starting in v and containing all the vertices in V 2 : w(T ) = 3n.

• • • • • • v x V 1 V 2
Given the symmetry of the final instance, it is easy to see that an optimum spanning tree on R ∪ {x} has the same value. However, the Steiner tree depicted in Figure 1 has value 2n + 1.

Remark 1. If the number of terminal vertices is small, then one can slightly improve the bound of Theorem 1. REOPT is a ρ ′ -approximation algorithm, where:

ρ ′ 2 - 1 2 1 -1 |R| = 3 2 - 1 2(|R| -1)
Indeed, when computing the path P , by triangle inequality we get that w(P ) 2w(T 0 )w(xx 1 ) -w(xx n ). Choosing (without loss of generality) xx 1 and xx n as the two heaviest among the edges xx i , w(P ) 2(1 -1/k)w(T 0 ). Plugging this new inequality in the proof of Theorem 1 leads to the result. Remark 2. One can wonder what happens when, instead of starting with an optimal solution T , we are given a ρ-approximate solution. A slight modification of the proof of Theorem 1 leads to the fact that the solution computed by REOPT is a ρ ′ -approximation, where: ρ ′ min{2, 3ρ/(1 + ρ)} Remark 3. The example given in the proof of Theorem 1 shows that the result is the same even if we consider instances with all the weights 1 or 2.

Remark 4. If we redefine T ′ to be the shortest among T , T x , and T ′′ , where T ′′ denotes a minimum spanning tree on the vertex-set V (T ) ∪ {x}, then the so obtained algorithm again has a tight approximation ratio of 3/2 -Θ(1/|R|).

The new vertex is terminal

In this subsection, we consider the case when the added vertex is terminal. As previously, let T be an optimum solution for an instance (V, R, w) of the Steiner tree problem. Suppose that a terminal vertex, say x, is added to V together with new edges {xy : y ∈ V } and their weights such that the new instance is again metric. Let T x denote a minimum spanning tree on the vertex-set R ∪ {x}, and let T ′′ denote the tree T , augmented with a lightest edge connecting a vertex of R with x.

In this case, REOPT computes the best solution T ′ between T x and T ′′ (ties broken arbitrarily). The complexity of its implementation is O(|R| 2 log |R|).

Theorem 2. REOPT is a 3/2-approximation algorithm. Furthermore, this bound is tight.

Proof. As in the proof of Theorem 1, let x 1 , . . . , x k denote the neighbors of x in an optimum solution T on the extended graph, let T 1 , . . . , T k be the connected components obtained by removing x from T (with x i ∈ V (T i )), and let T 0 be the union of edges xx i . Then w(T ′ ) = k i=0 w(T i ), and, as previously, the minimum spanning tree T x on R ∪ {x} satisfies:

w T ′ w (T x ) w (T 0 ) + 2 k i=1 w (T i ) (3)
If, as in the proof of Theorem 1, we link the vertices x i by a path P 1 = (x 1 , . . . , x n ), then the union of P 1 and T i is a tree of value at most 2w(T 0 ) -w(xx 1 ) -w(xx n ) + k i=1 w(T i ). Then, to get a Steiner tree, we have to connect x. Note that each T i (and in particular T 1 ) has at least one terminal vertex. If we link x to one terminal vertex of T 1 , then this edge has value at most w(xx 1 ) + w(T 1 ).

Since T is an optimum solution on the initial instance, w(T

) 2w(T 0 ) -w(xx 1 ) -w(xx n ) + k i=1 w(T i ).
Moreover, since each terminal vertex is in V (T ), the edge used by REOPT to connect x has value at most w(xx 1 ) + w(T 1 ). Then:

w T ′′ w(T ) + w (xx 1 ) + w (T 1 ) 2w (T 0 ) + k i=1 w (T i ) + w (T 1 ) -w (xx n )
We can do the same thing choosing, instead of T 1 , each of the T j 's:

w T ′′ 2w (T 0 ) + k i=1 w (T i ) + w (T j ) -w (xx j-1 )
Summing up these inequalities leads to:

kw T ′′ (2k -1)w (T 0 ) + (k + 1) k i=1 w (T i ) (4)
Adding (3) with coefficient (k -2) and ( 4) with coefficient 1 gives:

(2k -2)w T ′ (3k -3) k i=0 w(T )
The tightness of the bound follows from the instance given in the proof of Theorem 1 (Figure 1, considering now x as a terminal vertex).

As in Theorem 1, this result can be slightly improved when the number of terminal vertices is small. More precisely, using the fact that we can assume that each nonterminal vertex has degree at least 3 in an optimum solution, one can see that linking x to a terminal vertex of T i costs at most w(xx i ) + w(T i )/2. Using this inequality, we get a ((3/2) -(1/(8|R| -6)))-approximate solution.

Moreover, as previously, if we start from a ρ-approximate solution instead of an optimum one, we get a min{2, 3ρ/(ρ + 1)}-approximate solution.

More vertices are added

In this section, we consider two cases, according to whether a set of nonterminal vertices or a set including terminal and nonterminal vertices is inserted to the current graph.

Nonterminal vertices

Let T be an optimum solution for an instance (V, R, w) of the Steiner tree problem. Suppose that p nonterminal vertices Y = {y 1 , . . . , y p } are added to V together with new edges and their weights such that the new instance is again metric.

We generalize REOPT as follows. For Y ′ ⊆ Y , let T Y ′ denote a minimum spanning tree on the vertex-set R ∪ Y ′ . REOPT computes the best solution T ′ among the trees from {T } ∪ {T Y ′ : Y ′ ⊆ Y } (ties broken arbitrarily). The complexity of this implementation is at most O(2 p (|R| + p) 2 log (|R| + p)). Theorem 3. REOPT is a 3/2-approximation algorithm. This bound is tight.

Proof. Let Ỹ = V ( T )∩Y be the set of new vertices used by an optimum solution T . We consider the connected components T 1 , . . . , T k of the subgraph obtained from T when we remove the new vertices. Moreover, let us denote by X 1 , . . . , X q the connected components of the subgraph obtained from T when we remove the initial vertices. Finally, if in T there is an edge between T i and X j , we denote this edge by e ij . Note that the bipartite graph B = [U, L, Ẽ] where Ẽ is the set of these edges e ij , U = {T i , i = 1, . . . , k} and L = {X j , j = 1, . . . , q}, is a tree. Obviously:

w T = k i=1 w (T i ) + q j=1 w (X i ) + w Ẽ (5)
First, we bound from above the value of the initial solution T . Starting from T , we remove all the X j 's (and edges adjacent to it), in order to get a solution on the initial instance. Consider X j and the edges e ij of T adjacent to it. This is a tree; using a Euler tour on this tree (and removing the vertices in X j ), we can connect the T i 's adjacent to X j using a path P j of value at most 2 w(X j ) + i|e ij ∈ Ẽ w ij . More precisely, if we note d X j = max i|e ij ∈ Ẽ {w(e ij )}, since we compute a path and not a cycle, we can find a path such that:

w (P j ) 2   w (X j ) + i|e ij ∈ Ẽ w ij   -d X j
Replacing all the X j 's (and edges adjacent to it) by the paths P j , we get a solution on the initial instance, the value of which is at least the value of T :

w(T ) k i=1 w (T i ) + 2 q j=1 w (X j ) + 2w Ẽ - q j=1 d X j (6)
Now, we bound from above the value of a minimum spanning tree T Ỹ on R ∪ Ỹ . Starting from T , now we have to remove nonterminal vertices from the T i 's. We use the same technique. Consider T i and the edges e ij of T adjacent to it. Again, this is a tree and using a Euler tour on this tree, we can connect the X j 's adjacent to T i and the terminal vertices of T i (if any) using a path P ′ i . As previously, if we denote d T i = max j|e ij ∈ Ẽ {w(e ij )}, we can find a path such that w(

P ′ i ) 2(w(T i ) + j|e ij ∈ Ẽ w ij ) -d T i .
Replacing the T i 's (and edges adjacent to it) by the P ′ i 's, we get a tree on R ∪ Y , the value of which is at least w(T Ỹ ):

w T Ỹ 2 k i=1 w (T i ) + q j=1 w (X j ) + 2w Ẽ - k i=1 d T i (7)
Summing up ( 6) and ( 7), we get that the solution T ′ computed by REOPT satisfies:

2w T ′ 3 k i=1 w (T i ) + 3 q j=1 w (X j ) + 4w Ẽ - k i=1 d T i - q j=1 d T i
To conclude, using (5), we just have to show that k i=1 d T i + q j=1 d T i w( Ẽ). The left hand side corresponds to summing up, for each vertex in the tree B, the heaviest edge adjacent to this vertex. This sum is obviously greater than the total weight w( Ẽ) of the edges in B: to see this, just consider that w( Ẽ) can be seen as the sum, for each vertex (root excepted), of the edge linking this vertex to its father.

Several terminal and nonterminal vertices are added

Let T be an optimum solution for an instance (V, R, w) of the Steiner tree problem. Suppose that p vertices Y = {y 1 , . . . , y p } are added to V together with new edges and their weights such that the new instance is again metric. Among these p new vertices, Y t = {y 1 , . . . , y t } are terminal, while the remaining p -t are nonterminal.

As in the case where nonterminal vertices are added, for Y ′ such that Y t ⊆ Y ′ ⊆ Y , let T Y ′ denote a minimum spanning tree on the vertex-set R∪Y ′ . Also, we consider a minimum spanning tree T (Y t ) on the new terminal vertices, and link this tree to T using a lightest edge (ties broken arbitrarily) between Y t and V (T ). This gives a solution T ′′ .

Then, REOPT computes the best solution T ′ among the trees from

{T ′′ } ∪ {T Y ′ : T t ⊆ Y ′ ⊆ Y } (ties broken arbitrarily). Theorem 4. REOPT is a (2 -(1/(t + 2)))-approximation algorithm.
Proof. As previously, let us denote by T an optimum Steiner tree of G. The proof of the theorem is based upon the following two cases:

1. the maximum weight w Ter between two terminal vertices (either new or initial) is greater than εw( T ) (the value of ε will be specified later);

2. w Ter εw( T ).

In the first case, let v 0 and v 1 be two terminal vertices such that w(v 0 v 1 ) > εw( T ). Consider the tree T rooted at v 0 , and consider a depth-first visit of T , when v 1 is on the right hand side branch of the tree (the last visited). Then, if we stop this visit when visiting v 1 for the second time, we have a path on all vertices of V ( T ), of value at most 2w( T ) -w(v 0 v 1 ) (thanks to triangle inequalities). Hence, a minimum spanning tree on the terminal vertices has value at most (2 -ε)w( T ).

In the second case, revisit the proof of Theorem 3, in particular [START_REF] Gröpl | Approximation algorithms for the Steiner tree problem in graphs[END_REF] shown there (we use the same notations):

w T Ỹ 2 k i=1 w (T i ) + q j=1 w (X j ) + 2w Ẽ - k i=1 d T i (8)
Note that this solution T Ỹ is still feasible, and w(T ′ ) w T Ỹ . Revisit also [START_REF] Eppstein | Sparsification -a technique for speeding up dynamic graph algorithms[END_REF]:

w(T ) k i=1 w (T i ) + 2 q j=1 w (X j ) + 2w Ẽ - q j=1 d X j (9)
Of course, T is not feasible (as soon as t 1). But since the weight between any two terminal vertices is at most εw( T ), we can connect the t new terminal vertices to an initial one with a path of value at most tεw( T ). In other words, the solution T ′′ satisfies w(T ′′ ) w(T ) + tεw( T ).

Using the fact that w( T ) = k i=1 w(T i ) + q j=1 w(X j ) + w( Ẽ), we get from (9):

w T ′′ (1 + tε) k i=1 w (T i ) + (2 + tε) q j=1 w (X j ) + (2 + tε)w Ẽ - q j=1 d X j (10)
Since T ′ is better than T ′′ and T Ỹ , we can sum up ( 8) and [START_REF] Schäffter | Scheduling with forbidden sets[END_REF]. Using the fact that q j=1 d X j + q j=1 d X j w(E), we obtain:

2w T ′ (3 + tε) k i=1 w (T i ) + (3 + tε) q j=1 w (X j ) + (3 + tε)w Ẽ = (3 + tε)w T So, the solution T ′ is both a (2 -ε)-and a (3 + tε)/2-approximation. Letting ε = 1/(t + 2)
, we obtain the result.

Remark 5. The result of Theorem 4 is independent on the number of nonterminal vertices added. When t = 0, this is the 3/2-approximation for p new nonterminal vertices. Moreover, this bound is almost tight as shown in Theorem 5 (Section 5). Remark 6. The running time is roughly O(max{2 p-t (|R|+p) 2 log(|R|+p), t 2 log t, t|T |}). When the number of new nonterminal vertices is small, this is very quick.

Negative results

In the context of reoptimization, it seems natural to reuse the pre-computed solution when the initial instance is subject to modifications. So, we are interested in particular in algorithms that do not perform ex nihilo computations of a new solution but they rather exploit existing ones. Hence, a natural question is to determine whether it is always possible to maintain a good approximation ratio using only vertices of the initial solution plus, eventually, some newly added ones.

The next result shows that this is not the case. Informally, if we wish to keep a good approximation ratio, we have to consider vertices not contained in the current solution as well.

Theorem 5 .

Let T be an optimum solution for an instance (V, R, w) of the Steiner tree problem, and X be the set of new vertices (either terminal or not). Let A be an algorithm for the reoptimization problem that produces a Steiner tree whose vertex-set is contained in V (T ) ∪ X. Then, the following holds: Proof. We first deal with item 1. We consider the graph G i on 5 vertices {v i , u 1 i , u 2 i , u 3 i , t i } (see Figure 2), with the following weights:

1. if X =
• w(v i u k i ) = 1, for k, l ∈ [3]; • w(u k i u l i ) = 2, for k, l ∈ [3], k = l; • w(t i u k i ) = 4/3, for k ∈ [3]; • w(v i t i ) = 7/3.
The initial graph is composed of n copies G 1 , . . . , G n of G i , where {u k i : k ∈ [3], i ∈ [n]} are terminal vertices, with the following weights, for i, j ∈ [n]:

• w(t i t j ) = 3 -ǫ, for i = j;

• all the other weights (between vertices of different copies) are equal to 4. This instance is metric. An optimum solution T on this instance is given by taking edges t i u k i , for k ∈ [3] and i ∈ [n], and by linking vertices t i by a path (t 1 , . . . , t n ). Its total weight is

w(T ) = 4n + (3 -ǫ)(n -1) ∼ (7 -ǫ)n.
Now, we add the new vertex x, where w(xv i ) = 2, w(xu k i ) = 3, and w(wt i ) = 3 + 4/3 = 13/3 (for k ∈ [3] and i ∈ [n]). Assume that x is nonterminal. Then, x is useless to improve the solution T by considering only vertices in V (T ). However, the solution T consisting in taking the edges xv i and v i u k i , for k ∈ [3] and i ∈ [n], has value 5n. If, on the other hand, x is terminal, the result is the same.

In the case of weights 1 or 2, we can get a similar result with a bound of 4/3. We use the same kind of graph, but instead of considering G i , we consider H i on 4 vertices {v i , u 1 i , u 2 i , t i } (see Figure 3) with the following weights: • w(t i u

• w(v i u k i ) = 1, for k ∈ [2]; 1 1 1 4/3 4/3 4/3 t i u 2 i u 3 i u 1 i v i
k i ) = 1, for k ∈ [2];
• all other weights are equal to 2.

The initial graph is composed of n copies H 1 , . . . , H n of H i , with weight 2 between vertices of different copies. An optimum solution T for this instance is given by taking edges t i u k i , for k ∈ [2] and i ∈ [n], and by linking vertices t i by a path (t 1 , . . . , t n ). Its total weight is w(T ) = 2n + 2(n -1) = 4n -2. Now, we add the new vertex x, where w(xv i ) = 1, i ∈ [n], all other weights being equal to 2. Then, x is useless to improve the solution T by considering only vertices in V (T ).

t i u 2 i u 1 i v i
However, the solution T consisting in taking the edges xv i and v i u k i , for k ∈ [2] and i ∈ [n], has value 3n. This completes the proof of item 1.

For the proof of item 2, i.e., for the case where t terminal vertices are added, consider that the initial graph has 3 vertices v 1 , v 2 , v 3 , with w(v 1 v 2 ) = 2 and w(v 1 v 3 ) = w(v 2 v 3 ) = 1. Vertices v 1 and v 2 are terminal. An optimum solution is T = {v 1 v 2 }. Then, add t terminal vertices, such that the weights between v 3 and the new vertices are 1, and all other weights are 2.

Then, an optimum solution without considering v 3 has value 2(t + 1), whereas a star centered in v 3 has value t + 2.

We now handle reoptimization when a vertex is removed from the graph. We so have an initial instance (V, R, w) of the Steiner tree problem, and one vertex x ∈ V is deleted. Of course, the strategy consisting of computing a minimum spanning tree on the set of surviving terminal vertices is a 2-approximation. If we consider, as previously, algorithms operating on some vertex-set contained in V (T ) \ {x}, then we cannot improve this ratio. Theorem 6. Let T be an optimum solution for an instance (V, R, w) of the Steiner tree problem, and x ∈ V a vertex deleted from the current graph. Let A be an algorithm for the reoptimization problem that produces a Steiner tree whose vertex-set is contained in V (T ) \ {x}. Then, A cannot achieve an approximation ratio better than 2, even if edge-weights are either 1 or 2.

Proof. Let us consider that the initial instance contains n terminal vertices v 1 , . . . , v n , and two nonterminal vertices x and y. Weights between terminal vertices are 2, as well as w(xy), while all other weights are 1. Then a star T on v 1 , . . . , v n centered in x is an optimum solution of the initial instance. When deleting vertex x, the best solution included in T \ {x} is a spanning tree on v 1 , . . . , v n , whose value is 2(n -1), while a star on v 1 , . . . , v n centered in y has value n.

Conclusion

We have presented in this paper simple and fast reoptimization algorithms for the Steiner tree problem. We have handled insertion of one vertex x in the initial graph. We have provided reoptimization techniques achieving tight non-trivial approximation ratios for the cases where one or more vertices are inserted in the initial instance. We also have provided lower bounds showing that good approximation ratios cannot always be obtained without considering vertices that are not contained in the initial optimal solution. Finally, we have shown that when handling vertex-removals, complete recomputation of a new solution for the resulting instance is sometimes unavoidable.

The analysis presented in the paper leaves several open questions that, to our opinion, deserve further research.

1. Can one devise a reoptimization with a ratio better than 3/2 in the case where edge-weights are 1 or 2? We feel that a tight approximation ratio of 4/3 should be possible.

2. The second question deals with the matching of the upper and lower bounds of REOPT in the case where several terminal and nonterminal vertices are added (Section 4.2). Is it possible to get a lower bound of 2 -1/(t + 2), or an upper bound of 2 -2/(t + 2), or finally, to cross them somewhere between? Can the negative result of 7/5 in item 1 of Theorem 5 be tightened?

3. Can we find "general" lower bounds when p nonterminal vertices are added? Is it possible, for instance, to get a bound of 3/2 when p nonterminal vertices are added?

Figure 1 :

 1 Figure 1: Instance with edges of weight 1.

Figure 2 :

 2 Figure 2: Graph G i (other weights correspond to shortest paths).

Figure 3 :

 3 Figure 3: Graph H i with edges of weight 1.

  {x} (one vertex is added, either terminal or not), A cannot achieve an approximation ratio better than 7/5; furthermore, if edge-weights are either 1 or 2, A cannot achieve an approximation ratio better than 4/3; 2. if X = {x 1 , . . . , x t } where, for i ∈ [t], x i is terminal (t terminal vertices are added), A cannot achieve an approximation ratio better than 2 -(2/(t + 2)), even if edge-weights are either 1 or 2.

Part of this work was carried out while the author was with the LAMSADE on a visiting researcher position supported by a common CNRS-NSF research project "Algorithmic Decision Theory" between the LAMSADE and the DIMACS