Title:

A little-known interpretation of dynamic programming

Abstract:

Dynamic programming (DP) is a common method for solving decision problems, along with complete enumeration, divide and conquer, branching methods (branch and bound, branch and cut), constraint programming, mathematical programming modeling, etc. We describe the classical key concepts and principles of DP with reference to their historical roots (the works of Andrey Markov and Richard Bellman). Then we present the general ideas of our interpretation of DP, which operates with the concepts of partial solutions, their states, and dominance relation. Our interpretation will be demonstrated using examples of the 0-1 knapsack problem, the dual bin packing problem, the shortest path problem, the traveling salesman problem, and batch scheduling problems. General methods for transforming DP into Fully Polynomial Time Approximation Scheme will be presented last.

Bio:

Mikhail Y. Kovalyov is a principal researcher in the United Institute of Informatics Problems (Minsk, Belarus) and corresponding member of the National Academy of Sciences of Belarus. He has contributed to the theory of fully polynomial time approximation schemes, scheduling, production research, computational complexity, algorithm design, logistics, bio-informatics. He has published in top Operational Research, Computer Science and Industrial Research journals. He serves on the editorial boards of Computers and Operations Research, European Journal of Operational Research, INFORMS Journal on Computing, Omega, OR Spectrum and Journal of Scheduling.

Title:

Spectral Clustering: Basics and Recent Advancements

Abstract:

Spectral clustering is one of the most fundamental clustering algorithms in computer science, and has comprehensive applications in machine learning, parallel and distributed computing, and data science. This talk will introduce the basics of spectral clustering, starting with its roots in spectral graph theory and its connection to eigenvalues and eigenvectors of graph Laplacians, and analyse its performance on real-world datasets.
The second part of the talk will focus on recent advancements in spectral clustering, examining several new directions. I will discuss techniques for designing spectral clustering algorithms in dynamic settings, methods for uncovering more complex cluster structures in distributed environments, and the state-of-the-art for its efficient implementation. This discussion aims to bridge foundational knowledge with the latest developments, offering insights for both practitioners and researchers in theoretical computer science, machine learning, and distributed computing.

Bio:

He Sun is a Reader in the School of Informatics, University of Edinburgh. He received his PhD from Fudan University in 2010 and worked at the Max Planck Institute for Informatics (2010-2014), UC Berkeley (2014), and University of Bristol (2015-2017), before joining the University of Edinburgh in 2017. His research interests include algorithmic spectral graph theory, unsupervised learning, computational geometry, and randomised algorithms.
He received the President's Medal of Fudan University (2004), Shanghai Outstanding PhD Thesis Award (2010), Simons-Berkeley Research Fellowship (2014), and has so far received research grants of about 2.5 million pounds from different research foundations and industrial partners. In 2020, he was awarded an EPSRC Fellowship of 1.5 million pounds for developing advanced spectral algorithms and their open-source implementation.