Search

In this paper we study the problem of dynamically update all-pairs shortest paths in a distributed network while edge update operations occur to the network. Most of the previous solutions for this problem suffer of two main limitations: they work under the assumption that before dealing with an edge update operation, the algorithm for each previous operation has to be terminated, that is, they are not able to update shortest paths concurrently; they concurrently update shortest paths, but their convergence can be very slow (possibly infinite) due to the well-known looping and count-to-infinity phenomena; they are not suitable to work in the realistic fully dynamic case, where an arbitrary sequence of edge change operations can occur to the network in an unpredictable way. In this paper, we make a step forward in the area of shortest paths routing, by providing a new fully dynamic solution that overcomes some of the above limitations. In fact, our algorithm is able to concurrently update shortest paths, it heuristically reduces the cases where the looping and count-to-infinity phenomena occur and it is experimentally better than the Bellman-Ford algorithm. [ABSTRACT FROM AUTHOR]

In practical optimization problems, disturbances to a given instance are unavoidable due to unpredictable events which can occur when the system is running. In order to face these situations, many approaches have been proposed during the last years in the area of robust optimization. The basic idea of robustness is to provide a solution which is able to keep feasibility even if the input instance is disturbed, at the cost of optimality. However, the notion of robustness in every day life is much broader than that pursued in the area of robust optimization so far. In fact, robustness is not always suitable unless some recovery strategies are introduced. Recovery strategies are some capabilities that can be used when disturbing events occur, in order to keep the feasibility of the pre-computed solution. This suggests to study robustness and recoverability in a unified framework. Recently, a first tentative of unifying the notions of robustness and recoverability into a new integrated notion of recoverable robustness has been done in the context of railway optimization. In this paper, we review the recent algorithmic results achieved within the recoverable robustness model in order to evaluate the effectiveness of this model. To this aim, we concentrate our attention on two problems arising in the area of railway optimization: the shunting problem and the timetabling problem. The former problem regards the reordering of freight train cars over hump yards while the latter one consists in finding passenger train timetables in order to minimize the overall passengers traveling time. We also report on a generalization of recoverable robustness called multi-stage recoverable robustness which aims to extend recoverable robustness when multiple recovery phases are required. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of planning a timetable for passenger trains considering that possible delays might occur due to unpredictable (but bounded) circumstances. Once arrival and departure events are scheduled, if the timetable cannot be respected since an external event has determined a delay to a train, the so called delay management problem occurs. Delays might be managed in several ways and the usual objective function considered for such purpose is the minimization of the overall waiting time caused to passengers. We analyze the interaction between timetable planning and delay management in terms of the recoverable robustness model, where a timetable is said to be robust if it is able to absorb small delays by possibly applying given recovery capabilities. The quality of a robust timetable is measured by the price of robustness that is the ratio between the cost of the robust timetable and that of a non-robust optimal timetable. We consider the problem of designing robust timetables subject to bounded delays. We show that finding an optimal solution for this problem is NP-hard. Hence, we propose robust algorithms and evaluate their prices of robustness. Moreover, we show that such algorithms are optimal with respect to particular assumptions. [ABSTRACT FROM AUTHOR]

We propose a fully-dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If Δσ is the number of pairs of nodes changing the distance after a single edge modification σ (insert, delete, weight-decrease, or weight-increase) then the message complexity of the proposed algorithm is O (nΔσ)in the worst case, where n is the number of nodes of the network. If $\Delta_{\sigma} = o~(n^2)$, this is better than recomputing everything from scratch after each edge modification. [ABSTRACT FROM AUTHOR]

In this paper we consider Interval Routing Schemes (IRS) that are optimal with respect to the congestion of the induced path system. We provide a general framework able to deal with the various congestion issues in IRS. In fact, it is possible to distinguish between static cases, in which the source-destination configurations are fixed, and dynamic cases, where they vary over time. All these situations can be handled in a unified setting, thanks to the notion of competitiveness introduced in this paper. We first give some general results not related to specific traffic demands. Then, in the one-to-all communication pattern, we show that constructing competitive IRS for a given network is an intractable problem, both for the static and the dynamic case, that is respectively when the root vertex is fixed and when it can change along the time. Finally, both for one-to-all and all-to-all communication patterns, we provide nicely competitive k-IRS for relevant topologies. Networks considered are chains, trees, rings, chordal rings and multi-dimensional grids and tori. We consider both the directed congestion case, in which there are pairwise opposite unidirectional links connecting two neighbor processors, and the undirected congestion case, in which two neighbors are connected by a single bi-directional link. [ABSTRACT FROM AUTHOR]

In this work we introduce graphs with bounded induced distance of order k (BID(k) for short). In any graph belonging to BID(k), the length of every induced path between every pair of nodes is at most k times the distance between the same nodes. In communication networks modeled by these graphs any message can be always delivered through a path whose length is at most k times the best possible one, even if some nodes fail. In this work we first provide a characterization of graphs in BID(k) by means of cycle-chord conditions. After that, we investigate classes with order k ≤ 2. In this context, we note that the class BID(1) is the well known class of distance-hereditary graphs, and show that 3/2 is a lower bound for the order k of graphs that are not distance-hereditary. Then we characterize graphs in BID(2/3) by means of their minimal forbidden induced subgraphs, and we also show that graphs in BID(2) have a more complex characterization. We prove that the recognition problem for the generic class BID(k) is Co-NP-complete. Finally, we show that the split composition can be used to generate graphs in BID(k). [ABSTRACT FROM AUTHOR]