|
|
Milestone Year
1998
Approximation algorithms
Many optimization problems are computationally too difficult to solve optimally in reasonable time. A common approach for coping with this difficulty is by the use of approximation algorithms. These are efficient (polynomial time) algorithms that deliver a solution that is not necessarily optimal, but is guaranteed to be close to optimal, an aspect measured by the so called approximation ratio. Over the years, Weizmann scientists have designed approximation algorithms for several well known optimization problems. One such example is an algorithm for approximating the minimum bandwidth of a graph, designed in 1998, which dramatically improved the known approximation ratios for this notoriously difficult problem.
A graph is a set of vertices in which some pairs of vertices are connected by edges. One may envision a graph as a road network, where the roads are the edges and the road junctions are the vertices, and roads might cross over each other (as if there are bridges). The graph has bandwidth b if one can number its vertices by distinct integers such that for every edge the difference between the numbers given to the vertices in its endpoints is at most b, and the aim is to have a bandwidth that is as small as possible. The algorithm developed for approximating the bandwidth is relatively simple to describe and runs very quickly. However, the principles that led to its design and proof of correctness are quite complex, and are based on high dimensional geometry, an area of mathematics that might appear totally unrelated to the problem. Within this area, the process of developing the algorithm involved introducing new concepts ("volume respecting embedding") and analyzing their basic properties.