Search

Flows over time problems consider finding optimal dynamic flows over a network where capacities and transit times on arcs are given. In this paper we study a multicommodity flow over time problem in which no storage of flow at nodes is allowed and solutions are restricted to loopless flow-paths. We propose an exact algorithm based on a column generation approach for a path-based linear programming model and present the results of a preliminary computational study.

Given a graph representing a substrate (or physical) network with node and edge capacities and a set of virtual networks with node capacity demands and node-to-node traffic demands, the Virtual Network Embedding problem (VNE) calls for an embedding of (a subset of) the virtual networks onto the substrate network which maximizes the total profit while respecting the physical node and edge capacities. In this work, we investigate the computational complexity of VNE. In particular, we present a polynomial-time reduction from the maximum stable set problem which implies strong NP-hardness for VNE even for very special subclasses of graphs and yields a strong inapproximability result for general graphs. We also consider the special cases obtained when fixing one of the dimensions of the problem to one. We show that VNE is still strongly NP-hard when a single virtual network request is present or when each virtual network request consists of a single virtual node and that it is weakly NP-hard for the case with a single physical node.

Fair allocation of flows in multicommodity networks has been attracting a growing attention. In Max-Min Fair (MMF) flow allocation, not only the flow of the commodity with the smallest allocation is maximized but also, in turn, the second smallest, the third smallest, and so on. Since the MMF paradigm allows to approximate the TCP flow allocation when the routing paths are given and the flows are elastic, we address the network routing problem where, given a graph with arc capacities and a set of origin-destination pairs with unknown demands, we must route each commodity over a single path so as to maximize the throughput, subject to the constraint that the flows are allocated according to the MMF principle. After discussing two properties of the problem, we describe a column generation based heuristic and report some computational results.