The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number k c of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time n O(n) + O(n 3 log ∑ c k c ) and requires n ᶿ(n) space. An interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length ∑ c k c of the tour, allowing the algorithm to handle instances with very long tours. The superexponential dependence on the number of cities in both the time and space complexity, however, renders the algorithm impractical for all but the narrowest range of this parameter. In this article, we improve upon the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in time 2 O(n) , i.e., single-exponential in the number of cities, using polynomial space. The space requirement of our algorithm is (essentially) the size of the output, and assuming the Exponential-Time Hypothesis (ETH), the problem cannot be solved in time 2 o(n) . Our algorithm is deterministic, and arguably both simpler and easier to analyze than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number kc of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time nO(n) + O(n3 log Σc kc) and requires nO(n) space. The interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length Σc kc of the tour, allowing the algorithm to handle instances with very long tours, beyond what is tractable in the standard TSP setting. However, its superexponential dependence on the number of cities in both its time and space complexity renders the algorithm impractical for all but the narrowest range of this parameter. In this paper we significantly improve on the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in time 2O(n), i.e. single-exponential in the number of cities, with polynomial space. The space requirement of our algorithm is (essentially) the size of the output, and assuming the Exponential-time Hypothesis (ETH), the time requirement is optimal. Our algorithm is deterministic, and arguably both simpler and easier to analyse than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.

Various industrial control applications have stringent end-to-end latency requirements in the order of a few milliseconds. Software-defined networking (SDN) is a promising solution in order to meet these stringent requirements under varying traffic patterns, as it enables the flexible management of flows across the network. Thus, SDN allows to ensure that traffic flows use congestion-free paths, reducing the delay to forwarding and processing delays at the SDN nodes. However, accommodating new flows at runtime is under such a setting challenging as it may require the migration of existing flows, without interrupting ongoing traffic. In this paper, we consider the problem of dynamic flow migration and propose a polynomial time algorithm that can find a solution if direct flow migration is feasible. We furthermore propose an algorithm for computing both direct and indirect flow migration and prove its correctness. Numerical results obtained on a FatTree network topology show that flow migration is typically necessary for networks with a moderate number of flows, while direct flow migration is feasible in around 60% of the cases.

In this article, we consider k‐way vertex cut: the problem of finding a graph separator of a given size that decomposes the graph into the maximum number of components. Our main contribution is the derivation of an efficient polynomial‐time approximation scheme for the problem on planar graphs. Also, we show that k‐way vertex cut is polynomially solvable on graphs of bounded treewidth and fixed–parameter tractable on planar graphs with the size of the separator as the parameter. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 170–178 2014

In communication networks, resource assignment problems appear in several different settings. These problems are often modeled by a maximum weight matching problem in bipartite graphs and efficient matching algorithms are well known. In several applications, the corresponding matching problem has to be solved many times in a row as the underlying system operates in a time-slotted fashion and the edge weights change over time. However, changing the assignments can come with a certain cost for reconfiguration that depends on the number of changed edges between subsequent assignments. In order to control the cost of reconfiguration, we propose the k-constrained bipartite matching problem for bipartite graphs, which seeks an optimal matching that realizes at most k changes from a previous matching. We provide fast approximation algorithms with provable guarantees for this problem. Furthermore, to cope with the sequential nature of assignment problems, we introduce an online variant of the k-constrained matching problem and derive online algorithms that are based on our approximation algorithms for the k-constrained bipartite matching problem. Finally, we establish the applicability of our model and our algorithms in the context of OFDMA wireless networks finding a significant performance improvement for the proposed algorithms.