Design and Analysis of Randomized and Approximation Algorithms

Preliminary Motivation Text

Many computational tasks that arise in realistic scenarios are computationally difficult, and no efficient algorithms are known that guarantee an exact (or optimal) solution on every input instance. Nevertheless, practical necessity dictates that acceptable solutions be found in a reasonable time. Two important means for surmounting the intractability barrier are {em randomized computation}, where the answer is optimal with high probability but not with certainty, and {em approximate computation}, where the answer is guaranteed to be within, say, small percentage of optimality. Often, these two notions go hand-in-hand.

Randomization may be incorporated explicitly in an algorithm, as in the well known algorithms for testing whether a low degree multivariate polynomial is identically 0, or in randomized rounding techniques for converting a fractional solution to a linear program into an integral solution. In some cases, probabilistic arguments are included only in the analysis of the algorithm, whereas the algorithm itself may be deterministic (as is the case with deterministic algorithms that are the result of derandomization of randomized algorithms). Yet in other cases, randomization comes in the choice of input to the algorithm (as in average case analysis).

Approximation comes in several flavors as well. For example, in combinatorial optimization problems, the goal of an approximation algorithm is to find a feasible solution whose value is close to optimal. In other cases (such as determining the cardinality of combinatorially or computationally defined sets, volume, expectation of random variables on configurations of complex systems), the goal may be only to estimate some value, rather than exhibit any particular solution. The use of randomness often simplifies the design of approximation algorithms, and is very commonly used for estimation problems.

It is also interesting that randomness plays a major role in proving negative results, for example, in the design of {em probabilistically checkable proofs} (PCPs) that are the basis for many inapproximability results. The workshop will be concerned with the newest developments on the foundational aspects of randomized and approximate computation. The focus of the workshop will be on the following topics and the various interactions between them.

The goal of the workshop is to provide a forum for researchers to meet and discuss the problems connected to the design and analysis of randomized and approximation algorithms and their various applications, shedding some light on the themes discussed above.