dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

On the Search to Settle the Complexity of Approximating Directed Steiner Tree

  • Start Date: January 22, 2025
  • Event Start Time: 11:00 AM
  • Event End Time: 12:00 PM
  • Seminar Series: Theoretical Computer Science Seminar
  • Presenter(s): Bundit Laekhanukit - Shanghai University of Finance and Economics
  • Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
  • Event Additional Info: <p>See:&nbsp;<a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
  • Presentation Type: Stand Alone Presentation
  • Abstract:

    In the directed Steiner tree problem, we are given an edge-weightedgraph G, a root r, and a set of terminals K. The goal is to find a minimum-cost subgraph of G that connects the root r to every terminal in K. This talk discusses recent progress on approximation algorithms and hardness results for this challenging problem. We will also share a few insights that remain less widely known, highlighting areas where further exploration may prove fruitful.