Hard in Theory, Easy in Practice? Solving Hard Optimization Problems in Geometry and Elsewhere скачать в хорошем качестве

Hard in Theory, Easy in Practice? Solving Hard Optimization Problems in Geometry and Elsewhere

Speaker : Sándor Fekete Date : 23rd Feb 2026 Abstract: A main objective of Computer Science and Computational Mathematics is to develop methods for solving challenging algorithmic problems. Often this quest encounters fundamental challenges, like NP-completeness- and resorts to ways in which these obstructions can be sidestepped, e.g., with polynomial-time approximation algorithms or methods for special classes with additional properties. This comes at the risk of focusing on proving mostly theoretical theorems, instead of developing methods for actually computing solutions. In this talk, I will discuss these aspects for a number of NP-hard geometric optimization problems that are quite similar in flavor to the geometric Traveling Salesman Problem (TSP), but turn out to be of fundamentally different practical difficulty. These include Minimum-Weight Triangulation (MWT), Minimum-Dilation Triangulation (MDT) and Minimum-Area Polygonalizations (MAP). In addition, I will also sketch some recent insights into the perspectives of solving classical optimization problems with methods from quantum computing. Link to the talk: https://www.csa.iisc.ac.in/theorysemi...