{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:14Z","timestamp":1740109274476,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,5,10]],"date-time":"2016-05-10T00:00:00Z","timestamp":1462838400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["621\/12"],"award-info":[{"award-number":["621\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s00453-016-0162-7","type":"journal-article","created":{"date-parts":[[2016,5,10]],"date-time":"2016-05-10T10:01:01Z","timestamp":1462874461000},"page":"255-273","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimization with Uniform Size Queries"],"prefix":"10.1007","volume":"78","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[]},{"given":"Moshe","family":"Tennenholtz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,10]]},"reference":[{"key":"162_CR1","doi-asserted-by":"crossref","unstructured":"Bailly, G., Oulasvirta, A., Brumby, D.P., Howes, A.: Model of visual search and selection time in linear menus. In: CHI\u201914, pp. 3865\u20133874 (2014)","DOI":"10.1145\/2556288.2557093"},{"issue":"1","key":"162_CR2","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/s10878-010-9318-6","volume":"24","author":"A Bar-Noy","year":"2012","unstructured":"Bar-Noy, A., Lampis, M.: Online maximum directed cut. J. Comb. Optim. 24(1), 52\u201364 (2012)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"162_CR3","doi-asserted-by":"crossref","first-page":"1372","DOI":"10.1137\/050641181","volume":"39","author":"L Blumrosen","year":"2009","unstructured":"Blumrosen, L., Nisan, N.: On the computational power of demand queries. SIAM J. Comput. 39(4), 1372\u20131391 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"162_CR4","doi-asserted-by":"crossref","first-page":"622","DOI":"10.1006\/jcss.1998.1612","volume":"58","author":"J Chen","year":"1999","unstructured":"Chen, J., Friesen, D.K., Zheng, H.: Tight bound on johnson\u2019s algorithm for maximum satisfiability. J. Comput. Syst. Sci. 58(3), 622\u2013640 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"162_CR5","doi-asserted-by":"crossref","unstructured":"David, R., Dinur, I., Goldenberg, E., Kindler, G., Shinkar, I.: Direct sum testing. In: ITCS-2015, pp. 327\u2013336 (2015)","DOI":"10.1145\/2688073.2688078"},{"issue":"3","key":"162_CR6","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P Erdos","year":"1973","unstructured":"Erdos, P., Selfridge, J.: Online maximum directed cut. J. Comb. Theory Ser. A 14(3), 298\u2013301 (1973)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"4","key":"162_CR7","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: Threshold of $$\\ln n$$ ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"162_CR8","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondrak, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"162_CR9","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"162_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Grotschel","year":"1981","unstructured":"Grotschel, M., Lovasz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"162_CR11","first-page":"169","volume":"3","author":"I Guyon","year":"2003","unstructured":"Guyon, I., Elisseeff, A.: An introduction to variable and feature selection. J. Mach. Learn. Res. 3, 169\u2013197 (2003)","journal-title":"J. Mach. Learn. Res."},{"key":"162_CR12","first-page":"169","volume":"94","author":"J-J Laffont","year":"1986","unstructured":"Laffont, J.-J., Tirole, J.: Using cost observation to regulate firms. J. Polit. Econ. 94, 169\u2013197 (1986)","journal-title":"J. Polit. Econ."},{"issue":"2","key":"162_CR13","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","volume":"55","author":"B Lehmann","year":"2006","unstructured":"Lehmann, B., Lehmann, L.J., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270\u2013296 (2006)","journal-title":"Games Econ. Behav."},{"key":"162_CR14","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G Nemhauser","year":"1978","unstructured":"Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of approximations for maximizing submodular set functions\u2014I. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"162_CR15","doi-asserted-by":"crossref","unstructured":"Radlinski, F., Kleinberg, R., Joachims, T.: Learning diverse rankings with multi-armed bandits. In: ICML-2008, pp. 784\u2013791 (2008)","DOI":"10.1145\/1390156.1390255"},{"issue":"2","key":"162_CR16","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms. J. Comput. Syst. Sci. 37(2), 130\u2013143 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"162_CR17","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1257\/000282803322157160","volume":"93","author":"WP Rogerson","year":"2003","unstructured":"Rogerson, W.P.: Simple menus of contracts in cost-based procurement and regulation. Am. Econ. Rev. 93(3), 919\u2013926 (2003)","journal-title":"Am. Econ. Rev."},{"key":"162_CR18","unstructured":"Streeter, M.J., Golovin, D., Krause, A.: Online learning of assignments. In: NIPS-2009, pp. 1794\u20131802 (2009)"},{"key":"162_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0162-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0162-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0162-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0162-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:24Z","timestamp":1559072844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0162-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,10]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["162"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0162-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,5,10]]}}}