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.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20190107-C-Khazraei.html
END:VEVENT
END:VCALENDAR