We consider the Shortest Odd Path problem, where given an undirected graph G , a weight function on its edges, and two vertices s and t in G , the aim is to find an ( s , t ) -path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the Shortest Odd Path problem had been open for 20 years, and was recently shown to be NP -hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E − of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between Shortest Odd Path and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. It also relies on solving an intermediary problem variant called Shortest Parity-Constrained Odd Path where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving Shortest Odd Path . The first FPT algorithm is parameterized by | E − | , the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E − , when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G , and the algorithm does not rely on conservativeness.

We present a routing system that considers uncertainties, which are prevalent in any real transport system. Given desired departure or arrival times and a utility function representing the traveller’s preferences, our method computes not just a single path through the network, but a more sophisticated and adaptive journey plan called routing policy. For each stop and time instance, a policy specifies the list of services that the passenger is recommended to take. We show that the problem of finding an optimal policy is NP-hard. We also give a polynomial-time algorithm for a relaxation of the problem when the number of recommended services is limited at each stop and time. A computational case study for the public transport network of Budapest shows that the obtained routing policies can lead to substantial travel time savings compared to deterministic plans, and that considering multiple service policies leads to an improvement compared to previous solutions using single-service policies.

This article investigates the problem of the allocation of modulation and coding, subcarriers and power to users in LTE. The proposed model achieves inter-cell interference mitigation through the dynamic and distributed self-organization of cells. Therefore, there is no need for any a prior frequency planning. Moreover, a two-level decomposition method able to find near optimal solutions is proposed to solve the optimization problem. Finally, simulation results show that compared to classic reuse schemes the proposed approach is able to pack more users into the same bandwidth, decreasing the probability of user outage.

This work presents a novel approach for the avoidance of cross-tier interference in two-tier networks comprised of Orthogonal Frequency Division Multiple Access (OFDMA) macrocells and femtocells. This new technique is based on the use of Intracell HandOvers (IHOs), and it makes possible that either a macrocell or a femtocell can reassign its sub-channel or power allocation upon the detection of cross-tier interference. Simulation results show that this approach is able to cope with the cross-tier interference issues intrinsic to closed access femtocells, and the increased number of HandOvers (HOs) resulting from open access femtocells.

This paper introduces a dynamic system-level simulator for WIMAX (Wireless Interoperability for Microwave Access) networks that can be used to analyze the behavior of several network procedures. Moreover, the performance of a new approach to the frequency assignment problem, called DFP (Dynamic Frequency Planning), is studied using this simulation platform. DFP is able to run from a few times a day down to a frame by frame basis, balancing the radio resources between neighbouring BSs (Base Stations) and providing interference mitigation. We demonstrate the efficacy of DFP compared to off-the-shelf FRSs (Frequency Reuse Schemes) in terms of average network capacity and delay.

Adaptive multi-user resource allocation is one of the key features towards high speed wireless network based on Orthogonal Frequency Division Multiplexing Access (OFDMA). According to IEEE 802.16e (WiMAX) standard radio, resource allocation problem has to be performed on a two-dimensional space (frequency and time) with the constraint that each transmitted burst should occupy a contiguous portion of the frame. The paper introduces two different strategies and it investigates the advantages, drawbacks and challenges of the radio resource allocation procedure in two dimensions.

This work presents 2 novel approaches for the self-organization of Orthogonal Frequency Division Multiple Access (OFDMA) femtocells, in which the femtocell is able to dynamically sense the air interface and tune its sub-channel allocation in order to reduce inter-cell interference and enhance system capacity. In the sensing phase, these techniques make use of either messages broadcast by the femtocells or measurements reported by the users, while in the tuning phase, they provide a good solution for the frequency assignment problem. Results shows that it is recommend to use information collected at the user position (measurement reports), when devising self-organization algorithms for tuning the parameters of femtocells.

In order to avoid inter-cell interference, OFDMA networks are flexible in terms of radio resource management techniques, supporting different frequency reuse schemes (FRSs), which in turn, may decrease inter-cell interference and increase network performance. However, because most of them are based on fix patterns, these FRSs cannot cope with the uneven distribution and dynamic behavior of the traffic throughout the day. This work introduces a novel approach to the frequency assignment problem called dynamic frequency planning (DFP) tailored to OFDMA networks. The proposed approach dynamically adapts the radio frequency parameters to the environment taking the user and channel conditions into account. Moreover, a variant of DFP, called vertical DFP, based on the fractional frequency reuse schemes (FFRSs) concept is proposed. In comparison to the traditional FRSs, these techniques notably mitigate inter-cell interference and enhance network performance.

In this paper, a multiobjective optimization framework that tackles the problem of mobile WiMax access network design is presented. In the first stage of the network development, the most important issue is to find an appropriate solution to the base station location from a given set of candidate sites. The network can be considerably improved if the base station location solution found during the planning phase is designed to achieve optimal performance, and also reliable and cost-effective mobile WiMax networks. The design process is done through computer simulation to predict the network performance, and it is often carried out by planning and optimization tools similar to those used in the development of 2nd generation cellular networks (2G) with a few adaptations. The multiobjective optimization framework gives network providers a new perspective in mobile WiMax access network design, providing a clear and comprehensive description of different options and solutions to achieve an optimal base station location. Also, it analyzes the network performance with the mobile WiMax-specific parameters that most importantly affect the access network design process. It simplifies the problem and translates it into a formal optimization routine with consideration of economic factors in mobile WiMax networks. This has been done by using the method of the Pareto front, and the use of an optimization strategy based on a modified version of the metaheuristic Tabu search adapted to multiobjective optimization.

