{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089698,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MINERVA foundation (ARCHES 2011)"},{"name":"Israeli Science Foundation","award":["1016\/17"],"award-info":[{"award-number":["1016\/17"]}]},{"name":"Israeli Ministry of Science (in a program with JSPS)"},{"name":"BSF"},{"name":"ISF-NSFC","award":["2560\/17"],"award-info":[{"award-number":["2560\/17"]}]},{"name":"Israel Council for Higher Education"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188812","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"598-606","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating generalized network design under (dis)economies of scale with applications to energy efficiency"],"prefix":"10.1145","author":[{"given":"Yuval","family":"Emek","sequence":"first","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ron","family":"Lavi","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yangguang","family":"Shi","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735223.1735245"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.32"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2159864"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/110825959"},{"key":"e_1_3_2_2_6_1","volume-title":"Lisa Zhang, and Wenbo Zhao.","author":"Andrews Matthew","year":"2013","unstructured":"Matthew Andrews , Antonio Fern\u00e1ndez Anta , Lisa Zhang, and Wenbo Zhao. 2013 . Matthew Andrews, Antonio Fern\u00e1ndez Anta, Lisa Zhang, and Wenbo Zhao. 2013."},{"key":"e_1_3_2_2_7_1","volume-title":"Networks 61, 3","author":"Routing","year":"2013","unstructured":"Routing and scheduling for energy and delay minimization in the power down model. Networks 61, 3 ( 2013 ), 226\u2013237. Preliminary version in INFOCOM\u2019 10. Routing and scheduling for energy and delay minimization in the power down model. Networks 61, 3 (2013), 226\u2013237. Preliminary version in INFOCOM\u201910."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_3_2_2_9_1","unstructured":"Antonios Antoniadis Sungjin Im Ravishankar Krishnaswamy Benjamin Moseley Viswanath Nagarajan Kirk Pruhs and Cliff Stein. 2014. Antonios Antoniadis Sungjin Im Ravishankar Krishnaswamy Benjamin Moseley Viswanath Nagarajan Kirk Pruhs and Cliff Stein. 2014."},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201914)","author":"Hallucination","key":"e_1_3_2_2_10_1","unstructured":"Hallucination helps : energy efficient virtual circuit routing . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201914) . Society for Industrial and Applied Mathematics, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1141\u20131153. Hallucination helps: energy efficient virtual circuit routing. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201914). Society for Industrial and Applied Mathematics, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1141\u20131153."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796341"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386832"},{"key":"e_1_3_2_2_13_1","volume-title":"Load Balancing in the Lp Norm. In 36th Annual Symposium on Foundations of Computer Science FOCS. IEEE","author":"Awerbuch Baruch","year":"1995","unstructured":"Baruch Awerbuch , Yossi Azar , Edward F. Grove , Ming-Yang Kao , P. Krishnan , and Jeffrey Scott Vitter . 1995 . Load Balancing in the Lp Norm. In 36th Annual Symposium on Foundations of Computer Science FOCS. IEEE , Milwaukee, WI, USA, 383\u2013391. Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, and Jeffrey Scott Vitter. 1995. Load Balancing in the Lp Norm. In 36th Annual Symposium on Foundations of Computer Science FOCS. IEEE, Milwaukee, WI, USA, 383\u2013391."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060639"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.02.003"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206038"},{"key":"e_1_3_2_2_17_1","unstructured":"Jaros\u0142aw Byrka Fabrizio Grandoni Thomas Rothvoss and Laura Sanit\u00e0. 2013. Jaros\u0142aw Byrka Fabrizio Grandoni Thomas Rothvoss and Laura Sanit\u00e0. 2013."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/314613.314700"},{"key":"e_1_3_2_2_20_1","unstructured":"Moses Charikar and Adriana Karagiozova. 2005. Moses Charikar and Adriana Karagiozova. 2005."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060617"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921664"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958020"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Ho-Lin Chen Tim Roughgarden and Gregory Valiant. 2010. Ho-Lin Chen Tim Roughgarden and Gregory Valiant. 2010.","DOI":"10.1093\/database\/baq002"},{"key":"e_1_3_2_2_25_1","volume-title":"1799\u20131832","author":"Comput Designing","year":"2010","unstructured":"Designing network protocols for good equilibria. SIAM J. Comput . 39, 5 ( 2010 ), 1799\u20131832 . Designing network protocols for good equilibria. SIAM J. Comput. 39, 5 (2010), 1799\u20131832."},{"key":"e_1_3_2_2_26_1","unstructured":"Preliminary version in SODA\u201904. Preliminary version in SODA\u201904."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2010.5621967"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993708"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_2_2_30_1","volume-title":"Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency. ArXiv e-prints (March","author":"Emek Yuval","year":"2018","unstructured":"Yuval Emek , Shay Kutten , Ron Lavi , and Yangguang Shi . 2018. Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency. ArXiv e-prints (March 2018 ). arXiv: 1803.05361 Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi. 2018. Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency. ArXiv e-prints (March 2018). arXiv: 1803.05361"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13129-0_6"},{"key":"e_1_3_2_2_33_1","unstructured":"Sergiu Hart and Andreu Mas-Colell. 1989. Sergiu Hart and Andreu Mas-Colell. 1989."},{"volume-title":"Econometrica: Journal of the Econometric Society","year":"1989","key":"e_1_3_2_2_34_1","unstructured":"Potential, Value, and Consistency. Econometrica: Journal of the Econometric Society ( 1989 ), 589\u2013614. Potential, Value, and Consistency. Econometrica: Journal of the Econometric Society (1989), 589\u2013614."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067324"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873711"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2781678"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1552285.1552289"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_3_2_2_40_1","unstructured":"Jian Li and Samir Khuller. 2011. Jian Li and Samir Khuller. 2011."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32241-9_48"},{"key":"e_1_3_2_2_42_1","unstructured":"Konstantin Makarychev and Maxim Sviridenko. 2014. Konstantin Makarychev and Maxim Sviridenko. 2014."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.67"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1387589.1387612"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.16"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806883"},{"key":"e_1_3_2_2_47_1","unstructured":"Tim Roughgarden and Okke Schrijvers. 2016. Tim Roughgarden and Okke Schrijvers. 2016."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2841228"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"e_1_3_2_2_50_1","unstructured":"Philipp von Falkenhausen and Tobias Harks. 2013. Philipp von Falkenhausen and Tobias Harks. 2013."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0567"},{"volume-title":"Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE","author":"Yao F.","key":"e_1_3_2_2_52_1","unstructured":"F. Yao , A. Demers , and S. Shenker . 1995. A scheduling model for reduced CP U energy . In Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE , Milwaukee, WI, USA, 374\u2013382. Abstract 1 Introduction 1.1 Comparison to Existing Results 1.2 Paper Organization 2 Preliminaries 3 Technical Overview 4 Algorithm Description 5 Analyzing Alg-ABRD 6 Smoothness of the GND Game 7 The Potential Function of the Shapley Cost Sharing Mechanism Acknowledgments References F. Yao, A. Demers, and S. Shenker. 1995. A scheduling model for reduced CP U energy. In Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE, Milwaukee, WI, USA, 374\u2013382. Abstract 1 Introduction 1.1 Comparison to Existing Results 1.2 Paper Organization 2 Preliminaries 3 Technical Overview 4 Algorithm Description 5 Analyzing Alg-ABRD 6 Smoothness of the GND Game 7 The Potential Function of the Shapley Cost Sharing Mechanism Acknowledgments References"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188812","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188812","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188812"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":52,"alternative-id":["10.1145\/3188745.3188812","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188812","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}