Theory Seminar, Wednesday March 13: Lee-Ad Gottlieb (Ariel) - Near-Linear Time Approximation Schemes for Steiner Tree and Forest in Low-Dimensional Spaces
3 views
Skip to first unread message
Arnold Filtser
Feb 29, 2024, 4:09:09 AMFeb 29
to BIU Theory Seminar, ליעד גוטליב/Lee-Ad Gottlieb
Hi all,
Next week (Wed March 6, at 12:00) the seminar will be open only for registered students.
The week after (Wed March 13, at 12:00) we will meet for our theory seminar with a talk by Lee-Ad Gottlieb.
Next week (Wed March 6, at 12:00) the seminar will be open only for registered students.
The week after (Wed March 13, at 12:00) we will meet for our theory seminar with a talk by Lee-Ad Gottlieb.
Location: Building 503 room 226.
Speaker: Lee-Ad Gottlieb
Title: Near-Linear Time Approximation Schemes for Steiner Tree and Forest in Low-Dimensional Spaces
Abstract: In the Steiner tree and forest problems we are given a set 𝑆 of points, as well as a subset 𝑋 ⊆ 𝑆. The set 𝑆 − 𝑋 constitutes the Steiner
points, and 𝑋 the set of terminals.
The Steiner tree problem is to find a minimal spanning tree for 𝑋, where the tree may also utilize points of 𝑆 − 𝑋.
In the Steiner forest problem, we are also given a set of terminal pairs, and the goal is to find a collection of trees on 𝑆 in which every terminal pair is found in the same tree, and for which the sum of the edge-lengths in all the trees (the trees’ weights) is minimized.
We show how to derive near-linear time algorithms for these classic problems in metric spaces with low doubling dimension. On the way, we'll explore some interesting structural properties underlying these two problems, and how these properties affect the efficiency of the algorithmic solution.
Title: Near-Linear Time Approximation Schemes for Steiner Tree and Forest in Low-Dimensional Spaces
Abstract: In the Steiner tree and forest problems we are given a set 𝑆 of points, as well as a subset 𝑋 ⊆ 𝑆. The set 𝑆 − 𝑋 constitutes the Steiner
points, and 𝑋 the set of terminals.
The Steiner tree problem is to find a minimal spanning tree for 𝑋, where the tree may also utilize points of 𝑆 − 𝑋.
In the Steiner forest problem, we are also given a set of terminal pairs, and the goal is to find a collection of trees on 𝑆 in which every terminal pair is found in the same tree, and for which the sum of the edge-lengths in all the trees (the trees’ weights) is minimized.
We show how to derive near-linear time algorithms for these classic problems in metric spaces with low doubling dimension. On the way, we'll explore some interesting structural properties underlying these two problems, and how these properties affect the efficiency of the algorithmic solution.
Arnold Filtser
Mar 5, 2024, 6:00:26 AMMar 5
to BIU Theory Seminar, ליעד גוטליב/Lee-Ad Gottlieb
Reminder- tomorrow the theory seminar is open only for the registered students.
Next week we will meet for a talk by Lee-Ad Gottlieb.
In the meantime, you can enjoy a talk on Thursday 12 by Klim Efremenko in the colloquium (details in the attached pdf).
See you all there!
Arnold Filtser
Mar 5, 2024, 6:16:02 AMMar 5
to BIU Theory Seminar, ליעד גוטליב/Lee-Ad Gottlieb
Clarification: Klim Efremenko talk is on Thursday the 7th, at 12.
Reply all
Reply to author
Forward
0 new messages