{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T22:24:01Z","timestamp":1757629441191,"version":"3.44.0"},"reference-count":25,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[1990,4,1]],"date-time":"1990-04-01T00:00:00Z","timestamp":638928000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1990,4,1]],"date-time":"1990-04-01T00:00:00Z","timestamp":638928000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Parallel and Distributed Computing"],"published-print":{"date-parts":[[1990,4]]},"DOI":"10.1016\/0743-7315(90)90139-g","type":"journal-article","created":{"date-parts":[[2004,5,11]],"date-time":"2004-05-11T07:49:26Z","timestamp":1084261766000},"page":"400-406","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":24,"title":["Adaptive parallel algorithms for integral knapsack problems"],"prefix":"10.1016","volume":"8","author":[{"given":"Shang-Hua","family":"Teng","sequence":"first","affiliation":[]}],"member":"78","reference":[{"doi-asserted-by":"crossref","unstructured":"Aggarwal, A., and Park, J. Note on searching in multidimensional monotone arrays. Proc. FOCS 88, pp. 497\u2013512.","key":"10.1016\/0743-7315(90)90139-G_BIB1","DOI":"10.1109\/SFCS.1988.21966"},{"year":"1974","author":"Aho","series-title":"The Design and Analysis of Computer Algorithms","key":"10.1016\/0743-7315(90)90139-G_BIB2"},{"doi-asserted-by":"crossref","unstructured":"Atallah, M., Kosaraju, R., Larmore, L., Miller, G., and Teng, S-H. Constructing trees in parallel. Proc. ACM SPAA 89, pp. 421\u2013431.","key":"10.1016\/0743-7315(90)90139-G_BIB3","DOI":"10.1145\/72935.72980"},{"year":"1983","author":"Cook","series-title":"The classification of problems which have fast parallel algorithms","key":"10.1016\/0743-7315(90)90139-G_BIB4"},{"key":"10.1016\/0743-7315(90)90139-G_BIB5","series-title":"Concurrent Computations: Algorithms, Architecture, and Technology","first-page":"139","article-title":"Optimal tree contraction in EREW model","author":"Gazit","year":"1987"},{"key":"10.1016\/0743-7315(90)90139-G_BIB6","article-title":"Approximate algorithms for the knapsack problem on parallel computers","author":"Gopalakrishnan","year":"1987","journal-title":"IBM Res. Rep. RC-12549"},{"key":"10.1016\/0743-7315(90)90139-G_BIB7","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","article-title":"Computing partitions with applications to the knapsack problem","author":"Horowitz","year":"1974","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0743-7315(90)90139-G_BIB8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","article-title":"Exact and approximate algorithm for scheduling nonidentical processors","author":"Horowitz","year":"1976","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0743-7315(90)90139-G_BIB9","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"issue":"1","key":"10.1016\/0743-7315(90)90139-G_BIB10","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","article-title":"The circuit value problem is log space complete for P","volume":"7","author":"Ladner","year":"1975","journal-title":"SIGACT News"},{"key":"10.1016\/0743-7315(90)90139-G_BIB11","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","article-title":"Parallel prefix computation","author":"Ladner","year":"1980","journal-title":"J. Assoc. Comput. Mach."},{"year":"1976","author":"Lawler","series-title":"Combinatorial Optimization: Networks and Matroids","key":"10.1016\/0743-7315(90)90139-G_BIB12"},{"year":"1988","author":"Mayr","series-title":"Parallel approximation algorithms","key":"10.1016\/0743-7315(90)90139-G_BIB13"},{"doi-asserted-by":"crossref","unstructured":"Miller, G. L., and Rief, J. H. Parallel tree contraction and its application. Proc. FOCS 85, pp. 478\u2013489.","key":"10.1016\/0743-7315(90)90139-G_BIB14","DOI":"10.1109\/SFCS.1985.43"},{"key":"10.1016\/0743-7315(90)90139-G_BIB15","series-title":"Aegean Workshop on Computing VLSI Algorithms and Architectures","article-title":"Efficient parallel evaluation of straight-line code and arithmetic circuits","author":"Miller","year":"1986"},{"doi-asserted-by":"crossref","unstructured":"Miller, G. L., and Teng, S-H. Dynamic parallel complexity of computational circuits. Proc. ACM STOC 87, pp. 254\u2013263.","key":"10.1016\/0743-7315(90)90139-G_BIB16","DOI":"10.1145\/28395.28423"},{"year":"1987","author":"Miller","article-title":"Systematic methods for tree based parallel algorithm development","key":"10.1016\/0743-7315(90)90139-G_BIB17"},{"unstructured":"Ranade, A. G. How to emulate shared memory. Proc. IEEE FOCS 87.","key":"10.1016\/0743-7315(90)90139-G_BIB18"},{"doi-asserted-by":"crossref","unstructured":"Reif, J. H. An optimal parallel algorithm for integer sorting. Proc. IEEE FOCS 85, pp. 496\u2013504.","key":"10.1016\/0743-7315(90)90139-G_BIB19","DOI":"10.1109\/SFCS.1985.9"},{"year":"1983","author":"Sedgewick","series-title":"Algorithms","key":"10.1016\/0743-7315(90)90139-G_BIB20"},{"key":"10.1016\/0743-7315(90)90139-G_BIB21","first-page":"114","author":"Sahni","year":"1976","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"10.1016\/0743-7315(90)90139-G_BIB22","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/357114.357116","article-title":"Ultercomputers","volume":"2","author":"Schwartz","year":"1980","journal-title":"ACM Trans. Programming Languages Systems"},{"issue":"3","key":"10.1016\/0743-7315(90)90139-G_BIB23","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0743-7315(87)90035-9","article-title":"Parallel algorithms for message decomposition","volume":"4","author":"Teng","year":"1987","journal-title":"J. Parallel Distrib. Comput."},{"doi-asserted-by":"crossref","unstructured":"Valiant, L.G., and Brebner, G.J. Universal schemes for parallel communication. Proc. ACM STOC 81, pp. 263\u2013277.","key":"10.1016\/0743-7315(90)90139-G_BIB24","DOI":"10.1145\/800076.802479"},{"key":"10.1016\/0743-7315(90)90139-G_BIB25","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","article-title":"Fast parallel computation of polynomials using few processors","volume":"12","author":"Valiant","year":"1983","journal-title":"SIAM J. Comput."}],"container-title":["Journal of Parallel and Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:074373159090139G?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:074373159090139G?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T14:31:40Z","timestamp":1757514700000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/074373159090139G"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,4]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1990,4]]}},"alternative-id":["074373159090139G"],"URL":"https:\/\/doi.org\/10.1016\/0743-7315(90)90139-g","relation":{},"ISSN":["0743-7315"],"issn-type":[{"type":"print","value":"0743-7315"}],"subject":[],"published":{"date-parts":[[1990,4]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Adaptive parallel algorithms for integral knapsack problems","name":"articletitle","label":"Article Title"},{"value":"Journal of Parallel and Distributed Computing","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0743-7315(90)90139-G","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1990 Published by Elsevier Inc.","name":"copyright","label":"Copyright"}]}}