Network Optimization

A Multi-Exchange Local Search Algorithm for the Capacitated Facility Location Problem

  • Bo Chen
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Network Optimization Tags , ,

    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

    Speeding up dynamic shortest path algorithms

  • Luciana S. Buriol
  • Mauricio G.C. Resende
  • Mikkel Thorup
    • Categories Network Optimization Tags , , , ,

    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

    The Quadratic Selective Travelling Saleman Problem

  • Thomas R. Stidsen
  • Tommy Thomadsen
    • Categories 0-1 Programming, Branch and Cut Algorithms, Network Optimization Tags , , ,

    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

    Faster Approximation Schemes for Fractional Multicommodity Flow Problems

  • George Karakostas
    • Categories Network Optimization Tags

    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

    A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing

  • Luciana S. Buriol
  • Mauricio G.C. Resende
  • Celso C. Ribeiro
  • Mikkel Thorup
    • Categories Meta Heuristics, Network Optimization, Telecommunications Tags , , , , , ,

    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

    Streaming Cache Placement Problems: Complexity and Algorithms

  • Carlos A. S. Oliveira
  • Panos M. Pardalos
  • Oleg A. Prokopyev
  • Mauricio G.C. Resende
    • Categories Approximation Algorithms, Network Optimization, Telecommunications Tags , , ,

    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

    Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
  • Jerome W. O'Neal
    • Categories Linear Programming, Network Optimization Tags , , , , , , ,

    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

    Design and analysis of an approximation algorithm for Stackelberg network pricing

  • Patrice Marcotte
  • Sébastien Roch
  • Gilles Savard
    • Categories Combinatorial Optimization, Network Optimization Tags , , , ,

    We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of $\frac{1}{2}\log m_T+1$, where … Read more

    An annotated bibliography of network interior point methods

  • Mauricio G.C. Resende
  • Geraldo Veiga
    • Categories Linear Programming, Network Optimization Tags , ,

    This paper presents an annotated bibliography on interior point methods for solving network flow problems. We consider single and multi-commodity network flow problems, as well as preconditioners used in implementations of conjugate gradient methods for solving the normal systems of equations that arise in interior network flow algorithms. Applications in electrical engineering and miscellaneous papers … Read more

    Transparent optical network design with sparse wavelength conversion

  • Arie M.C.A. Koster
  • Adrian Zymolka
  • Roland Wessäly
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Telecommunications Tags , ,

    We consider the design of transparent optical networks from a practical perspective. Network operators aim at satisfying the communication demands at minimum cost. Such an optimization involves three interdependent planning issues: the dimensioning of the physical topology, the routing of lightpaths, and the wavelength assignment. Further topics include the reliability of the configuration and sparse … Read more