The Computational Complexity of the Minimum Weight Processor Assignment Problem

Haitze J. Broersma, Daniël Paulusma, Gerardus Johannes Maria Smit, F. Vlaardingerbroek, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
37 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 languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers
EditorsJuraj Hromkovic, Manfred Nagl, Bernhard Westfechtel
Place of PublicationBerlin
PublisherSpringer
Pages189-200
Number of pages12
ISBN (Print)3-540-24132-9
DOIs
Publication statusPublished - Jun 2004
Event30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004 - Bad Honnef, Germany
Duration: 21 Jun 200423 Jun 2004
Conference number: 30

Publication series

NameLecture notes in computer science
Volume3353
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004
Abbreviated titleWG
CountryGermany
CityBad Honnef
Period21/06/0423/06/04

Fingerprint

Assignment Problem
Computational Complexity
Graph in graph theory
Maximum Degree
Multiway Cut
Minimum Cut
Multimedia Systems
Generalise
Energy Efficient
Bipartite Graph
Polynomial-time Algorithm
Covering
Efficient Algorithms
NP-complete problem
Optimization Problem
Vertex of a graph

Keywords

  • CAES-EEA: Efficient Embedded Architectures
  • EWI-1499
  • IR-48397
  • METIS-219813

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). Berlin: Springer. https://doi.org/10.1007/978-3-540-30559-0_16, https://doi.org/10.1007/b104584
Broersma, Haitze J. ; Paulusma, Daniël ; Smit, Gerardus Johannes Maria ; Vlaardingerbroek, F. ; Woeginger, Gerhard. / 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, EWI-1499, IR-48397, METIS-219813",
author = "Broersma, {Haitze J.} and Dani{\"e}l Paulusma and Smit, {Gerardus Johannes Maria} and F. Vlaardingerbroek and Gerhard Woeginger",
year = "2004",
month = "6",
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",

}

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, https://doi.org/10.1007/b104584

The Computational Complexity of the Minimum Weight Processor Assignment Problem. / Broersma, Haitze J.; Paulusma, Daniël; Smit, Gerardus Johannes Maria; Vlaardingerbroek, F.; Woeginger, Gerhard.

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 proceedingConference contributionAcademicpeer-review

TY - GEN

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

AU - Broersma, Haitze J.

AU - Paulusma, Daniël

AU - Smit, Gerardus Johannes Maria

AU - Vlaardingerbroek, F.

AU - Woeginger, Gerhard

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

KW - EWI-1499

KW - IR-48397

KW - METIS-219813

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

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). https://doi.org/10.1007/978-3-540-30559-0_16, https://doi.org/10.1007/b104584