𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Alignment and Distribution Is Not (Always) NP-Hard

✍ Scribed by Vincent Boudet; Fabrice Rastello; Yves Robert

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
293 KB
Volume
61
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, an efficient algorithm to simultaneously implement array alignment and dataΓ‚computation distribution is introduced and evaluated. We revisit previous work of J. Li and M. Chen (in ``Frontiers 90: The Third Symposium on the Frontiers of Massively Parallel Computation, '' pp. 424 433, College Park MD, Oct. 1990; and J. Parallel Distrib. Comput. 13 (1991), 213 221), and we show that their alignment step should not be conducted without preserving the potential parallelism. In other words, the optimal alignment may well sequentialize computations, whatever the distribution afterward. We provide an efficient algorithm that handles alignment and dataΓ‚computation distribution simultaneously. The good news is that several important instances of the whole alignment Γ‚distribution problem have polynomial complexity, while alignment itself is NP-complete (Li and Chen, 1990).

πŸ“œ SIMILAR VOLUMES

Checking identities is computationally i
Checking identities is computationally intractable NP-hard and therefore human provers will always be needed
✍ Vladik Kreinovich; Chin-Wang Tao πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 97 KB

A 1990 article in the American Mathematical Monthly has shown that most combinatorial identities of the type described in Monthly problems can be solved by known identity checking algorithms. A natural question arises: are these algorithms always feasible or can the number of computational steps be

All that is iron-ink is not always iron-
All that is iron-ink is not always iron-gall!
✍ Marina Bicchieri; Michela Monti; Giovanna Piantanida; Armida Sodo πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 194 KB
Early stent occlusion is not always caus
Early stent occlusion is not always caused by thrombosis
✍ Heijer, Peter Den ;van Dijk, RenΓ© B. ;Twisk, S. PΓ© M. ;Lie, Kong I. πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 454 KB

Early occlusion of intracoronary stents has been exclusively attributed to thrombosis. Using intracoronary angioscopy, we have found 2 patients in whom this common and serious complication of coronary stenting was caused by obstructive intima dissection rather than thrombosis.