Efficient algorithms for discrete optimization problems

  • Sanità, Laura (Recipient)

Prize: NWOVidiScientific


Modern life heavily relies on fast data transmission on networks, time-effective scheduling of trains and airplanes, or facilities such as fire stations or hospitals, being built in strategic locations. All of these are examples of discrete optimization problems, which practitioners face daily and need to solve in a fast and reliable way. Unfortunately, most discrete optimization problems are computationally intractable (NP-hard) and unlikely to admit fast algorithms that always deliver an optimal solution. An effective way to address this intractability is to focus on so-called approximation algorithms: efficient algorithms that yield a solution within a guaranteed factor of the optimum. The investigation of these algorithms started more than 50 years ago, and nowadays this research area is tremendously active. If we inspect the most prestigious conferences in theoretical computer science, we can see that roughly one third of the best paper awards given in the last 10 years went to papers related to approximation algorithms. The main goal of this proposal is to develop approximation algorithms for prominent optimization problems, targeting the areas of (i) network optimization, (ii) algorithmic game theory, and (iii) polyhedral theory. Such problems are of fundamental theoretical significance, but also very meaningful from a practical perspective. In fact, (i) the network optimization problems addressed in this proposal are motivated by real-world optimization problems in telecommunication and logistic networks; (ii) the algorithmic game theory problems in the focus of this proposal model observed selfish behaviors in resource allocation problems; (iii) the polyhedral techniques at the heart of this proposal are heavily exploited by commercial solvers (such as CPLEX or GUROBI), used in the Operations Research industry. The objective is to produce results and methods of prime theoretical relevance, as well as with high potential for applications.
Degree of recognitionNational
Granting OrganisationsNWO