BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: In the well-known Steiner Tree problem\, the objective is to c
 onnect a set of terminals at the least total cost. We can further constrain
  the problem by specifying upper bounds for the distance of each terminal t
 o a chosen root terminal. Further\, using the Lagrangianr elaxation of this
  restriction\, we can penalize large distances in the objective function ra
 ther than applying strict distance constraints. We arrive at a special case
  of the so-called Cost-Distance Steiner Tree Problem in which we have a sin
 gle weight function on the edges.   In this talk\, I will present several r
 esults from my master's thesis that concern the Cost-Distance Steiner Tree 
 Problem. The NP-hardness of the Cost-Distance Steiner Tree Problem triviall
 y follows from the fact that the regular Steiner Tree problem is the specia
 l case where we set demand weights (Lagrange multipliers) of the terminals 
 to zero. I therefore proceed to prove that the problem remains NP-hard in t
 hree restricted cases that do not contain the regular Steiner Tree Problem 
 as a special case. Then I improve on a previous constant-factor approximati
 on for the single-weighted case by using a hybrid method of an approximate 
 Steiner tree with a shortest-path tree replacing sections of the tree where
  path segments are used by many terminals with demand weights summing to hi
 gher than a tunable threshold. I also use a similar approach to extend Aror
 a's dynamic-programming method for the two-dimensional geometric Steiner Tr
 ee Problem to the case with the penalizing terms in the objective function.
  
DTSTAMP:20181229T152800
DTSTART:20190107T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Ardalan Khazraei (Bonn): Cost-distance Steiner trees
UID:95596615@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20190107-C-Kha
 zraei.html
END:VEVENT
END:VCALENDAR