The Computational Complexity of the Minimum Weight Processor Assignment Problem

H.J. Broersma; D. Paulusma; G.J.M. Smit; F. Vlaardingerbroek; G. Woeginger

doi:10.1007/978-3-540-30559-0_16

The Computational Complexity of the Minimum Weight Processor Assignment Problem

H.J. Broersma, D. Paulusma, G.J.M. Smit, F. Vlaardingerbroek, G. Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

71 Downloads (Pure)

Abstract

In portable multimedia systems a number of communicating tasks has to be performed on a set of heterogeneous processors in an energy-efficient way. We model this problem as a graph optimization problem, which we call the minimum weight processor assignment problem. We show that our setting generalizes several problems known in literature, including minimum multiway cut, graph k-colorability, and minimum (generalized) vertex covering. We show that the minimum weight processor assignment problem is NP-hard, even when restricted to instances where the (process) graph is a bipartite graph with maximum degree at most 3, or with only two processors, or with arbitrarily small weight differences, or with only two different edge weights. For graphs with maximum degree at most 2 (or in fact the larger class of degree-2-contractible graphs) we give a polynomial time algorithm. Finally we generalize this algorithm into an exact (but not efficient) algorithm for general graphs.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers
Editors	Juraj Hromkovic, Manfred Nagl, Bernhard Westfechtel
Place of Publication	Berlin
Publisher	Springer
Pages	189-200
Number of pages	12
ISBN (Print)	3-540-24132-9
DOIs	https://doi.org/10.1007/978-3-540-30559-0_16
Publication status	Published - Jun 2004
Event	30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004 - Bad Honnef, Germany Duration: 21 Jun 2004 → 23 Jun 2004 Conference number: 30

Publication series

Name	Lecture notes in computer science
Volume	3353
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004
Abbreviated title	WG
Country/Territory	Germany
City	Bad Honnef
Period	21/06/04 → 23/06/04

Keywords

CAES-EEA: Efficient Embedded Architectures

Access to Document

10.1007/978-3-540-30559-0_16

Broersma2004computationalAccepted author version, 153 KB

Cite this

