Design is as Easy as Optimization

Aranyak Mehta (IBM Almaden)

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.

Paper available at: http://www-static.cc.gatech.edu/~aranyak/design-fullversion.pdf

Host: Ronitt Rubinfeld

(The Algorithms and Complexity Seminar series talks are usually held Mondays from 4-5:15pm in 32-G575.)