Seminars

View all Seminars  |  Download ICal for this event

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

Series: Bangalore Theory Seminars

Speaker: Sándor Fekete, TU Braunschweig

Date/Time: Feb 23 16:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

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.


Microsoft Teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan