{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:54Z","timestamp":1740122454165,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T00:00:00Z","timestamp":1581033600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T00:00:00Z","timestamp":1581033600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-15-1-0100","FA9550-19-1-0106"],"award-info":[{"award-number":["FA9550-15-1-0100","FA9550-19-1-0106"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s10898-020-00880-5","type":"journal-article","created":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T14:02:44Z","timestamp":1581084164000},"page":"575-602","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Primal-dual analysis for online interval scheduling problems"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0654-0062","authenticated-orcid":false,"given":"Ge","family":"Yu","sequence":"first","affiliation":[]},{"given":"Sheldon H.","family":"Jacobson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,7]]},"reference":[{"issue":"4","key":"880_CR1","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1287\/opre.2014.1289","volume":"62","author":"S Agrawal","year":"2014","unstructured":"Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4), 876\u2013890 (2014)","journal-title":"Oper. Res."},{"issue":"3","key":"880_CR2","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1016\/j.ejor.2009.01.042","volume":"200","author":"AN Avramidis","year":"2010","unstructured":"Avramidis, A.N., Chan, W., Gendreau, M., L\u2019ecuyer, P., Pisacane, O.: Optimizing daily agent scheduling in a multiskill call center. Eur. J. Oper. Res. 200(3), 822\u2013832 (2010)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"880_CR3","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/2339123.2339126","volume":"59","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Buchbinder, N., Naor, J.S.: A primal-dual randomized algorithm for weighted paging. J. ACM (JACM) 59(4), 19 (2012)","journal-title":"J. ACM (JACM)"},{"issue":"1\u20133","key":"880_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0166-218X(99)00238-3","volume":"103","author":"P Baptiste","year":"2000","unstructured":"Baptiste, P.: Scheduling equal-length jobs on identical parallel machines. Discret. Appl. Math. 103(1\u20133), 21\u201332 (2000)","journal-title":"Discret. Appl. Math."},{"key":"880_CR5","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Jain, K., Singh, M.: Secretary problems via linear programming. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 163\u2013176. Springer (2010)","DOI":"10.1007\/978-3-642-13036-6_13"},{"issue":"2\u20133","key":"880_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.S., et al.: The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comput. Sci. 3(2\u20133), 93\u2013263 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"880_CR7","unstructured":"Chen, Y., Wang, M.: Stochastic primal-dual methods and sample complexity of reinforcement learning. arXiv:1612.02516 (2016)"},{"issue":"1","key":"880_CR8","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10951-006-5595-4","volume":"9","author":"M Chrobak","year":"2006","unstructured":"Chrobak, M., D\u00fcrr, C., Jawor, W., Kowalik, \u0141., Kurowski, M.: A note on scheduling equal-length jobs to maximize throughput. J. Sched. 9(1), 71\u201373 (2006)","journal-title":"J. Sched."},{"key":"880_CR9","doi-asserted-by":"crossref","unstructured":"Deng, D., Shahabi, C., Zhu, L.: Task matching and scheduling for multiple workers in spatial crowdsourcing. In: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, p.\u00a021. ACM (2015)","DOI":"10.1145\/2820783.2820831"},{"key":"880_CR10","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of ranking for online bipartite matching. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 101\u2013107. SIAM (2013)","DOI":"10.1137\/1.9781611973105.7"},{"key":"880_CR11","doi-asserted-by":"crossref","unstructured":"Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: beating 1-1\/e. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201909, pp. 117\u2013126. IEEE (2009)","DOI":"10.1109\/FOCS.2009.72"},{"issue":"3","key":"880_CR12","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/s10878-007-9131-z","volume":"16","author":"SP Fung","year":"2008","unstructured":"Fung, S.P., Poon, C.K., Zheng, F.: Online interval scheduling: randomized and multiprocessor cases. J. Comb. Optim. 16(3), 248\u2013262 (2008)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"880_CR13","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/s00224-013-9528-2","volume":"55","author":"SP Fung","year":"2014","unstructured":"Fung, S.P., Poon, C.K., Zheng, F.: Improved randomized online scheduling of intervals and jobs. Theory Comput. Syst. 55(1), 202\u2013228 (2014)","journal-title":"Theory Comput. Syst."},{"key":"880_CR14","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 352\u2013358. ACM (1990)","DOI":"10.1145\/100216.100262"},{"issue":"2","key":"880_CR15","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.ejor.2006.01.049","volume":"178","author":"MY Kovalyov","year":"2007","unstructured":"Kovalyov, M.Y., Ng, C., Cheng, T.E.: Fixed interval scheduling: models, applications, computational complexity and algorithms. Eur. J. Oper. Res. 178(2), 331\u2013342 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"880_CR16","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPS. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 597\u2013606. ACM (2011)","DOI":"10.1145\/1993636.1993716"},{"issue":"4","key":"880_CR17","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1287\/moor.1120.0551","volume":"37","author":"VH Manshadi","year":"2012","unstructured":"Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: online actions based on offline statistics. Math. Oper. Res. 37(4), 559\u2013573 (2012)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"880_CR18","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0167-6377(98)00019-4","volume":"22","author":"SS Seiden","year":"1998","unstructured":"Seiden, S.S.: Randomized online interval scheduling. Oper. Res. Lett. 22(4), 171\u2013177 (1998)","journal-title":"Oper. Res. Lett."},{"issue":"5","key":"880_CR19","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y","volume":"2","author":"FC Spieksma","year":"1999","unstructured":"Spieksma, F.C.: On the approximability of an interval scheduling problem. J. Sched. 2(5), 215\u2013227 (1999)","journal-title":"J. Sched."},{"key":"880_CR20","doi-asserted-by":"crossref","unstructured":"Wang, M., Chen, Y.: An online primal-dual method for discounted Markov decision processes. In: IEEE 55th Conference on Decision and Control (CDC), pp. 4516\u20134521. IEEE (2016)","DOI":"10.1109\/CDC.2016.7798956"},{"issue":"1","key":"880_CR21","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0304-3975(94)90150-3","volume":"130","author":"GJ Woeginger","year":"1994","unstructured":"Woeginger, G.J.: On-line scheduling of jobs with fixed start and end times. Theor. Comput. Sci. 130(1), 5\u201316 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"880_CR22","unstructured":"Yu, G., Jacobson, S.H.: Approximation Algorithms for Stochastic Online Matching with Reusable Resources. Technical Report, University of Illinois at Urbana Champaign (2018)"},{"issue":"2","key":"880_CR23","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s11590-017-1191-0","volume":"12","author":"G Yu","year":"2018","unstructured":"Yu, G., Jacobson, S.H.: Online C-benevolent job scheduling on multiple machines. Optim. Lett. 12(2), 251\u2013263 (2018)","journal-title":"Optim. Lett."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00880-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-020-00880-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00880-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T22:04:47Z","timestamp":1612821887000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-020-00880-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,7]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["880"],"URL":"https:\/\/doi.org\/10.1007\/s10898-020-00880-5","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2020,2,7]]},"assertion":[{"value":"8 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}