{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T05:40:07Z","timestamp":1746250807757,"version":"3.40.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,5,30]],"date-time":"2014-05-30T00:00:00Z","timestamp":1401408000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s00453-014-9888-2","type":"journal-article","created":{"date-parts":[[2014,5,29]],"date-time":"2014-05-29T18:49:22Z","timestamp":1401389362000},"page":"1011-1032","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Register Loading via Linear Programming"],"prefix":"10.1007","volume":"72","author":[{"given":"Gruia","family":"Calinescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minming","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,5,30]]},"reference":[{"key":"9888_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"Spencer. The probabilistic method","author":"N Alon","year":"2000","unstructured":"Alon, N., Joel, H.: Spencer. The probabilistic method, 2nd edn. Wiley, Hoboken, NJ (2000)","edition":"2"},{"key":"9888_CR2","doi-asserted-by":"crossref","unstructured":"Amit, A., Noga, A., Moses, S.: Charikar. Improved approximation for directed cut problems. In: Proceedings of the thirty-ninth annual ACM symposium on Theory of Computing, STOC \u201907, pp. 671\u2013680. ACM, New York, NY (2007)","DOI":"10.1145\/1250790.1250888"},{"key":"9888_CR3","doi-asserted-by":"crossref","unstructured":"Bergner, P., Dahl, P., Engebretsen, D., O\u2019Keefe, M.: Spill code minimization via interference region spilling. In: Proceedings of the ACM SIGPLAN 1997 conference on Programming Language Design and Implementation, PLDI \u201997, pp. 287\u2013295. ACM, New York, NY (1997)","DOI":"10.1145\/258915.258941"},{"key":"9888_CR4","doi-asserted-by":"crossref","unstructured":"Bernstein, D., Golumbic, M., Mansour, Y., Pinter, R., Goldin, D., Krawczyk, H. Nahshon, I.: Spill code minimization techniques for optimizing compliers. In: Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, PLDI \u201989, pp. 258\u2013263. ACM, New York, NY (1989)","DOI":"10.1145\/73141.74841"},{"key":"9888_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/130616.130617","volume":"1","author":"P Briggs","year":"1992","unstructured":"Briggs, P., Cooper, K.D., Torczon, L.: Coloring register pairs. ACM Lett. Program. Lang. Sys. 1, 3\u201313 (1992)","journal-title":"ACM Lett. Program. Lang. Sys."},{"key":"9888_CR6","doi-asserted-by":"crossref","unstructured":"Changqing, Fu., Wilken, K.: A faster optimal register allocator. In: Proceedings of the 35th annual ACM\/IEEE International symposium on Microarchitecture, MICRO 35, pp. 245\u2013256. IEEE Computer Society Press, Los Alamitos, CA (2002)","DOI":"10.1109\/MICRO.2002.1176254"},{"issue":"1","key":"9888_CR7","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T.Y., Dai, Z., Goel, A., Guha, Sudipto, Li, Ming: Approximation algorithms for directed Steiner problems. J. Algo. 33(1), 73\u201391 (1999)","journal-title":"J. Algo."},{"issue":"3","key":"9888_CR8","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s00493-005-0015-5","volume":"25","author":"J Cheriyan","year":"2005","unstructured":"Cheriyan, J., Karloff, H.J., Rabani, Y.: Approximating directed multicuts. Combinatorica 25(3), 251\u2013269 (2005)","journal-title":"Combinatorica"},{"key":"9888_CR9","doi-asserted-by":"crossref","unstructured":"Cooper, K., Dasgupta, A., Eckhardt, J.: Revisiting graph coloring register allocation: a study of the Chaitin\u2013Briggs and Callahan\u2013Koblenz algorithms. In: Ayguad, E., Baumgartner, G., Ramanujam, J., Sadayappan, P., (eds) Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science, vol. 4339, pp. 1\u201316. Springer, Berlin (2006)","DOI":"10.1007\/978-3-540-69330-7_1"},{"issue":"5","key":"9888_CR10","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput. 34(5), 1129\u20131146 (2005)","journal-title":"SIAM J. Comput."},{"key":"9888_CR11","doi-asserted-by":"crossref","unstructured":"Falk, H.: Wcet-aware register allocation based on graph coloring. In: Proceedings of the Fourty-Sixth ACM\/IEEE Design Automation Conference, DAC\u201909. ACM, New York , NJ (2009)","DOI":"10.1145\/1629911.1630100"},{"key":"9888_CR12","unstructured":"Freescale. http:\/\/www.freescale.com"},{"issue":"1","key":"9888_CR13","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N Garg","year":"2004","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algo. 50(1), 49\u201361 (2004)","journal-title":"J. Algo."},{"key":"9888_CR14","unstructured":"Gupta, A.: Improved results for directed multicut. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, SODA \u201903, pp. 454\u2013455. Society for Industrial and Applied Mathematics, Philadelphia, PA (2003)"},{"issue":"1","key":"9888_CR15","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0166-218X(93)90167-M","volume":"43","author":"K Jansen","year":"1993","unstructured":"Jansen, K.: The allocation problem in hardware design. Discret. Appl. Math. 43(1), 37\u201346 (1993)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"9888_CR16","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/S0167-9260(98)00008-X","volume":"25","author":"K Jansen","year":"1998","unstructured":"Jansen, K., Reiter, J.: An approximation algorithm for the register allocation problem. Int. VLSI J. 25(2), 89\u2013102 (1998)","journal-title":"Int. VLSI J."},{"issue":"3","key":"9888_CR17","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/S0895480101396949","volume":"20","author":"K Jansen","year":"2006","unstructured":"Jansen, K., Porkolab, L.: On preemptiveresource constrained scheduling: polynomial-time approximation schemes. SIAM J. Discret. Math. 20(3), 545\u2013563 (2006)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"9888_CR18","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1006\/jagm.1998.0956","volume":"29","author":"S Kannan","year":"1998","unstructured":"Kannan, S., Proebsting, T.A.: Register allocation in structured programs. J. Algo. 29(2), 223\u2013237 (1998)","journal-title":"J. Algo."},{"key":"9888_CR19","doi-asserted-by":"crossref","unstructured":"Koes, D.R., Goldstein, S.C.: A global progressive register allocator. In: Proceedings of the ACM SIGPLAN 2006 conference on Programming language design and implementation, PLDI \u201906, pp. 204\u2013215. ACM, New York, NY (2006)","DOI":"10.1145\/1133981.1134006"},{"key":"9888_CR20","doi-asserted-by":"crossref","unstructured":"Koes, D., Goldstein, S.C.: A progressive register allocator for irregular architectures. In: Proceedings of the International Symposium on Code Generation and Optimization, CGO \u201905, pp. 269\u2013280. IEEE Computer Society, Washington, DC (2005)","DOI":"10.1109\/CGO.2005.4"},{"key":"9888_CR21","doi-asserted-by":"crossref","unstructured":"Koes, D.R., Goldstein, S.C.: Register allocation deconstructed. In: Proceedings of the 12th International Workshop on Software and Compilers for Embedded Systems, SCOPES \u201909, pp. 21\u201330. ACM, New York, NY (2009)","DOI":"10.1145\/1543820.1543824"},{"issue":"2","key":"9888_CR22","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/s10878-010-9365-z","volume":"23","author":"M Li","year":"2012","unstructured":"Li, M., Chun Jason, X., Tiantian, L., Yingchao, Z.: Analysis and approximation for bank selection instruction minimization on partitioned memory architecture. J. Comb. Optim. 23(2), 274\u2013291 (2012)","journal-title":"J. Comb. Optim."},{"key":"9888_CR23","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, E.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20, 257\u2013301 (1995)","journal-title":"Math. Oper. Res."},{"key":"9888_CR24","doi-asserted-by":"crossref","unstructured":"Quint\u00e3o Pereira, F.M., Pereira, J. Palsberg.: Register allocation by puzzle solving. In: Proceedings of the 2008 ACM SIGPLAN conference on Programming Language Design and Implementation, PLDI \u201908, pp. 216\u2013226. ACM, New York, NY (2008)","DOI":"10.1145\/1375581.1375609"},{"issue":"2","key":"9888_CR25","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"9888_CR26","doi-asserted-by":"crossref","unstructured":"Smith, M.D., Ramsey, N., Holloway, G.: A generalized algorithm for graph-coloring register allocation. In: Proceedings of the ACM SIGPLAN 2004 conference on Programming Language Design and Implementation, PLDI \u201904, pp. 277\u2013288. ACM, New York, NY (2004)","DOI":"10.1145\/996841.996875"},{"issue":"2","key":"9888_CR27","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M Thorup","year":"1998","unstructured":"Thorup, M.: All structured programs have small tree-width and good register allocation. Inf. Comput. 142(2), 159\u2013181 (1998)","journal-title":"Inf. Comput."},{"key":"9888_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/3-540-35767-X_16","volume-title":"Languages and Compilers for Parallel Computing","author":"J Zalamea","year":"2003","unstructured":"Zalamea, J., Llosa, J., Ayguad, E., Valero, M.: Modulo scheduling with integrated register spilling. In: Dietz, H. (ed.) Languages and Compilers for Parallel Computing. Lecture Notes in Computer Science, vol. 2624, pp. 239\u2013253. Springer, Berlin (2003)"},{"issue":"1","key":"9888_CR29","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"A Zelikovsky","year":"1997","unstructured":"Zelikovsky, A.: A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica 18(1), 99\u2013110 (1997)","journal-title":"Algorithmica"},{"key":"9888_CR30","unstructured":"Zhou, Y.: Hardness of register loading, 2010. Personal communication (2010)"},{"key":"9888_CR31","unstructured":"Zilog.: http:\/\/www.zilog.com"},{"key":"9888_CR32","unstructured":"Zosin, L., Khuller, S.: On directed Steiner trees. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201902, pp. 59\u201363. Society for Industrial and Applied Mathematics, San Francisco, CA (2002)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9888-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9888-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9888-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T04:58:57Z","timestamp":1746248337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9888-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,30]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9888"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9888-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2014,5,30]]}}}