lu.se

Datavetenskap

Lunds Tekniska Högskola

Kalendarium

Cake seminar by Jakob Nordström: The Computational Challenge of Combinations

Seminarium

Tid: 2023-02-02 14:06 till 15:00
Plats: E:1406
Kontakt: johan [dot] nilsson [at] bme [dot] lth [dot] se
Spara händelsen till din kalender


The E house is now reviving the cake seminars (”tårtseminarierna”). This is a series of seminars aimed at all employees in the E house, and where we get to know newly employed professors and other persons of high importance to the E-house. The seminars are held in E:1406 and start at 14:06. The seminar takes around 30-45 minutes, and after that, cake is served in the Foyer and Glasveranda outside E:1406. Welcome!

The Computational Challenge of Combinations

Prof. Jakob Nordström, Dept of Computer Science, Lund University

Abstract:

Combinatorial solving deals with problems that are solved by combining objects, but where these objects cannot be subdivided to make it easier to find solutions. To see what this means, note that in a power grid we can fine-tune voltages and currents to get the right power distribution, but if we want to distribute packages between delivery trucks, there is no way we can fine-tune the load balance by assigning 90% of a package to one truck and the remaining 10% to another. This fact makes combinatorial problems computationally very challenging. In this talk, I will discuss three aspects of my research on combinatorial problems:

  1. Are we lacking good general-purpose algorithms for combinatorial problems because we just haven't been smart enough, or can one prove mathematically that these problems are somehow inherently hard to solve for computers?
  2. For the type of combinatorial problems that can be solved in practice, can we leverage more sophisticated mathematical tools to get even better performance?
  3. For problems with life-or-death consequences, is there any way we can guarantee that what the computer outputs is in fact a correct solution?