{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:59Z","timestamp":1787323559062,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>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\u2013103] 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.<\/jats:p>","DOI":"10.1137\/080735898","type":"journal-article","created":{"date-parts":[[2010,3,17]],"date-time":"2010-03-17T18:06:09Z","timestamp":1268849169000},"page":"270-286","source":"Crossref","is-referenced-by-count":1,"title":["Design is as Easy as Optimization"],"prefix":"10.1137","volume":"24","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aranyak","family":"Mehta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijay V.","family":"Vazirani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,3,17]]},"reference":[{"key":"R1","unstructured":"A. Agarwal and M. Charikar,\n                      On the advantage of network coding for improving network throughput\n                      , in Proceedings of the IEEE Information Theory Workshop, 2004, pp. 2410\u20132424."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"R. Ahlswede, N. Cai, S.Y. R. Li, and R. Yeung,\n                      Network information flow\n                      , IEEE Trans. Inform. Theory, IT-46, 2000, pp. 1204\u20131216.","DOI":"10.1109\/18.850663"},{"key":"R3","unstructured":"S. Arora, E. Hazan, and S. Kale,\n                      The Multiplicative Weights Update Method: A Meta Algorithm and Applications\n                      , manuscript, 2006."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503423264"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"D. Chakrabarty, A. Mehta, and V. V. Vazirani,\n                      Design is as easy as optimization\n                      , in Proceedings of ICALP, 2006, pp. 477\u2013488.","DOI":"10.1007\/11786986_42"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90029-1"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10033"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(81)90044-X"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"J. Elson, R. Karp, C. Papadimitriou, and S. Shenker,\n                      Global synchronization in sensornets\n                      , in Proceedings of LATIN, 2004, pp. 609\u2013624.","DOI":"10.1007\/978-3-540-24698-5_63"},{"key":"R10","first-page":"931","volume":"29","author":"Falikman D. I.","year":"1981","journal-title":"Mat. Zametki","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5874","issn-type":"print"},{"key":"R11","unstructured":"A. Flaxman, A. T. Kalai, and H. B. McMahan,\n                      Online convex optimization in the bandit setting: Gradient descent without a gradient\n                      , in Proceedings of SODA, 2005."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0738"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1026"},{"key":"R14","unstructured":"G. Frederickson and R. Solis-Oba,\n                      Efficient algorithms for robustness in matroid optimization\n                      , in Proceedings of SODA, 1997, pp. 659\u2013668."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.5.4.472"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584085"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/050645452"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer-Verlag, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104445071"},{"key":"R20","unstructured":"K. Jain, M. Mahdian, and M. Salavatipour,\n                      Packing Steiner trees\n                      , in Proceedings of SODA, 2003, pp. 266\u2013274."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298340"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00013-8"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0044-3"},{"key":"R24","unstructured":"Z. Li and B. Li,\n                      Efficient computation of maximum multicast rate\n                      , in Proceedings of the $22^{\\rm nd}$ Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2003, pp. 1618\u20131628."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70504-1"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991894"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.4.414"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, London, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"},{"key":"R32","unstructured":"M. Zinkevich,\n                      Online convex programming and generalized infinitesimal gradient\n                      ascent, in Proceedings of ICML, 2003, pp. 928\u2013936."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080735898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:09:23Z","timestamp":1787321363000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080735898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080735898"],"URL":"https:\/\/doi.org\/10.1137\/080735898","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}