{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:15:04Z","timestamp":1761621304171,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,2,16]],"date-time":"2017-02-16T00:00:00Z","timestamp":1487203200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s10951-017-0515-3","type":"journal-article","created":{"date-parts":[[2017,2,16]],"date-time":"2017-02-16T13:50:24Z","timestamp":1487253024000},"page":"313-325","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved algorithms for resource allocation under varying capacity"],"prefix":"10.1007","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9422-7243","authenticated-orcid":false,"given":"Venkatesan T.","family":"Chakaravarthy","sequence":"first","affiliation":[]},{"given":"Anamitra R.","family":"Choudhury","sequence":"additional","affiliation":[]},{"given":"Shalmoli","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Sambudha","family":"Roy","sequence":"additional","affiliation":[]},{"given":"Yogish","family":"Sabharwal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,16]]},"reference":[{"key":"515_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., & Wiese, A. (2013). Approximation schemes for maximum weight independent set of rectangles. In 54th Annual IEEE symposium on foundations of computer science, FOCS (pp. 400\u2013409).","DOI":"10.1109\/FOCS.2013.50"},{"key":"515_CR2","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Chalermsook, P., Ene, A., & Wiese, A. (2016). Submodular unsplittable flow on trees. In Proceedings of the 18th conference on integer programming and combinatorial optimization (IPCO).","DOI":"10.1007\/978-3-319-33461-5_28"},{"issue":"3\u20134","key":"515_CR3","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"P Agarwal","year":"1998","unstructured":"Agarwal, P., Kreveld, M., & Suri, S. (1998). Label placement by maximum independent set in rectangles. Computational Geometry, 11(3\u20134), 209\u2013218.","journal-title":"Computational Geometry"},{"key":"515_CR4","unstructured":"Akcoglu, K., Aspnes, J., Dasgupta, B., & Kao, M. (2000). Opportunity cost algorithms for combinatorial auctions. In E. Kontoghiorghes, B. Rustem, & S. Siokos (Eds.), Applied optimization: Computational methods in decision-making, economics and finance (pp. 455\u2013476) Kluwer Academic Publishers."},{"key":"515_CR5","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., & Wiese, A. (2013). Constant integrality gap LP formulations of unsplittable flow on a path. In Proceedings of the 16th international conference on integer programming and combinatorial optimization (IPCO) (pp. 25\u201336).","DOI":"10.1007\/978-3-642-36694-9_3"},{"key":"515_CR6","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., & Wiese, A. (2014). A mazing \n                        $$2+\\epsilon $$\n                        \n                            \n                                \n                                    2\n                                    +\n                                    \u03f5\n                                \n                            \n                        \n                     approximation for Unsplittable Flow on a Path. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 26\u201341).","DOI":"10.1137\/1.9781611973402.3"},{"key":"515_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., & Schieber, B. (2006). A quasi-PTAS for unsplittable flow on line graphs. In Proceedings of the 38th annual ACM symposium on theory of computing, STOC (pp. 721\u2013729).","DOI":"10.1145\/1132516.1132617"},{"key":"515_CR8","doi-asserted-by":"crossref","unstructured":"Bansal, N., Friggstad, Z., Khandekar, R., & Salavatipour, M. (2009). A logarithmic approximation for unsplittable flow on line graphs. In Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 702\u2013709).","DOI":"10.1137\/1.9781611973068.77"},{"issue":"5","key":"515_CR9","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., & Schieber, B. (2001). A unified approach to approximating resource allocation and scheduling. Journal of the ACM, 48(5), 1069\u20131090.","journal-title":"Journal of the ACM"},{"issue":"2","key":"515_CR10","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., Noar, J., & Schieber, B. (2001). Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing SICOMP, 31(2), 331\u2013352.","journal-title":"SIAM Journal on Computing SICOMP"},{"issue":"3","key":"515_CR11","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/A:1009822211065","volume":"4","author":"P Berman","year":"2000","unstructured":"Berman, P., & Dasgupta, B. (2000). Multi-phase algorithms for throughput maximization for real-time scheduling. Journal of Combinatorial Optimization, 4(3), 307\u2013323.","journal-title":"Journal of Combinatorial Optimization"},{"key":"515_CR12","doi-asserted-by":"crossref","unstructured":"Bonsma, P., Schulz, J., & Wiese, A. (2011). A constant factor approximation algorithm for unsplittable flow on paths. In IEEE 52nd annual symposium on foundations of computer science, FOCS (pp. 47\u201356).","DOI":"10.1109\/FOCS.2011.10"},{"key":"515_CR13","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chakrabarti, A., Karloff, H.\u00a0J., & Rabani, Y. (2002). Improved approximation algorithms for resource allocation. In Integer programming and combinatorial optimization, 9th International IPCO (pp. 401\u2013414).","DOI":"10.1007\/3-540-47867-1_28"},{"key":"515_CR14","unstructured":"Chakaravarthy, V., Choudhury, A.\u00a0R., & Sabharwal, Y. (2010). A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints. In IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS (pp. 181\u2013191)."},{"key":"515_CR15","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Choudhury, A., Roy, S., & Sabharwal, Y. (2013). Distributed algorithms for scheduling on line and tree networks with non-uniform bandwidths. In 27th IEEE international symposium on parallel and distributed processing, IPDPS (pp. 973\u2013984).","DOI":"10.1109\/IPDPS.2013.92"},{"key":"515_CR16","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Pandit, V., Sabharwal, Y., & Seetharam, D. (2010). Varying bandwidth resource allocation problem with bag constraints. In 24th IEEE international symposium on parallel and distributed processing, IPDPS  (pp. 1\u201310).","DOI":"10.1109\/IPDPS.2010.5470347"},{"key":"515_CR17","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Roy, S., & Sabharwal, Y. (2012). Distributed algorithms for scheduling on line and tree networks. In ACM symposium on principles of distributed computing, PODC (pp. 345\u2013354).","DOI":"10.1145\/2332432.2332503"},{"issue":"1","key":"515_CR18","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s00453-006-1210-5","volume":"47","author":"A Chakrabarti","year":"2007","unstructured":"Chakrabarti, A., Chekuri, C., Gupta, A., & Kumar, A. (2007). Approximation algorithms for the unsplittable flow problem. Algorithmica, 47(1), 53\u201378.","journal-title":"Algorithmica"},{"key":"515_CR19","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., & Chuzhoy, J. (2009). Maximum independent set of rectangles. In Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 892\u2013901).","DOI":"10.1137\/1.9781611973068.97"},{"key":"515_CR20","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A., & Korula, N. (2009). Unsplittable flow in paths and trees and column-restricted packing integer programs. In Proceedings of the 12th international workshop on approximation, randomization, and combinatorial optimization (APPROX) (pp.42\u201355).","DOI":"10.1007\/978-3-642-03685-9_4"},{"key":"515_CR21","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Mydlarz, M., & Shepherd, F. (2007). Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms, 3(3), 27. doi:\n                        10.1145\/1273340.1273343\n                        \n                    .","DOI":"10.1145\/1273340.1273343"},{"key":"515_CR22","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Ostrovsky, R., & Rabani, Y (2001). Approximation algorithms for the job interval selection problem and related scheduling problems. In 42nd Annual symposium on foundations of computer science, FOCS (pp. 348\u2013356).","DOI":"10.1109\/SFCS.2001.959909"},{"key":"515_CR23","unstructured":"Elbassioni, K., Garg, N., Gupta, D., Kumar, A., Narula, V., & Pal, A. (2012). Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees. In IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS (pp. 267\u2013275)."},{"issue":"1","key":"515_CR24","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. Journal of Algorithms, 46(1), 27\u201353.","journal-title":"Journal of Algorithms"},{"issue":"3","key":"515_CR25","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R Fowler","year":"1981","unstructured":"Fowler, R., Paterson, M., & Tanimoto, S. (1981). Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12(3), 133\u2013137.","journal-title":"Information Processing Letters"},{"key":"515_CR26","unstructured":"Grandoni, F., Ingala, S., & Uniyal, S. (2013). Improved approximation algorithms for unsplittable flow on a path with time windows. In Proceedings of the 13th workshop on approximation and online algorithms (pp. 25\u201336)."},{"key":"515_CR27","unstructured":"Khanna, S., Muthukrishnan, S., & Paterson, M. (1998). On approximating rectangle tiling and packing. In Proceedings of the ninth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 384\u2013393)."},{"key":"515_CR28","volume-title":"Handbook of approximation algorithms and metaheuristics","author":"S Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S. (2007). Edge-disjoint paths and unsplittable flow. In T. Gonzalez (Ed.), Handbook of approximation algorithms and metaheuristics. London: Chapman and Hall."},{"issue":"4","key":"515_CR29","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00446-010-0100-x","volume":"22","author":"A Panconesi","year":"2010","unstructured":"Panconesi, A., & Sozio, M. (2010). Fast primal-dual distributed algorithms for scheduling and matching problems. Distributed Computing, 22(4), 269\u2013283.","journal-title":"Distributed Computing"},{"key":"515_CR30","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y","volume":"2","author":"F Spieksma","year":"1999","unstructured":"Spieksma, F. (1999). On the approximability of an interval scheduling problem. Journal of Scheduling, 2, 215\u2013227.","journal-title":"Journal of Scheduling"},{"issue":"2","key":"515_CR31","first-page":"14","volume":"8","author":"Y Ye","year":"2012","unstructured":"Ye, Y., & Borodin, A. (2012). Elimination graphs. ACM Transactions on Algorithms, 8(2), 14.","journal-title":"ACM Transactions on Algorithms"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-017-0515-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0515-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0515-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,5,29]],"date-time":"2018-05-29T07:03:37Z","timestamp":1527577417000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-017-0515-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,16]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["515"],"URL":"https:\/\/doi.org\/10.1007\/s10951-017-0515-3","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2017,2,16]]}}}