tanya@MOJAVE.STANFORD.EDU (Tanya Walker) (05/15/87)
Computer Science Colloquium PLACE: Terman Auditorium TIME: 4:15-5:15 DATE: May 19, 1987 TITLE: An Introduction to the Probabilistic Analysis of Combinatorial Algorithms SPEAKER: Richard Karp, Computer Science Dept, UC Berkeley In fields such as operations research, artificial intelligence and computer-aided design, algorithms are often used that perform well in practice even though there is no theoretical guarantee of their good performance. The simplex algorithm for linear programming is perhaps the most notable example of this phenomenon. It is a major challenge to algorithm designers to provide a theoretical foundation for such quick-and-dirty heuristic algorithms. One approach is through probabilistic analysis, in which one defines a probability distribution over the set of instances of a problem, and the endevors to prove that some fast, simple algorithm performs well with high probability. The speaker will discuss this approach, using examples related to set partitioning, bin packing and linear programming. He will then make an assessment of the strengths and weaknesses of probabilistic analysis as a method of validating quick-and-dirty algorithms. -------