Broersma, H. J., Paulusma, D., Smit, G. J. M., Vlaardingerbroek, F., & Woeginger, G. (2004). The Computational Complexity of the Minimum Weight Processor Assignment Problem. In J. Hromkovic, M. Nagl, & B. Westfechtel (Eds.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers (pp. 189-200). (Lecture notes in computer science; Vol. 3353). Springer. https://doi.org/10.1007/978-3-540-30559-0_16

Broersma, H.J. ; Paulusma, D. ; Smit, G.J.M. et al. / The Computational Complexity of the Minimum Weight Processor Assignment Problem. Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers. editor / Juraj Hromkovic ; Manfred Nagl ; Bernhard Westfechtel. Berlin : Springer, 2004. pp. 189-200 (Lecture notes in computer science).

@inproceedings{d260b28b351d4da48ed0055c6fa51df6,

title = "The Computational Complexity of the Minimum Weight Processor Assignment Problem",

abstract = "In portable multimedia systems a number of communicating tasks has to be performed on a set of heterogeneous processors in an energy-efficient way. We model this problem as a graph optimization problem, which we call the minimum weight processor assignment problem. We show that our setting generalizes several problems known in literature, including minimum multiway cut, graph k-colorability, and minimum (generalized) vertex covering. We show that the minimum weight processor assignment problem is NP-hard, even when restricted to instances where the (process) graph is a bipartite graph with maximum degree at most 3, or with only two processors, or with arbitrarily small weight differences, or with only two different edge weights. For graphs with maximum degree at most 2 (or in fact the larger class of degree-2-contractible graphs) we give a polynomial time algorithm. Finally we generalize this algorithm into an exact (but not efficient) algorithm for general graphs.",

keywords = "CAES-EEA: Efficient Embedded Architectures",

author = "H.J. Broersma and D. Paulusma and G.J.M. Smit and F. Vlaardingerbroek and G. Woeginger",

year = "2004",

month = jun,

doi = "10.1007/978-3-540-30559-0_16",

language = "English",

isbn = "3-540-24132-9",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "189--200",

editor = "Juraj Hromkovic and Manfred Nagl and Bernhard Westfechtel",

booktitle = "Graph-Theoretic Concepts in Computer Science",

note = "30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, WG ; Conference date: 21-06-2004 Through 23-06-2004",

}

Broersma, HJ, Paulusma, D, Smit, GJM, Vlaardingerbroek, F & Woeginger, G 2004, The Computational Complexity of the Minimum Weight Processor Assignment Problem. in J Hromkovic, M Nagl & B Westfechtel (eds), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers. Lecture notes in computer science, vol. 3353, Springer, Berlin, pp. 189-200, 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, Bad Honnef, Germany, 21/06/04. https://doi.org/10.1007/978-3-540-30559-0_16

The Computational Complexity of the Minimum Weight Processor Assignment Problem. / Broersma, H.J.; Paulusma, D.; Smit, G.J.M. et al.
Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers. ed. / Juraj Hromkovic; Manfred Nagl; Bernhard Westfechtel. Berlin: Springer, 2004. p. 189-200 (Lecture notes in computer science; Vol. 3353).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The Computational Complexity of the Minimum Weight Processor Assignment Problem

AU - Broersma, H.J.

AU - Paulusma, D.

AU - Smit, G.J.M.

AU - Vlaardingerbroek, F.

AU - Woeginger, G.

N1 - Conference code: 30

PY - 2004/6

Y1 - 2004/6

N2 - In portable multimedia systems a number of communicating tasks has to be performed on a set of heterogeneous processors in an energy-efficient way. We model this problem as a graph optimization problem, which we call the minimum weight processor assignment problem. We show that our setting generalizes several problems known in literature, including minimum multiway cut, graph k-colorability, and minimum (generalized) vertex covering. We show that the minimum weight processor assignment problem is NP-hard, even when restricted to instances where the (process) graph is a bipartite graph with maximum degree at most 3, or with only two processors, or with arbitrarily small weight differences, or with only two different edge weights. For graphs with maximum degree at most 2 (or in fact the larger class of degree-2-contractible graphs) we give a polynomial time algorithm. Finally we generalize this algorithm into an exact (but not efficient) algorithm for general graphs.

AB - In portable multimedia systems a number of communicating tasks has to be performed on a set of heterogeneous processors in an energy-efficient way. We model this problem as a graph optimization problem, which we call the minimum weight processor assignment problem. We show that our setting generalizes several problems known in literature, including minimum multiway cut, graph k-colorability, and minimum (generalized) vertex covering. We show that the minimum weight processor assignment problem is NP-hard, even when restricted to instances where the (process) graph is a bipartite graph with maximum degree at most 3, or with only two processors, or with arbitrarily small weight differences, or with only two different edge weights. For graphs with maximum degree at most 2 (or in fact the larger class of degree-2-contractible graphs) we give a polynomial time algorithm. Finally we generalize this algorithm into an exact (but not efficient) algorithm for general graphs.

KW - CAES-EEA: Efficient Embedded Architectures

U2 - 10.1007/978-3-540-30559-0_16

DO - 10.1007/978-3-540-30559-0_16

M3 - Conference contribution

SN - 3-540-24132-9

T3 - Lecture notes in computer science

SP - 189

EP - 200

BT - Graph-Theoretic Concepts in Computer Science

A2 - Hromkovic, Juraj

A2 - Nagl, Manfred

A2 - Westfechtel, Bernhard

PB - Springer

CY - Berlin

T2 - 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004

Y2 - 21 June 2004 through 23 June 2004

ER -

Broersma HJ, Paulusma D, Smit GJM, Vlaardingerbroek F, Woeginger G. The Computational Complexity of the Minimum Weight Processor Assignment Problem. In Hromkovic J, Nagl M, Westfechtel B, editors, Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers. Berlin: Springer. 2004. p. 189-200. (Lecture notes in computer science). doi: 10.1007/978-3-540-30559-0_16

The Computational Complexity of the Minimum Weight Processor Assignment Problem

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this