Grant: Discovery Grants Program - Individual

Computers rely on algorithms, pre-definied sets of rules, to solve problems. But some problems are simply too difficult and do not allow for an exact solution in a reasonable amount of time even when the input size is modest. In such cases researchers have resorted to ""approximation algorithms"" that work in reasonable amount of time and yet do not compromise too much in the accuracy of their solutions. As the field of approximation algorithms matured, the algorithms that were being designed tended to fall into one of a relatively small number of algorithmic-paradigms. My particular research focuses on some of these approaches, mainly ones that are based on geometric considerations. The first is the ""semidefinte relaxations"" approach, in which we look at a problem with relaxed conditions that is solvable, and the challenge is to relate it with the original one. This technique was shown to be very powerful and has gained much popularity in the last decade. In addition, I study the area of ""metric embedding"" where geometric simplifications are sought in order to transform a hard problem to a simpler one using distances as important parameters. I am also interested in showing limitations these and other algorithmic paradigms, such as dynamic programming, greedy algorithms and backtracking algorithms have. Such insights may indicate new ways of finding algorithmic methods that overcome the obstacles the existing ones suffer from. Last, I am interested in finding sublinear-time algorithms to problems where the typical input size is too large even to be read completely.