{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,12]],"date-time":"2023-01-12T13:19:12Z","timestamp":1673529552615},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"Ministry of Science"},{"DOI":"10.13039\/501100003977","name":"Israeli Science Foundation","doi-asserted-by":"crossref","award":["1016\/17"]},{"name":"ISF-NSFC","award":["2560\/17"]},{"name":"JSPS"},{"name":"BSF"},{"DOI":"10.13039\/501100005385","name":"Israel Council for Higher Education","doi-asserted-by":"crossref"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,2,29]]},"abstract":"\n In a\n generalized network design (GND)<\/jats:italic>\n problem, a set of\n resources<\/jats:italic>\n are assigned (non-exclusively) to multiple\n requests<\/jats:italic>\n . Each request contributes its weight to the resources it uses and the total\n load<\/jats:italic>\n on a resource is then translated to the cost it incurs via a resource-specific cost function. Motivated by\n energy efficiency<\/jats:italic>\n applications, recently, there is a growing interest in GND using cost functions that exhibit\n (dis)economies of scale ((D)oS)<\/jats:italic>\n , namely, cost functions that appear subadditive for small loads and superadditive for larger loads.\n <\/jats:p>\n \n The current article advances the existing literature on approximation algorithms for GND problems with (D)oS cost functions in various aspects: (1) while the existing results are restricted to\n routing<\/jats:italic>\n requests in undirected graphs, identifying the resources with the graph\u2019s edges, the current article presents a generic\n approximation framework<\/jats:italic>\n that yields approximation results for a much wider family of requests (including various types of\n Steiner tree<\/jats:italic>\n and\n Steiner forest<\/jats:italic>\n requests) in both directed and undirected graphs, where the resources can be identified with either the edges or the vertices; (2) while the existing results assume that a request contributes the same weight to each resource it uses, our approximation framework allows for\n unrelated<\/jats:italic>\n weights, thus providing the first non-trivial approximation for the problem of\n scheduling unrelated parallel machines<\/jats:italic>\n with (D)oS cost functions; (3) while most of the existing approximation algorithms are based on convex programming, our approximation framework is fully\n combinatorial<\/jats:italic>\n and runs in strongly polynomial time; (4) the family of (D)oS cost functions considered in the current article is more general than the one considered in the existing literature, providing a more accurate abstraction for practical energy conservation scenarios; and (5) we obtain the first approximation ratio for GND with (D)oS cost functions that depends only on the parameters of the resources\u2019 technology and does not grow with the number of resources, the number of requests, or their weights. The design of our approximation framework relies heavily on Roughgarden\u2019s\n smoothness<\/jats:italic>\n toolbox [43], thus demonstrating the possible usefulness of this toolbox in the area of approximation algorithms.\n <\/jats:p>","DOI":"10.1145\/3377387","type":"journal-article","created":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T08:38:41Z","timestamp":1581064721000},"page":"1-33","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency"],"prefix":"10.1145","volume":"67","author":[{"given":"Yuval","family":"Emek","sequence":"first","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"given":"Ron","family":"Lavi","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-2923-2748","authenticated-orcid":false,"given":"Yangguang","family":"Shi","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2020,2,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Symposium on Distributed Computing. Springer","author":"Abraham Ittai","unstructured":"Ittai Abraham , Danny Dolev , and Joseph Y. Halpern . 2013. Distributed protocols for leader election: A game-theoretic perspective . In Proceedings of the International Symposium on Distributed Computing. Springer , Berlin, 61--75. Ittai Abraham, Danny Dolev, and Joseph Y. Halpern. 2013. Distributed protocols for leader election: A game-theoretic perspective. In Proceedings of the International Symposium on Distributed Computing. Springer, Berlin, 61--75."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735223.1735245"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.32"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2159864"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/110825959"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21474"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.84"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646143"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386832"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796265"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060639"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.02.003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206038"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics","author":"Charikar Moses","year":"1998","unstructured":"Moses Charikar , Chandra Chekuri , To-yat Cheung, Zuo Dai , Ashish Goel , Sudipto Guha , and Ming Li . 1998 . Approximation algorithms for directed Steiner problems . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, 192--200. Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. 1998. Approximation algorithms for directed Steiner problems. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 192--200."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060617"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921664"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958020"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958021"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2010.5621967"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993708"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13129-0_6"},{"key":"e_1_2_1_27_1","volume-title":"Online primal-dual for non-linear optimization with applications to speed scaling. CoRR abs\/1109.5931","author":"Gupta Anupam","year":"2011","unstructured":"Anupam Gupta , Ravishankar Krishnaswamy , and Kirk Pruhs . 2011. Online primal-dual for non-linear optimization with applications to speed scaling. CoRR abs\/1109.5931 ( 2011 ), 16. arxiv:1109.5931 http:\/\/arxiv.org\/abs\/1109.5931 Anupam Gupta, Ravishankar Krishnaswamy, and Kirk Pruhs. 2011. Online primal-dual for non-linear optimization with applications to speed scaling. CoRR abs\/1109.5931 (2011), 16. arxiv:1109.5931 http:\/\/arxiv.org\/abs\/1109.5931"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/1911054"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067324"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.016"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873711"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2781678"},{"key":"e_1_2_1_33_1","article-title":"A unified approach to scheduling on unrelated parallel machines","volume":"56","author":"Anil Kumar V. S.","year":"2009","unstructured":"V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , and Aravind Srinivasan . 2009 . A unified approach to scheduling on unrelated parallel machines . J. ACM 56 , 5, Article 28 (2009), 31 pages. V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. 2009. A unified approach to scheduling on unrelated parallel machines. J. ACM 56, 5, Article 28 (2009), 31 pages.","journal-title":"J. ACM"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133043"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32241-9_48"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.67"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1387589.1387612"},{"key":"e_1_2_1_39_1","volume-title":"Vazirani","author":"Nisan Noam","year":"2007","unstructured":"Noam Nisan , Tim Roughgarden , Eva Tardos , and Vijay V . Vazirani . 2007 . Algorithmic Game Theory. Vol. 1 . Cambridge University Press Cambridge , New York, NY, USA. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Vol. 1. Cambridge University Press Cambridge, New York, NY, USA."},{"key":"e_1_2_1_40_1","unstructured":"Debmalya Panigrahi. 2015. Design and Analysis of Algorithms. https:\/\/www.cs.duke.edu\/courses\/fall15\/cps232\/scribe_notes\/lec16.pdf. Debmalya Panigrahi. 2015. Design and Analysis of Algorithms. https:\/\/www.cs.duke.edu\/courses\/fall15\/cps232\/scribe_notes\/lec16.pdf."},{"key":"e_1_2_1_41_1","unstructured":"Tim Roughgarden. 2013. CS364A: Algorithmic Game Theory Lecture# 17: No-Regret Dynamics. Tim Roughgarden. 2013. CS364A: Algorithmic Game Theory Lecture# 17: No-Regret Dynamics."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.16"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806883"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2841228"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0567"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE","author":"Yao F.","unstructured":"F. Yao , A. Demers , and S. Shenker . 1995. A scheduling model for reduced CPU energy . In Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE , Milwaukee, WI, USA, 374--382. F. Yao, A. Demers, and S. Shenker. 1995. A scheduling model for reduced CPU energy. In Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE, Milwaukee, WI, USA, 374--382."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3377387","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T07:57:05Z","timestamp":1672559825000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3377387"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,7]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,29]]}},"alternative-id":["10.1145\/3377387"],"URL":"http:\/\/dx.doi.org\/10.1145\/3377387","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2020,2,7]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}