{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:00:06Z","timestamp":1760014806713},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662447765"},{"type":"electronic","value":"9783662447772"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44777-2_19","type":"book-chapter","created":{"date-parts":[[2014,8,16]],"date-time":"2014-08-16T10:43:15Z","timestamp":1408185795000},"page":"222-234","source":"Crossref","is-referenced-by-count":11,"title":["Improved Algorithms for Resource Allocation under Varying Capacity"],"prefix":"10.1007","author":[{"given":"Venkatesan T.","family":"Chakaravarthy","sequence":"first","affiliation":[]},{"given":"Anamitra R.","family":"Choudhury","sequence":"additional","affiliation":[]},{"given":"Shalmoli","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[]},{"given":"Yogish","family":"Sabharwal","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: FOCS (2013)","DOI":"10.1109\/FOCS.2013.50"},{"issue":"3-4","key":"19_CR2","doi-asserted-by":"publisher","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.: Label placement by maximum independent set in rectangles. Computational Geometry\u00a011(3-4), 209\u2013218 (1998)","journal-title":"Computational Geometry"},{"key":"19_CR3","unstructured":"Akcoglu, K., Aspnes, J., Dasgupta, B., Kao, M.: Opportunity cost algorithms for combinatorial auctions. In: Kontoghiorghes, E., Rustem, B., Siokos, S. (eds.) Applied Optimization: Computational Methods in Decision-Making (2000)"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing 2\u2009+\u2009\u03b5 approximation for Unsplittable Flow on a Path. In: Proceedings of the Symposium on Discrete Algorithms, SODA 2014 (2014)","DOI":"10.1137\/1.9781611973402.3"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: STOC (2006)","DOI":"10.1145\/1132516.1132617"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, M.: A logarithmic approximation for unsplittable flow on line graphs. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.77"},{"issue":"5","key":"19_CR7","doi-asserted-by":"publisher","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.: A unified approach to approximating resource allocation and scheduling. Journal of the ACM\u00a048(5), 1069\u20131090 (2001)","journal-title":"Journal of the ACM"},{"issue":"2","key":"19_CR8","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., Noar, J., Schieber, B.: Approximating the throughput of multiple machines in real-time scheduling. SICOMP\u00a031(2), 331\u2013352 (2001)","journal-title":"SICOMP"},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/A:1009822211065","volume":"4","author":"P. Berman","year":"2000","unstructured":"Berman, P., Dasgupta, B.: Multi-phase algorithms for throughput maximization for real-time scheduling. J. of Comb. Opt.\u00a04, 307\u2013323 (2000)","journal-title":"J. of Comb. Opt."},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Bonsma, P., Schulz, J., Wiese, A.: A constant factor approximation algorithm for unsplittable flow on paths. In: FOCS (2011)","DOI":"10.1109\/FOCS.2011.10"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/3-540-47867-1_28","volume-title":"Integer Programming and Combinatorial Optimization","author":"G. Calinescu","year":"2002","unstructured":"Calinescu, G., Chakrabarti, A., Karloff, H., Rabani, Y.: Improved approximation algorithms for resource allocation. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 401\u2013414. Springer, Heidelberg (2002)"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Choudhury, A., Roy, S., Sabharwal, Y.: Distributed algorithms for scheduling on line and tree networks with non-uniform bandwidths. In: IPDPS (2013)","DOI":"10.1109\/IPDPS.2013.92"},{"key":"19_CR13","unstructured":"Chakaravarthy, V., Choudhury, A.R., Sabharwal, Y.: A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints. In: FSTTCS (2010)"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Pandit, V., Sabharwal, Y., Seetharam, D.: Varying bandwidth resource allocation problem with bag constraints. In: IPDPS (2010)","DOI":"10.1109\/IPDPS.2010.5470347"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Roy, S., Sabharwal, Y.: Distributed algorithms for scheduling on line and tree networks. In: PODC (2012)","DOI":"10.1145\/2332432.2332503"},{"issue":"1","key":"19_CR16","doi-asserted-by":"publisher","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.: Approximation algorithms for the unsplittable flow problem. Algorithmica\u00a047(1), 53\u201378 (2007)","journal-title":"Algorithmica"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.97"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-642-03685-9_4","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C. Chekuri","year":"2009","unstructured":"Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. LNCS, vol.\u00a05687, pp. 42\u201355. Springer, Heidelberg (2009)"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Mydlarz, M., Shepherd, F.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. on Algorithms\u00a03(3) (2007)","DOI":"10.1145\/1273340.1273343"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Ostrovsky, R., Rabani, Y.: Approximation algorithms for the job interval selection problem and related scheduling problems. In: FOCS (2001)","DOI":"10.1109\/SFCS.2001.959909"},{"key":"19_CR21","unstructured":"Elbassioni, K., Garg, N., Gupta, D., Kumar, A., Narula, V., Pal, A.: Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees. In: FSTTCS (2012)"},{"issue":"1","key":"19_CR22","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. J. Algorithms\u00a046(1), 27\u201353 (2003)","journal-title":"J. Algorithms"},{"key":"19_CR23","unstructured":"Khanna, S., Muthukrishnan, S., Paterson, M.: On approximating rectangle tiling and packing. In: SODA (1998)"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S.: Edge-disjoint paths and unsplittable flow. In: Gonzalez, T. (ed.) Handbook of Approximation Algorithms and Metaheuristics, Chapman and Hall\/CRC (2007)","DOI":"10.1201\/9781420010749.ch57"},{"issue":"4","key":"19_CR25","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00446-010-0100-x","volume":"22","author":"A. Panconesi","year":"2010","unstructured":"Panconesi, A., Sozio, M.: Fast primal-dual distributed algorithms for scheduling and matching problems. Distributed Computing\u00a022(4), 269\u2013283 (2010)","journal-title":"Distributed Computing"},{"key":"19_CR26","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":"F. Spieksma","year":"1999","unstructured":"Spieksma, F.: On the approximability of an interval scheduling problem. J. of Scheduling\u00a02, 215\u2013227 (1999)","journal-title":"J. of Scheduling"},{"issue":"2","key":"19_CR27","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/2151171.2151177","volume":"8","author":"Y. Ye","year":"2012","unstructured":"Ye, Y., Borodin, A.: Elimination graphs. ACM Transactions on Algorithms\u00a08(2), 14 (2012)","journal-title":"ACM Transactions on Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2014"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44777-2_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T16:03:31Z","timestamp":1558973011000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44777-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662447765","9783662447772"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44777-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}