TY - JOUR
T1 - Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
AU - Emek, Yuval
AU - Kutten, Shay
AU - Lavi, Ron
AU - Shi, Yangguang
N1 - Funding Information:
The work of Yuval Emek was supported in part by an Israeli Science Foundation grant number 1016/17. The work of Shay Kutten was supported in part by a grant from the ministry of science in the program that is joint with JSPS and in part by the BSF. The work of Ron Lavi was partially supported by the ISF-NSFC joint research program (grant No. 2560/17). The work of Yangguang Shi was partially supported at the Technion by a fellowship of the Israel Council for Higher Education. An extended abstract of this article has appeared in the Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC 2018). Authors’ address: Y. Emek, S. Kutten, R. Lavi, and Y. Shi, Technion - Israel Institute of Technology, Haifa, Israel, 3200003; emails: {yemek, kutten, ronlavi, shiyangguang}@technion.ac.il. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2020 Association for Computing Machinery. 0004-5411/2020/02-ART7 $15.00 https://doi.org/10.1145/3377387
Publisher Copyright:
© 2020 ACM.
PY - 2020/2/7
Y1 - 2020/2/7
N2 - In a generalized network design (GND) problem, a set of resources are assigned (non-exclusively) to multiple requests. Each request contributes its weight to the resources it uses and the total load on a resource is then translated to the cost it incurs via a resource-specific cost function. Motivated by energy efficiency applications, recently, there is a growing interest in GND using cost functions that exhibit (dis)economies of scale ((D)oS), namely, cost functions that appear subadditive for small loads and superadditive for larger loads. 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 routing requests in undirected graphs, identifying the resources with the graph's edges, the current article presents a generic approximation framework that yields approximation results for a much wider family of requests (including various types of Steiner tree and Steiner forest 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 unrelated weights, thus providing the first non-trivial approximation for the problem of scheduling unrelated parallel machines with (D)oS cost functions; (3) while most of the existing approximation algorithms are based on convex programming, our approximation framework is fully combinatorial 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' 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's smoothness toolbox [43], thus demonstrating the possible usefulness of this toolbox in the area of approximation algorithms.
AB - In a generalized network design (GND) problem, a set of resources are assigned (non-exclusively) to multiple requests. Each request contributes its weight to the resources it uses and the total load on a resource is then translated to the cost it incurs via a resource-specific cost function. Motivated by energy efficiency applications, recently, there is a growing interest in GND using cost functions that exhibit (dis)economies of scale ((D)oS), namely, cost functions that appear subadditive for small loads and superadditive for larger loads. 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 routing requests in undirected graphs, identifying the resources with the graph's edges, the current article presents a generic approximation framework that yields approximation results for a much wider family of requests (including various types of Steiner tree and Steiner forest 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 unrelated weights, thus providing the first non-trivial approximation for the problem of scheduling unrelated parallel machines with (D)oS cost functions; (3) while most of the existing approximation algorithms are based on convex programming, our approximation framework is fully combinatorial 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' 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's smoothness toolbox [43], thus demonstrating the possible usefulness of this toolbox in the area of approximation algorithms.
KW - (dis)economies of scale
KW - Approximation algorithms
KW - best response dynamics
KW - energy consumption
KW - generalized network design
KW - real exponent polynomial cost functions
KW - smoothness
UR - http://www.scopus.com/inward/record.url?scp=85083037609&partnerID=8YFLogxK
U2 - 10.1145/3377387
DO - 10.1145/3377387
M3 - Article
SN - 0004-5411
VL - 67
SP - 1
EP - 33
JO - Journal of the ACM
JF - Journal of the ACM
IS - 1
M1 - 7
ER -