Tel-Aviv University - Computer Science Colloquium
Sunday, May 16, 14:15-15:15
at 14:00 Variable elimination algorithms (e.g., resolution, dynamic programming) are time and space exponential in the size of the relationships they record. Consequently, such methods are not practical in reasoning and combinatorial optimization problems, unless the knowledge-based is very sparse. In this talk I will present a scheme of parameterized approximation algorithms, (called mini-bucket) that bounds the size of the recorded relations. The bounding parameter thus allows adjustable tradeoff between accuracy and efficiency that can be tuned to match users' requirements and resources.
The mini-bucket scheme generates both an upper and a lower bound on the optimal solution and can, therefore, be embedded in anytime schemes that guarantee any desired accuracy. Alternatively, it can be used for generating admissible heuristic functions (upper bounding functions) with varying strength, to improve the efficiency of exact algorithms. Experimental evaluation in the domains of medical diagnosis and probabilistic decoding shows that the solution of large, real-life combinatorial optimization problems is turning feasible.
(Joint work with Irina Rish and Kalev Kask)
Bio:
Rina Dechter is a Professor of Computer Science at the University of
California, Irvine. She received her Ph.D. in computer science at UCLA
in 1985. Before coming to UC-Irvine she worked at Hughes aircraft and
subsequently spent two years on the faculty of the computer science
department at the Technion, Haifa, Israel. Her research centers on
computational aspects of automated reasoning and knowledge
representation, including constraint processing, probabilistic
reasoning, and distributed computation.
Professor Dechter is a Fellow of the American Association of
Artificial Intelligence. She has published over 50 research articles,
and is now serving on the editorial boards of: Artificial
Intelligence, Journal of Artificial Intelligence Research, Constraints
Journal, and the Encyclopedia of AI.
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html