[SSC] Dr Salavatipour's Talk

[Mohsen Taghaddosi]

The Students Scientific Chapter announces:

#2.
*
Speaker:* Prof. *Salavatipour*, Department of Computer Science, University
of Alberta

*Title*: Classical Network design problems with extra constraints


*Monday, 10th of Dey, from 12:00 to 13:30
Kharazmi hall CE department *

*Abstract:*
 In this talk we consider some classical network design problems with degree
or order constraints. The first problem we consider is the Survivable
Network Design problem with degree constraints on vertices. The objective is
to find a minimum cost subgraph which satisfies connectivity requirements
between vertices and also degree upper bounds B_v on the vertices. We
present a (2,2B_v+3)-approximation algorithm for the edge-connectivity
Survivable Network Design problem with degree constraints, where the cost of
the returned solution is at most twice the optimum solution (satisfying the
degree bounds) and the degree of each vertex v is at most 2B_v+3. We also
study the problem of finding a minimum cost l-edge-connected subgraph with
at least k vertices. This generalizes some well-studied classical problems
such as the k-minimum-spanning tree and the minimum cost l-edge-connected
subgraph problems. We give a poly-logarithmic approximation for the case of
l=2 and give evidences that the problem might be hard to approximate for
arbitrary large l.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ce.sharif.edu/pipermail/ssc/attachments/20071227/ba37f38b/attachment.htm