Dutch Optimization Intercity Seminar

CWI is pleased to announce the first Dutch Optimization intercity seminar at CWI . Together with the Dutch Day of Optimization, the intercity seminars will be their in-person events, which will rotate between participating institutions.

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

  • The schedule for the event is as follows:
    2:30pm-3:30pm 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.

  • 3:30pm-4pm Coffee Break
  • 4:00pm-5:00pm William Cook, University of Waterloo

 

Title: An approximate solution to a 2,079,471-point traveling salesman problemAbstract: 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.