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 main criterion for them is your ability to repay any Wisconsin Loans Online, they are not interested in your previous attempts, the current one is all that matters. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.