{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:58Z","timestamp":1725551158563},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633075"},{"type":"electronic","value":"9783540694229"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63307-3_51","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T19:22:48Z","timestamp":1270495368000},"page":"104-115","source":"Crossref","is-referenced-by-count":11,"title":["Constrained TSP and low-power computing"],"prefix":"10.1007","author":[{"given":"Moses","family":"Charikar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Motwani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prabhakar","family":"Raghavan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Craig","family":"Silverstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, A.K. Chandra and P. Raghavan. Energy Consumption in VLSI Circuits. In Proceedings of the ACM Symposium on Theory of Computing, 1988, pp. 205\u2013216.","DOI":"10.1145\/62212.62230"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"R. Bhatia, S. Khuller, and J. Naor. The Loading Time Scheduling Problem. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, pp. 72\u201381.","DOI":"10.1109\/SFCS.1995.492464"},{"issue":"1","key":"9_CR3","first-page":"19","volume":"32","author":"L. Bianco","year":"1994","unstructured":"L. Bianco, A. Mingozzi, S. Riccardelli, and M. Spadoni. Exact and Heuristic Procedures for the Traveling Salesman Problem with Precedence Constraints, Based on Dynamic Programming. INFOR, 32(1):19\u201332, 1994.","journal-title":"INFOR"},{"key":"9_CR4","unstructured":"N. Christofides. Vehicle Routing. In The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Ed: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys), John Wiley & Sons (1985), pp. 431\u2013448."},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF00383598","volume":"1","author":"C.J. Colbourn","year":"1985","unstructured":"C.J. Colbourn and W.R. Pulleyblank. Minimizing Setups in Ordered Sets of Fixed Width. Order, 1:225\u2013229 (1985).","journal-title":"Order"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"S. Devadas and S. Malik. A Survey of Optimization Techniques Targeting Low-Power VLSI Circuits. Preprint, 1995.","DOI":"10.1145\/217474.217536"},{"key":"9_CR7","volume-title":"Computers and Intractability \u2014 a Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson. Computers and Intractability \u2014 a Guide to the Theory of NP-completeness. W.H. Freeman, San Francisco, 1979."},{"volume-title":"Vehicle Routing. Methods and Studies","year":"1988","key":"9_CR8","unstructured":"B.L. Golden and A.A. Assad, Eds. Vehicle Routing. Methods and Studies. North-Holland, Amsterdam (1988)."},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"K. Govil, E. Chan, and H. Wasserman. Comparing Algorithms for Dynamic Speed-Setting of a Low-Power CPU. Preprint, 1995.","DOI":"10.1145\/215530.215546"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"T. Jiang and M. Li. On the Approximation of Shortest Common Supersequences and Longest Common Subsequences. In Proceedings of 21st International Colloquium on Automata, Languages and Programming, 1994, pp. 191\u2013202.","DOI":"10.1007\/3-540-58201-0_68"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"G. Kissin. Energy Consumption in VLSI Circuits: a Foundation. ACM Symposium on Theory of Computing, 1982.","DOI":"10.1145\/800070.802181"},{"issue":"4","key":"9_CR12","doi-asserted-by":"crossref","first-page":"354","DOI":"10.15807\/jorsj.33.354","volume":"30","author":"M. Kubo","year":"1990","unstructured":"M. Kubo and H. Kagusai. Heuristic Algorithms for the Single-Vehicle Dial-a-ride Problem. Journal of the Operations Research Society of Japan, 30(4):354\u2013365, 1990.","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"M. T Lee, V. Tiwari, S. Malik, and M. Fujita. Power Analysis and Low-Power Scheduling Techniques for Embedded DSP Software. Technical Report FLA-CAD-95-O1, Fujitsu Labs of America, March 1996.","DOI":"10.1145\/224486.224525"},{"key":"9_CR14","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M. Manasse","year":"1990","unstructured":"M. Manasse, L. McGeoch, and D. Sleator. Competitive Algorithms for Server Problems. Journal of Algorithms, 11:208\u2013230 (1990).","journal-title":"Journal of Algorithms"},{"key":"9_CR15","unstructured":"R. Motwani, K. Palem, S. Reyen, and V Sarkar. Combining Register Allocation and Instruction Scheduling. Submitted for publication, 1997. Preliminary version: Technical Report STAN-CS-TN-95-22, Department of Computer Science, Stanford University, 1996."},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"S. Prasad and K. Roy. Circuit Activity Driven Multilevel Logic Optimization for Low Power Reliable Operation. Proceedings of the European Conference on Design Autoamtion (EDAC), 1993, pp. 368\u2013372.","DOI":"10.1109\/EDAC.1993.386448"},{"key":"9_CR17","unstructured":"K. Roy and S. Prasad. SYSLOP: Synthesis of CMOS Logic for Low-Power Applications. In Proceedings of the International Conference on Computer Design, 1992."},{"key":"9_CR18","unstructured":"SPEC Consortium. The SPECint95 and SPECfp95 Benchmarks. World-Wide Web URL http:\/\/www.specbench.org, 1995."},{"key":"9_CR19","unstructured":"C-L. Su, C-Y Tsui, and A.M. Despain. Low-Power Architecture Design and Compilation Techniques for High-Performance Processors. In Proceedings of the IEEE COMPCON, 1994, pp. 489\u2013498."},{"key":"9_CR20","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1109\/92.335012","volume":"2","author":"V. Tiwari","year":"1994","unstructured":"V. Tiwari, S. Malik, and A. Wolfe. Power analysis of embedded software: A first step towards software power minimization. IEEE Transaction on VLSI Systems, 2:437\u2013445 (1994).","journal-title":"IEEE Transaction on VLSI Systems"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"V. Tiwari, S. Malik, and A. Wolfe. Compilation Techniques for Low Energy: An Overview. In Proceedings of the 1994 Symposium on Low-Power Electronics, 1994, pp. 38\u201339.","DOI":"10.1109\/LPE.1994.573195"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"C.Y. Tsui, M. Pedram, and A.M. Despain. Technology Decomposition and Mapping Targeting Low-Power Dissipation. In Proceedings of the 30th Design Automation Conference, 1993, pp. 68\u201373.","DOI":"10.1145\/157485.164577"},{"key":"9_CR23","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/159544.159617","volume":"36","author":"M. Weiser","year":"1993","unstructured":"M. Weiser. Some Computer Science Issues in Ubiquitous Computing. Communications of the ACM, 36:74\u201383 (1993).","journal-title":"Communications of the ACM"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"F. Yao, A. Demers, and S. Shenker. A Scheduling Model for Reduced CPU Energy. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, pp. 374\u2013382.","DOI":"10.1109\/SFCS.1995.492493"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63307-3_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:18:37Z","timestamp":1559002717000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63307-3_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633075","9783540694229"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-63307-3_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}