## 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**

**Abstract:**

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**

**Abstract:**

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**

**Abstract:**

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.