Invited Session Wed.3.H 3002

Wednesday, 15:15 - 16:45 h, Room: H 3002

Cluster 23: Telecommunications & networks [...]

Local access networks


Chair: Stefan Gollowitzer



Wednesday, 15:15 - 15:40 h, Room: H 3002, Talk 1

Stefan Gollowitzer
Capacitated network design with facility location

Coauthors: Bernard Gendron, Ivana Ljubic


We consider a network design problem that arises in the design of last mile telecommunication networks. It combines the capacitated network design problem (CNDP) with the single-source capacitated facility location problem (SSCFLP). We will refer to it as the Capacitated connected facility location problem (CapConFL). We develop a basic integer programming model based on multi-commodity flows. Based on valid inequalities for the subproblems, CNDP and SSCFLP, we derive several (new) classes of valid inequalities for the CapConFL. We use them in a branch-and-cut framework and show their applicability on a set of benchmark instances.



Wednesday, 15:45 - 16:10 h, Room: H 3002, Talk 2

Mohsen Rezapour
Approximation algorithms for connected facility location with buy-at-bulk edge costs

Coauthors: Andreas Bley, S. Mehdi Hashemi


We consider a generalization of the Connected Facility Location problem (ConFL), where we need to design a capacitated network with a tree configuration to route client demands to open facilities. In addition to choosing facilities to open and connecting them by a Steiner tree, where each edge of the Steiner tree has infinite capacity, we need to buy cables from an available set of cables with different costs and capacities to route all demands of clients to open facilities via individual trees. We assume that the cable costs obey economies of scale. The objective is to minimize the sum of facility opening, connecting the open facilities and cable installation costs. In this presentation, we give the first approximation algorithm for the problem with K different types of cables. We also consider the simplified version of the problem where capacity of an edge is provided in multiples of only one cable type and give a better constant factor approximation algorithm for this case.



Wednesday, 16:15 - 16:40 h, Room: H 3002, Talk 3

Ashwin Arulselvan
An incremental algorithm for the facility location problem

Coauthors: Olaf Maurer, Martin Skutella


We are given an instance of a facility location problem. We provide an incremental algorithm to obtain a sequence of customers and facilities along with their assignments. The algorithm guarantees that the cost of serving the first k customers in the sequence with their assigned facilities in the sequence is within a constant factor from the optimal cost of serving any k customers. The problem finds applications in facility location problems equipped with planning periods, where facilities are opened and customers are served in an incremental fashion.


  payday loans direct . Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.