#### 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.