DESIGN IS AS EASY AS OPTIMIZATION

作者：Chakrabarty Deeparnab^*; Mehta Aranyak; Vazirani Vijay V

来源：SIAM Journal on Discrete Mathematics, 2010, 24(1): 270-286.

DOI：10.1137/080735898

• design problems
• fractional packing
• multiplicative updates

We consider the class of max-min and min-max optimization problems subject to a global budget constraint. We undertake a systematic algorithmic and complexity-theoretic study of such problems, which we call design problems. Every optimization problem leads to a natural design problem. Our main result uses techniques of Freund and Schapire [Games Econom. Behav., 29 (1999), pp. 79-103] from learning theory, and its generalizations, to show that for a large class of optimization problems, the design version is as easy as the optimization version. We also observe the relationship between max-min design problems and fractional packing problems. In particular, we obtain in a systematic fashion results about the fractional packing number of Steiner trees.

• 出版日期2010