Design is as Easy as Optimization
Speaker: Aranyak Mehta , IBM Almaden Research Center
Date: October 16 2006
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Ronitt Rubinfeld, MIT CSAIL
Contact: Joanne Hanley, 617.253.6054, joanne@csail.mit.edu
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/aranyak-abs.html
Over the last four decades, theoreticians have identified and studied several fundamental genres of algorithmic problems. These include decision, search, optimization, counting, enumeration, random generation, and approximate counting problems.
We identify a new genre of algorithmic problems -- design problems. Every optimization problem leads to a natural design problem. For instance, the minimum spanning tree problem leads to: given an undirected graph $G = (V,E)$ and a bound $B$, find a way of distributing weight $B$ on the edges of $G$ so that the weight of the minimum spanning tree is maximized.
Practitioners have always been faced with design problems and such problems have been studied individually by theoreticians as well. However, this genre has not been subjected to a systematic complexity-theoretic study before. Using techniques of Freund-Schapire and its follow-up works in learning theory, we show that for a large class of problems, the design version is as easy as the optimization version in the following sense: given an oracle (exact or approximation) for the optimization version, the design version can be solved (exactly or with the same approximation factor) in polynomial time.
Joint work with Deeparnab Chakrabarty and Vijay V. Vazirani.
See other events that are part of Algorithms and Complexity Series 2006/2007
See other events happening in October 2006