In this paper we give a method for solving certain budgeted optimization problems in strongly polynomial time. The method can be applied to several known budgeted problems, and in addition we show two new applications. The first one extends Frederickson’s and Solis‐Oba’s result [G. N. Frederickson and R. Solis‐Oba, Combinatorica, 18 (1998), pp. 503–518] to (poly)matroid intersections from single matroids. The second one is the budgeted version of the minimum cost circulation problem.

The hose resource provisioning model promises to provide an easy-to-use characterization framework for virtual private network service offerings. Significant research effort has recently been spent on proposing new algorithms for provisioning cost-optimal networks specified according to this new model. However, a detailed comparison of the bandwidth requirement for networks designed based on the hose model and networks designed based on the traditional pipe model has not been performed. The first contribution of this paper is a detailed comparison of the bandwidth needs of the two models assuming a range of network sizes and network topologies. This numerical evaluation required efficient calculation methods for determining resource allocation based on the hose model parameters, therefore, a linear programming based formulation is also presented for this purpose. The second contribution is the calculation of a lower bound for the hose based realization. This lower bound is very useful in evaluating the two models given that the problem of provisioning a minimal cost network based on the hose model specification can only approximately be solved in polynomial time.

We compare the effectiveness of distributed restoration path computation methods that use head-end precomputation and do not use backup path sharing. Our aim is to provide statistics on primary and secondary path lengths of simple disjoint path computation methods in real-world network topologies. Moreover, we propose a path computation method which can be used when paths are precomputed, but not preestablished. The benefit of this new method is that it intends to select strictly the shortest paths for the working path and for the restoration path as well. We allow common links between the two paths, therefore an additional restoration path is needed. By minimizing the number of common edges between the working and the shortest backup path, our method maximizes the probability that, in the case of a link failure, the shortest backup path can be used for restoration. In the case that the restoration path is a shortest path, it is not necessary to revert to the original working path after the failed link is restored, instead, sub-optimal paths can be re-optimized in the network in order to balance traffic load.

The paper addresses the IP/MPLS network cost optimization problem of selecting the localizations of nodes and links, combined with links' dimensioning. As MPLS is flexible in routing demands' flows through the network, the considered problem is similar to the classical NP-hard topological design problems dealt with in the past, mostly in the context of the road traffic. We assume that the network nodes are composed of two disjoint sets: the set of access nodes (label edge routers) and the set of transit nodes (label switching routers). The access (end) nodes only generate demands and do not transit end-to-end demands' flows, while the transit nodes do not generate demands but do transit the flows. The selection of the actually installed transit nodes and the links interconnecting (all) network nodes is the major subject of optimization. As the considered problem is hard, we discuss and propose branch-and-bound based solution methods. The effectiveness of the methods is illustrated by means of a numerical study.

In this paper a practically efficient QoS routing method is presented, which provides a solution to the delay constrained least cost routing problem. The algorithm uses the concept of aggregated costs and provides an efficient method to find the optimal multiplier based on Lagrange relaxation. This method is proven to be polynomial and it is also efficient in practice. The benefit of this method is that it also gives a lower bound on the theoretical optimal solution along with the result. The difference between the lower bound and the cost of the found path is very small proving the good quality of the result. Moreover, by further relaxing the optimality of paths, an easy way is provided to control the trade-off between the running time of the algorithm and the quality of the found paths. We present a comprehensive numerical evaluation of the algorithm, by comparing it to a wide range of QoS routing algorithms proposed in the literature. It is shown that the performance of the proposed polynomial time algorithm is close to the optimal solution computed by an exponential algorithm.

Multiprotocol label switching (MPLS) technology provides efficient means for controlling the traffic of IP backbone networks and thus, offers performance superior to that of traditional interior gateway protocol (IGP)-based packet forwarding. However, computation of explicit paths yielding optimal network performance is a difficult task; several different strategies can be thought of. We propose a novel approach for the optimal routing of new label switched paths (LSP). Our method is based on the idea that we allow the re-routing of an already established LSP when there is no other way to route the new one. Our optimization algorithm is based on an integer linear programming (ILP) formulation of the problem. We show by numerical evaluation that our method significantly improves the success probability of setting up new LSP by extending the widely known constrained shortest path first (CSPF) algorithm with the ILP-based re-routing function. Although the task itself is NP-hard, our heuristic method provides efficient solution in practical cases. The proposed algorithm is aimed to be implemented primarily in a network operation center. However, with the restriction that only LSP starting from the optimizing label edge routers can be re-routed, the algorithm can be implemented directly in edge routers themselves in a distributed fashion.