Modelling the power supply network - Hardness and approximation

Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Pages62-71
Number of pages10
Volume7876 LNCS
ISBN (Print)9783642382352
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event10th International Conference on Theory and Applications of Models of Computation, TAMC 2013 - Hong Kong, China
Duration: May 20 2013May 22 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7876 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other10th International Conference on Theory and Applications of Models of Computation, TAMC 2013
CountryChina
CityHong Kong
Period5/20/135/22/13

Fingerprint

Approximation algorithms
Hardness
Graph Partitioning
Approximation
Modeling
Polynomials
Approximation Algorithms
Vertex of a graph
Energy
Partition
Disjoint Paths
Less than or equal to
Demand
Undirected Graph
Polynomial-time Algorithm
Subgraph
NP-complete problem
Maximise
Imply

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Popa, A. (2013). Modelling the power supply network - Hardness and approximation. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 7876 LNCS, pp. 62-71). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7876 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-38236-9_7

Modelling the power supply network - Hardness and approximation. / Popa, Alexandru.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7876 LNCS Springer Verlag, 2013. p. 62-71 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7876 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Popa, A 2013, Modelling the power supply network - Hardness and approximation. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 7876 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7876 LNCS, Springer Verlag, pp. 62-71, 10th International Conference on Theory and Applications of Models of Computation, TAMC 2013, Hong Kong, China, 5/20/13. https://doi.org/10.1007/978-3-642-38236-9_7
Popa A. Modelling the power supply network - Hardness and approximation. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7876 LNCS. Springer Verlag. 2013. p. 62-71. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-38236-9_7
Popa, Alexandru. / Modelling the power supply network - Hardness and approximation. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7876 LNCS Springer Verlag, 2013. pp. 62-71 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{35482c984ff74918880725db0fad6ea3,
title = "Modelling the power supply network - Hardness and approximation",
abstract = "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.",
author = "Alexandru Popa",
year = "2013",
doi = "10.1007/978-3-642-38236-9_7",
language = "English",
isbn = "9783642382352",
volume = "7876 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "62--71",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",

}

TY - GEN

T1 - Modelling the power supply network - Hardness and approximation

AU - Popa, Alexandru

PY - 2013

Y1 - 2013

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

SN - 9783642382352

VL - 7876 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 62

EP - 71

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Verlag

ER -