{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:44:52Z","timestamp":1725795892588},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_40","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"477-488","source":"Crossref","is-referenced-by-count":2,"title":["Demand Queries with Preprocessing"],"prefix":"10.1007","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[]},{"given":"Shlomo","family":"Jozeph","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"40_CR1","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01277956","volume":"5","author":"N. Alon","year":"1995","unstructured":"Alon, N., Feige, U., Wigderson, A., Zuckerman, D.: Derandomized graph products. Computational Complexity\u00a05(1), 60\u201375 (1995)","journal-title":"Computational Complexity"},{"issue":"2","key":"40_CR2","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1109\/18.52484","volume":"36","author":"J. Bruck","year":"1990","unstructured":"Bruck, J., Naor, M.: The hardness of decoding linear codes with preprocessing. IEEE Transactions on Information Theory\u00a036(2), 381\u2013385 (1990)","journal-title":"IEEE Transactions on Information Theory"},{"doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1\/2)-approximation for unconstrained submodular maximization. In: FOCS. pp. 649\u2013658 (2012)","key":"40_CR3","DOI":"10.1109\/FOCS.2012.73"},{"issue":"3","key":"40_CR4","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF02579361","volume":"5","author":"W.H. Cunningham","year":"1985","unstructured":"Cunningham, W.H.: On submodular function minimization. Combinatorica\u00a05(3), 185\u2013192 (1985)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. In: STOC, pp. 610\u2013618 (2005)","key":"40_CR5","DOI":"10.1145\/1060590.1060681"},{"doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: SODA, pp. 1064\u20131073 (2006)","key":"40_CR6","DOI":"10.1145\/1109557.1109675"},{"issue":"2","key":"40_CR7","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM\u00a043(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"key":"40_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-31594-7_29","volume-title":"Automata, Languages, and Programming","author":"U. Feige","year":"2012","unstructured":"Feige, U., Jozeph, S.: Universal factor graphs. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 339\u2013350. Springer, Heidelberg (2012)"},{"issue":"1","key":"40_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.jcss.2004.01.002","volume":"69","author":"U. Feige","year":"2004","unstructured":"Feige, U., Micciancio, D.: The inapproximability of lattice and coding problems with preprocessing. J. Comput. Syst. Sci.\u00a069(1), 45\u201367 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"40_CR10","doi-asserted-by":"publisher","first-page":"247","DOI":"10.4086\/toc.2010.v006a011","volume":"6","author":"U. Feige","year":"2010","unstructured":"Feige, U., Vondr\u00e1k, J.: The submodular welfare problem with demand queries. Theory of Computing\u00a06(1), 247\u2013290 (2010)","journal-title":"Theory of Computing"},{"doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Harvey, N.J.A., Iwata, S., Mirrokni, V.S.: Approximating submodular functions everywhere. In: SODA, pp. 535\u2013544 (2009)","key":"40_CR11","DOI":"10.1137\/1.9781611973068.59"},{"issue":"1","key":"40_CR12","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate withinn n\n                  1\u2009\u2212\u2009\u03b5\n                  . Acta Mathematica\u00a0182(1), 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"issue":"1","key":"40_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-007-9105-7","volume":"52","author":"S. Khot","year":"2008","unstructured":"Khot, S., Lipton, R.J., Markakis, E., Mehta, A.: Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica\u00a052(1), 3\u201318 (2008)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Khot, S., Popat, P., Vishnoi, N.K.: \n                    \n                      \n                    \n                    $2^{\\log^{1-\\epsilon} n}$\n                   hardness for the closest vector problem with preprocessing. In: STOC, pp. 277\u2013288 (2012)","key":"40_CR14","DOI":"10.1145\/2213977.2214004"},{"issue":"2","key":"40_CR15","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","volume":"55","author":"B. Lehmann","year":"2006","unstructured":"Lehmann, B., Lehmann, D.J., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior\u00a055(2), 270\u2013296 (2006)","journal-title":"Games and Economic Behavior"},{"doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: STOC, pp. 681\u2013690 (2006)","key":"40_CR16","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:04:35Z","timestamp":1558922675000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}