{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:33Z","timestamp":1725489153840},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73545-8_49","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"504-514","source":"Crossref","is-referenced-by-count":0,"title":["Priority Algorithms for the Subset-Sum Problem"],"prefix":"10.1007","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","reference":[{"key":"49_CR1","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s00453-004-1113-2","volume":"40","author":"S. Angelopoulos","year":"2004","unstructured":"Angelopoulos, S., Borodin, A.: On the power of priority algorithms for facility location and set cover. Algorithmica\u00a040, 271\u2013291 (2004)","journal-title":"Algorithmica"},{"key":"49_CR2","volume-title":"Social Choice and Individual Values","author":"K. Arrow","year":"1951","unstructured":"Arrow, K.: Social Choice and Individual Values. Wiley, Chichester (1951)"},{"key":"49_CR3","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<245::AID-JOS28>3.0.CO;2-5","volume":"2","author":"P. Baptiste","year":"1999","unstructured":"Baptiste, P.: Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. Journal of Scheduling\u00a02, 245\u2013252 (1999)","journal-title":"Journal of Scheduling"},{"key":"49_CR4","doi-asserted-by":"publisher","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.: Approximating throughput in real-time scheduling. SIAM Journal of Computing\u00a031, 331\u2013352 (2001)","journal-title":"SIAM Journal of Computing"},{"key":"49_CR5","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00453-003-1036-3","volume":"37","author":"A. Borodin","year":"2003","unstructured":"Borodin, A., Nielsen, M., Rackoff, C.: (Incremental) priority algorithms. Algorithmica\u00a037, 295\u2013326 (2003)","journal-title":"Algorithmica"},{"key":"49_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/978-3-540-31833-0_12","volume-title":"Approximation and Online Algorithms","author":"A. Borodin","year":"2005","unstructured":"Borodin, A., Boyar, J., Larsen, K.: Priority algorithms for graph optimization problems. In: Persiano, G., Solis-Oba, R. (eds.) WAOA 2004. LNCS, vol.\u00a03351, pp. 126\u2013139. Springer, Heidelberg (2005)"},{"key":"49_CR7","unstructured":"Chrobak, M., Durr, C., Jawor, W., Kowalik, L., Kurowski, M.: On scheduling equal length jobs to maximize throughput. To appear in Journal of Scheduling."},{"key":"49_CR8","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1109\/SFCS.2001.959909","volume-title":"Proceedings of 42nd Annual IEEE Symposium of Foundations of Computer Science","author":"J. Chuzhoy","year":"2001","unstructured":"Chuzhoy, J., Ostrovsky, R., Rabani, Y.: 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. 348\u2013356. IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"49_CR9","first-page":"381","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Davis","year":"2004","unstructured":"Davis, S., Impagliazzo, R.: Models of greedy algorithms for graph problems. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 381\u2013390. ACM Press, New York (2004)"},{"key":"49_CR10","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0196-6774(02)00291-2","volume":"46","author":"T. Erlebach","year":"2003","unstructured":"Erlebach, T., Spieksma, F.: Interval selection: Applications, algorithms, and lower bounds. Journal of Algorithms\u00a046, 27\u201353 (2003)","journal-title":"Journal of Algorithms"},{"key":"49_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"49_CR12","unstructured":"Horn, S.: One-pass algorithms with revocable acceptances for job interval selection. Master\u2019s thesis, University of Toronto (2004)"},{"key":"49_CR13","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O. Ibarra","year":"1975","unstructured":"Ibarra, O., Kim, C.: Fast approximation algorithms for the knapsack and sum of subset problem. Journal of the ACM\u00a022, 463\u2013468 (1975)","journal-title":"Journal of the ACM"},{"key":"49_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-45465-9_26","volume-title":"Automata, Languages and Programming","author":"K. Iwama","year":"2002","unstructured":"Iwama, K., Taketomi, S.: Removable online knapsack problems. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 293\u2013305. Springer, Heidelberg (2002)"},{"key":"49_CR15","doi-asserted-by":"publisher","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.: An efficient fully polynomial approximation scheme for the subset-sum problem. Journal of Computer and System Science\u00a066, 349\u2013370 (2003)","journal-title":"Journal of Computer and System Science"},{"key":"49_CR16","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S. Martello","year":"1990","unstructured":"Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. John Wiley and Sons, Chichester (1990)"},{"key":"49_CR17","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"J. Moore","year":"1968","unstructured":"Moore, J.: An n-job, one machine sequencing algorithm algorithm for minimizing the number of late jobs. Management Science\u00a015, 102\u2013109 (1968)","journal-title":"Management Science"},{"key":"49_CR18","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0020-0190(02)00264-8","volume":"84","author":"O. Regev","year":"2002","unstructured":"Regev, O.: Priority algorithms for makespan minimization in the subset model. Information Processing Letters\u00a084, 153\u2013157 (2002)","journal-title":"Information Processing Letters"},{"key":"49_CR19","unstructured":"Ye, Y., Borodin, A.: Priority algorithms for the subset-sum problem. Technical Report, University of Toronto (2007), http:\/\/www.cs.toronto.edu\/~bor"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:18:01Z","timestamp":1619518681000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735441","9783540735458"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}