Intercity Seminar

  • When May 04, 2023 from 02:30 PM to 05:00 PM (Europe/Amsterdam / UTC200)
  • Where Room L017 at CWI
  • Contact Name
  • Add event to calendar iCal

Schedule:

2:30pm - 3:30pm: Distributed, Parallel and Dynamic Graph Algorithms (Yasamin Nazari, Vrije Universiteit Amsterdam)

3:30pm - 4:00pm: Coffee Break

4:00pm - 5:00pm: An approximate solution to a 2,079,471-point traveling salesman problem (William Cook, University of Waterloo)


Registration:

As space is limited, please register using the following google form by Friday, 28 April:
https://forms.gle/n4ZPLzkuFxChPWwz7


Livestream Zoom Link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448) 


Speaker: Yasamin Nazari(Vrije Universiteit Amsterdam)

Title: Distributed, Parallel and Dynamic Graph Algorithms

Abstract:

In recent years, there has been a growing interest in designing
algorithms in models that capture different aspects of modern computational
systems and big data processing. This talk focuses on graph algorithms in
several such models, such as distributed, dynamic and parallel models.

We will focus on the task of graph distance computation in these models and
introduce several graph theoretic structures that preserve
approximate distances, but tradeoff this approximation factor with size,
query time, or the number of hops on the approximate shortest paths. We
then show how these combinatorial structures can be utilized for
faster distance computation in distributed or dynamic settings.

Finally, we discuss several open problems including possible connections
with combinatorial optimization.
 
Video:
 
Slides: 
Slides

 


Speaker: William Cook (University of Waterloo)

Title: An approximate solution to a 2,079,471-point traveling salesman problem

Abstract:

Together with Keld Helsguan, we have found a TSP tour through the 3D positions
of 2,079,471 stars. We discuss how linear programming allows us to prove the
tour is at most a factor of 0.0000074 longer than an optimal solution. The talk
will focus on the use of GF(2) linear systems to drive the cutting-plane method
towards improved LP relaxations of the TSP.

Video: