{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T17:04:43Z","timestamp":1777827883803,"version":"3.51.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,1,5]],"date-time":"2008-01-05T00:00:00Z","timestamp":1199491200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s10878-007-9126-9","type":"journal-article","created":{"date-parts":[[2008,1,4]],"date-time":"2008-01-04T15:28:02Z","timestamp":1199460482000},"page":"198-228","source":"Crossref","is-referenced-by-count":11,"title":["Priority algorithms for the subset-sum problem"],"prefix":"10.1007","volume":"16","author":[{"given":"Yuli","family":"Ye","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Allan","family":"Borodin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,5]]},"reference":[{"key":"9126_CR1","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s00453-004-1113-2","volume":"40","author":"S Angelopoulos","year":"2004","unstructured":"Angelopoulos S, Borodin A (2004) On the power of priority algorithms for facility location and set cover. Algorithmica 40:271\u2013291","journal-title":"Algorithmica"},{"key":"9126_CR2","volume-title":"Social choice and individual values","author":"K Arrow","year":"1951","unstructured":"Arrow K (1951) Social choice and individual values. Wiley, New York"},{"key":"9126_CR3","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J Aspnes","year":"1997","unstructured":"Aspnes J, Azar Y, Fiat A, Plotkin S, Waarts O (1997) On-line routing of virtual circuits with applications to load balancing and machine scheduling. J\u00a0ACM 44:486\u2013504","journal-title":"J\u00a0ACM"},{"key":"9126_CR4","first-page":"245","volume":"2","author":"P Baptiste","year":"1999","unstructured":"Baptiste P (1999) Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. J\u00a0Sched 2:245\u2013252","journal-title":"J\u00a0Sched"},{"key":"9126_CR5","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy A, Guha S, Naor J, Schieber B (2001) Approximating throughput in real-time scheduling. SIAM J Comput 31:331\u2013352","journal-title":"SIAM J Comput"},{"key":"9126_CR6","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/s00453-003-1036-3","volume":"37","author":"A Borodin","year":"2003","unstructured":"Borodin A, Nielsen M, Rackoff C (2003) (Incremental) priority algorithms. Algorithmica 37:295\u2013326","journal-title":"Algorithmica"},{"key":"9126_CR7","first-page":"126","volume-title":"Lecture notes in computer science, vol\u00a03351","author":"A Borodin","year":"2005","unstructured":"Borodin A, Boyar J, Larsen K (2005) Priority algorithms for graph optimization problems. In: Lecture notes in computer science, vol\u00a03351. Springer, Berlin, pp\u00a0126\u2013139"},{"key":"9126_CR8","first-page":"71","volume":"9","author":"M Chrobak","year":"2006","unstructured":"Chrobak M, Durr C, Jawor W, Kowalik L, Kurowski M (2006) A\u00a0note on scheduling equal-length jobs to maximize throughput. J\u00a0Sched 9:71\u201373","journal-title":"J\u00a0Sched"},{"key":"9126_CR9","doi-asserted-by":"crossref","unstructured":"Chuzhoy J, Ostrovsky R, Rabani Y (2001) Approximation algorithms for the job interval scheduling problem and related scheduling problems. In: Proceedings of 42nd annual IEEE symposium of foundations of computer science, pp\u00a0348\u2013356","DOI":"10.1109\/SFCS.2001.959909"},{"key":"9126_CR10","unstructured":"Davis S, Impagliazzo R (2004) Models of greedy algorithms for graph problems. In: Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms, pp\u00a0381\u2013390"},{"key":"9126_CR11","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0196-6774(02)00291-2","volume":"46","author":"T Erlebach","year":"2003","unstructured":"Erlebach T, Spieksma F (2003) Interval selection: applications, algorithms, and lower bounds. J\u00a0Algorithms 46:27\u201353","journal-title":"J\u00a0Algorithms"},{"key":"9126_CR12","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R Fleischer","year":"2000","unstructured":"Fleischer R, Wahl M (2000) On-line scheduling revisited. J Sched 3:343\u2013353","journal-title":"J Sched"},{"key":"9126_CR13","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York"},{"key":"9126_CR14","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R Graham","year":"1966","unstructured":"Graham R (1966) Bounds for certain multiprocessor anomalies. Bell Syst Tech J 45:1563\u20131581","journal-title":"Bell Syst Tech J"},{"key":"9126_CR15","unstructured":"Horn S (2004) One-pass algorithms with revocable acceptances for job interval selection. Master\u2019s thesis, University of Toronto"},{"key":"9126_CR16","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O Ibarra","year":"1975","unstructured":"Ibarra O, Kim C (1975) Fast approximation algorithms for the knapsack and sum of subset problem. J\u00a0ACM 22:463\u2013468","journal-title":"J\u00a0ACM"},{"key":"9126_CR17","first-page":"293","volume-title":"Lecture notes in computer science, vol\u00a02380","author":"K Iwama","year":"2002","unstructured":"Iwama K, Taketomi S (2002) Removable online knapsack problems. In: Lecture notes in computer science, vol\u00a02380. Springer, Berlin, pp 293\u2013305"},{"key":"9126_CR18","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0022-0000(03)00006-0","volume":"66","author":"H Kellerer","year":"2003","unstructured":"Kellerer H, Mansini R, Pferschy U, Speranza M (2003) An efficient fully polynomial approximation scheme for the subset-sum problem. J\u00a0Comput Syst Sci 66:349\u2013370","journal-title":"J\u00a0Comput Syst Sci"},{"key":"9126_CR19","volume-title":"Knapsack problems: algorithms and computer implementations","author":"S Martello","year":"1990","unstructured":"Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York"},{"key":"9126_CR20","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"J Moore","year":"1968","unstructured":"Moore J (1968) An n-job, one machine sequencing algorithm for minimizing the number of late jobs. Manag Sci 15:102\u2013109","journal-title":"Manag Sci"},{"key":"9126_CR21","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0020-0190(02)00264-8","volume":"84","author":"O Regev","year":"2002","unstructured":"Regev O (2002) Priority algorithms for makespan minimization in the subset model. Inf Process Lett 84:153\u2013157","journal-title":"Inf Process Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9126-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9126-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9126-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:12Z","timestamp":1559276292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9126-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,5]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9126"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9126-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,5]]}}}