The natural approach for describing network flow problems is to introduce side constraints that capture restrictions of a logical or technological nature, e.g., capacity constraints. We study the traffic equilibria arising from selfish routing of individual users in networks with side constraints. We examine first the case of linear latency functions. Under very general assumptions … Read more
The safe dissemination of statistical tabular data is one of the main concerns of National Statistical Institutes (NSIs). Although each cell of the tables is made up of the aggregated information of several individuals, the statistical confidentiality can be violated. NSIs must guarantee that no individual information can be derived from the released tables. One … Read more
In this paper, we consider a modified version of a well-known long-step primal-dual infeasible IP algorithm for solving the linear program $\min\{c^T x : Ax=b, \, x \ge 0\}$, $A \in \Re^{m \times n}$, where the search directions are computed by means of an iterative linear solver applied to a preconditioned normal system of equations. … Read more
We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between $3+2\sqrt{2}-\epsilon$ and $3+2\sqrt{2}+\epsilon$ for any given constant … Read more
Dynamic shortest path algorithms update the shortest paths to take into account a change in an edge weight. This paper describes a new technique that allows the reduction of heap sizes used by several dynamic shortest path algorithms. For unit weight change, the updates can be done without heaps. These reductions almost always reduce the … Read more
A well-known extension of the Travelling Salesman Problem (TSP) is the Selective TSP (STSP): Each node has an associated profit and instead of visiting all nodes, the most profitable set of nodes, taking into account the tour cost, is visited. The Quadratic STSP (QSTSP) adds the additional complication that each pair of nodes have an … Read more
We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of minimal dependency on the number of commodities k. We show that by modifying the algorithms by Garg & Konemann and Fleischer we can reduce their running time to a logarithmic dependence on k, and essentially match the running time … Read more
Intra-domain traffic engineering aims to make more efficient use of network resources within an autonomous system. Interior Gateway Protocols such as OSPF (Open Shortest Path First) and IS-IS (Intermediate System-Intermediate System) are commonly used to select the paths along which traffic is routed within an autonomous system. These routing protocols direct traffic based on link … Read more
Virtual private networks (VPN) are often used to distribute live content, such as video or audio streams, from a single source to a large number of destinations. Streaming caches or splitters are deployed in these multicast networks to allow content distribution without overloading the network. In this paper, we consider two combinatorial optimization problems that … Read more
Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more