FLOW ON DATA NETWORK AND A POSITIVE SEMIDEFINITE REPRESENTABLE DELAY FUNCTION
JÉRÔME GALTER, Alexandre Laugier · Journal of Interconnection Networks · 2007
Data networks are subject to congestion, thereby the delay to go across the network may be large enough in order to dishearten customers to keep on using such a network. In this paper we address the problem of determining in a given network a routing which minimizes the delay or keeps it under a certain bound. This problem was already shown as [Formula: see text] complete. Our main contribution is to study it in the special context of the positive semidefinite programming and we present a column generation approach to solve the underlying problem.