Premium
On minimum reload cost paths, tours, and flows
Author(s) -
Amaldi Edoardo,
Galbiati Giulia,
Maffioli Francesco
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20423
Subject(s) - arc (geometry) , mathematical optimization , tree (set theory) , path (computing) , shortest path problem , mathematics , minimum cost flow problem , computer science , function (biology) , steiner tree problem , flow network , combinatorics , graph , geometry , evolutionary biology , biology , programming language
The concept of reload cost, that is of a cost incurred when two consecutive arcs along a path are of different types, naturally arises in a variety of applications related to transportation, telecommunication, and energy networks. Previous work on reload costs is devoted to the problem of finding a spanning tree of minimum reload cost diameter (with no arc costs) or of minimum reload cost. In this article, we investigate the complexity and approximability of the problems of finding optimum paths, tours, and flows under a general cost model including reload costs as well as regular arc costs. Some of these problems, such as shortest paths and minimum cost flows, turn out to be polynomially solvable while others, such as minimum shortest path tree and minimum unsplittable multicommodity flows, are NP ‐hard to approximate within any polynomial‐time computable function. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(3), 254–260 2011