✦ LIBER ✦

The complexity of multiple wordlength assignment

✍ Scribed by G.A. Constantinides; G.J. Woeginger

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 331 KB
Volume: 15
Category: Article
ISSN: 0893-9659
DOI: 10.1016/s0893-9659(01)00107-0

No coin nor oath required. For personal study only.

✦ Synopsis

This note discusses the multiple wordlength assignment problem for the design of custom digital signal processing (DSP) parallel processors. It is demonstrated that this assignment problem is NP-hard.

📜 SIMILAR VOLUMES

On the Complexity of Optimal Hotlink Ass

On the Complexity of Optimal Hotlink Assignment

✍ Tobias Jacobs 📂 Article 📅 2011 🏛 Springer 🌐 English ⚖ 772 KB

The computational complexity of bilevel

The computational complexity of bilevel assignment problems

✍ Elisabeth Gassner; Bettina Klinz 📂 Article 📅 2009 🏛 Springer 🌐 English ⚖ 282 KB

Complexity of a 3-dimensional assignment

Complexity of a 3-dimensional assignment problem

✍ A.M. Frieze 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 305 KB

The complexity of a multiprocessor task

The complexity of a multiprocessor task assignment problem without deadlines

✍ Ronald D. Dutton; Robert C. Brigham 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 301 KB

Random assignment of multiple indivisibl

Random assignment of multiple indivisible objects

✍ Fuhito Kojima 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 458 KB

Complexity of the min–max and min–max re

Complexity of the min–max and min–max regret assignment problems

✍ Hassene Aissi; Cristina Bazgan; Daniel Vanderpooten 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 179 KB

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment pro