  We introduce a new approach for the numerical pricing of American options.
The main idea is to choose a finite number of suitable excessive functions
(randomly) and to find the smallest majorant of the gain function in the span
of these functions. The resulting problem is a linear semi-infinite programming
problem, that can be solved using standard algorithms. This leads to good upper
bounds for the original problem. For our algorithms no discretization of space
and time and no simulation is necessary. Furthermore it is applicable even for
high-dimensional problems. The algorithm provides an approximation of the value
not only for one starting point, but for the complete value function on the
continuation set, so that the optimal exercise region and e.g. the Greeks can
be calculated. We apply the algorithm to (one- and) multidimensional diffusions
and to L\'evy processes, and show it to be fast and accurate.
