TY - GEN
T1 - Modelling the power supply network - Hardness and approximation
AU - Popa, Alexandru
PY - 2013/1/1
Y1 - 2013/1/1
N2 - In this paper we study a problem named graph partitioning with supply and demand (GPSD), motivated by applications in energy transmission. The input consists of an undirected graph G with the nodes partitioned into two sets: suppliers and consumers. Each supply node has associated a capacity and each consumer node has associated a demand. The goal is to find a subgraph of G and to partition it into trees, such that in each tree: (i) there is precisely one supplier and (ii) the total demand of the consumers is less than or equal to the capacity of the supplier. Moreover, we want to maximize the demand of all the consumers in such a partition. We also study a variation of the GPSD, termed energy delivery (ED). In this paper we show the following results: 1. A 2k-approximation algorithm for the GPSD problem, where k is the number of suppliers. This is the first approximation algorithm proposed for the general case. 2. A 2-approximation for the GPSD in the case of two suppliers implies a polynomial time algorithm for the famous minimum sum 2-disjoint paths problem, which is not known if it is in P or NP-hard. 3. The ED problem in the case of two or more suppliers is hard to approximate within any factor, assuming P ≠ NP.
AB - In this paper we study a problem named graph partitioning with supply and demand (GPSD), motivated by applications in energy transmission. The input consists of an undirected graph G with the nodes partitioned into two sets: suppliers and consumers. Each supply node has associated a capacity and each consumer node has associated a demand. The goal is to find a subgraph of G and to partition it into trees, such that in each tree: (i) there is precisely one supplier and (ii) the total demand of the consumers is less than or equal to the capacity of the supplier. Moreover, we want to maximize the demand of all the consumers in such a partition. We also study a variation of the GPSD, termed energy delivery (ED). In this paper we show the following results: 1. A 2k-approximation algorithm for the GPSD problem, where k is the number of suppliers. This is the first approximation algorithm proposed for the general case. 2. A 2-approximation for the GPSD in the case of two suppliers implies a polynomial time algorithm for the famous minimum sum 2-disjoint paths problem, which is not known if it is in P or NP-hard. 3. The ED problem in the case of two or more suppliers is hard to approximate within any factor, assuming P ≠ NP.
UR - http://www.scopus.com/inward/record.url?scp=84893466546&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893466546&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38236-9_7
DO - 10.1007/978-3-642-38236-9_7
M3 - Conference contribution
AN - SCOPUS:84893466546
SN - 9783642382352
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 62
EP - 71
BT - Theory and Applications of Models of Computation - 10th International Conference, TAMC 2013, Proceedings
PB - Springer Verlag
T2 - 10th International Conference on Theory and Applications of Models of Computation, TAMC 2013
Y2 - 20 May 2013 through 22 May 2013
ER -