{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:42Z","timestamp":1725662922710},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540108566"},{"type":"electronic","value":"9783540387695"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10856-4_74","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:34:05Z","timestamp":1330191245000},"page":"61-77","source":"Crossref","is-referenced-by-count":2,"title":["A survey on oracle techniques"],"prefix":"10.1007","author":[{"given":"B.","family":"Korte","sequence":"first","affiliation":[]},{"given":"R.","family":"Schrader","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker, Th., Gill, J., and Solovay, R.; Relativizations of the P = ? NP question. SIAM Journal on Computing 4 (1975) 431\u2013442.","journal-title":"SIAM Journal on Computing"},{"key":"5_CR2","doi-asserted-by":"crossref","first-page":"1402","DOI":"10.1287\/opre.28.6.1402","volume":"28","author":"V. Chv\u00e1tal","year":"1980","unstructured":"Chv\u00e1tal, V.; Hard knapsack problems. Operations Research 28 (1980) 1402\u20131411.","journal-title":"Operations Research"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S.A.; The Complexity of theorem \u2014 proving procedures. Proc. of the 3rd Annual ACM Symposium on the Theory of Computing, Shaker Heights, Ohio (1971) 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"5_CR4","unstructured":"Dobkin, D. and Lipton, R.J.; A lower bound of 1\/2 n2 on linear search programs for the knapsack problem. In: A. Masurkiewicz (ed.), Mathematical Foundations of Computer Science (1976), Lect. Notes in Corp. Science 45."},{"key":"5_CR5","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., and Schrijver, A.; The ellipsoid method and its consequences in combinatorial optimization. To appear in: Combinatorica."},{"key":"5_CR6","unstructured":"Hausmann, D., Kannan, R. and Korte, B.; Exponential lower bounds on a class of knapsack algorithms. To appear in: Mathematics of Operations Research."},{"key":"5_CR7","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-3-642-95322-4_17","volume":"157","author":"D. Hausmann","year":"1978","unstructured":"Hausmann, D. and Korte, B.; Oracle algorithms for fixed \u2014 point problems \u2014 an axiomatic approach. In: Henn et al. (eds.), Optimization and Operations Research, Lecture Notes in Economics and Mathematical Systems 157 (1978) 161\u2013172.","journal-title":"Optimization and Operations Research"},{"key":"5_CR8","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0012-365X(78)90097-3","volume":"24","author":"D. Hausmann","year":"1978","unstructured":"Hausmann, D. and Korte, B.; Lower bounds on the worst \u2014 case complexity of some oracle algorithms. Discrete Mathematics 24 (1978) 261\u2013276.","journal-title":"Discrete Mathematics"},{"key":"5_CR9","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/BFb0120924","volume":"14","author":"D. Hausmann","year":"1981","unstructured":"Hausmann, D. and Korte, B.; Algorithmic versus axiomatic definitions of matroids. Mathematical Programming Study 14 (1981) 98\u2013111.","journal-title":"Mathematical Programming Study"},{"key":"5_CR10","unstructured":"Hausmann, D. and Korte, B.; The relative strength of oracles for independence systems. In: J. Frehse, D. Pallaschke, U. Trottenberg (eds.), Special topics of applied mathematics, North Holland, 1980, 195\u2013211."},{"key":"5_CR11","unstructured":"Jensen, P. M. and Korte, B.; Complexity of matroid property algorithms. To appear in: SIAM Journal on Computing."},{"key":"5_CR12","first-page":"128","volume":"12","author":"D. B. Judin","year":"1976","unstructured":"Judin, D. B. and Nemirovskii, A. S.; Evaluation of the informational complexity of mathematical programming problems. Ekonomikai Matematicheskie Metody 12 (1976) 128\u2013142. Matekon 13,2 (1977) 3\u201325.","journal-title":"Ekonomikai Matematicheskie Metody"},{"key":"5_CR13","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0167-5060(08)70322-4","volume":"2","author":"B. Korte","year":"1978","unstructured":"Korte, B. and Hausmann, D.; An analysis of the greedy heuristic for independence systems. In: B. Alspach, P. Hell, and D. J. Miller (eds.), Annals of Discrete Mathematcis 2 (1978) 65\u201374.","journal-title":"Annals of Discrete Mathematcis"},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-0348-5997-4_13","volume":"2","author":"B. Korte","year":"1979","unstructured":"Korte, B. and Monma, C. L.; Some remarks on a classification of oracle-type-algorithms. In: Collatz et al. (eds.), Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen, Band 2 (1979) 195\u2013215.","journal-title":"Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen"},{"key":"5_CR15","unstructured":"Korte, B. and Schrader, R.; On the existence of fast approximation schemes. To appear in: O. L. Mangasarian, R. R. Meyer, S. M. Robinson (eds.), Nonlinear Programming 4."},{"key":"5_CR16","unstructured":"Labetoulle, I., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G.; Preemptive scheduling of uniform machines subject to release dates. Mathematisch Centrum, Preprint BW 99\/79 (1979)."},{"key":"5_CR17","unstructured":"Milner, E. C. and Welsh, D. J. A.; On the computational complexity of graph theoretical properties. In: Nash-Williams (ed.), Proceedings of the 5th British combinatorial conference, Aberdeen 1975."},{"key":"5_CR18","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"G. L. Nemhauser","year":"1978","unstructured":"Nemhauser, G. L. and Wolsey, L. A.; Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research 3 (1978) 177\u2013188.","journal-title":"Mathematics of Operations Research"},{"key":"5_CR19","first-page":"4","volume":"IV","author":"V. P. Orevkov","year":"1963","unstructured":"Orevkov, V. P.; A constructive mapping of a spuare onto itself displacing every constructive point. Soviet Mathematics IV (1963) 4\u20136.","journal-title":"Soviet Mathematics"},{"key":"5_CR20","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1017\/S0305004100056498","volume":"87","author":"G. C. Robinson","year":"1980","unstructured":"Robinson, G. C. and Welsh, D. J. A.; The computational complexity of matroid properties. Mathematical Proceedings of the Cambridge Philosophical Society 87 (1980) 29\u201345.","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"5_CR21","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1287\/opre.27.5.925","volume":"27","author":"S. Sahni","year":"1979","unstructured":"Sahni, S.; Preemptive scheduling with Due dates. Operations Research 27 (1979) 925\u2013934.","journal-title":"Operations Research"},{"key":"5_CR22","series-title":"Working Paper","volume-title":"Recognizing graphic matroids","author":"P. D. Seymour","year":"1979","unstructured":"Seymour, P. D.; Recognizing graphic matroids. Working Paper, Merton College, Oxford and University of Waterloo, Canada (1979)."},{"key":"5_CR23","volume-title":"Matroid theory","author":"D. J. A. Welsh","year":"1976","unstructured":"Welsh, D. J. A.; Matroid theory. Academic Press, London-New York-San Francisco (1976)."},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Yao, A. C., Avis, D. M., and Rivest, R. L.; O(n2 log n) lower bound to the shortest paths problem. In: Proceedings of the Ninth Annual ACM Symposium on the Theory of Computing, 11\u201317 (1977).","DOI":"10.1145\/800105.803391"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1981"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10856-4_74.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:40:02Z","timestamp":1619556002000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10856-4_74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108566","9783540387695"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-10856-4_74","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}