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


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.


Talk 2 of the invited session Wed.3.H 3002
"Local access networks" [...]
Cluster 23
"Telecommunications & networks" [...]


  The system of instant Payday Loans Virginia allows any adult U.S. citizen. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Levitra, but also as part of its analogs.