NP-hard Problem (np-hard + problem)

Distribution by Scientific Domains

Selected Abstracts

A static mapping heuristics to map parallel applications to heterogeneous computing systems

Ranieri Baraglia
Abstract In order to minimize the execution time of a parallel application running on a heterogeneously distributed computing system, an appropriate mapping scheme is needed to allocate the application tasks to the processors. The general problem of mapping tasks to machines is a well-known NP-hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper we propose a static graph-based mapping algorithm, called Heterogeneous Multi-phase Mapping (HMM), which permits suboptimal mapping of a parallel application onto a heterogeneous computing distributed system by using a local search technique together with a tabu search meta-heuristic. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application, and considering an affinity parameter, that identifies which machine in the heterogeneous computing system is most suitable to execute a task. We compare HMM with some leading techniques and with an exhaustive mapping algorithm. We also give an example of mapping of two real applications using HMM. Experimental results show that HMM performs well demonstrating the applicability of our approach. Copyright 2005 John Wiley & Sons, Ltd. [source]

Solving resource constrained multiple project scheduling problems by random key-based genetic algorithm

Ikutaro Okada
Abstract In this paper, we propose a hybrid genetic algorithm with fuzzy logic controller (flc-rkGA) to solve the resource-constrained multiple project scheduling problem (rc-mPSP) which is well known as an NP-hard problem and the objective in this paper is to minimize total complete time in the project. It is difficult to treat the rc-mPSP problems with traditional optimization techniques. The new approach proposed is based on the hybrid genetic algorithm (flc-rkGA) with fuzzy logic controller (FLC) and random-key encoding. For these rc-mPSP problems, we demonstrate that the proposed flc-rkGA to solve the rc-mPSP problem yields better results than several heuristic genetic algorithms presented in the computation result. 2009 Wiley Periodicals, Inc. Electron Comm Jpn, 92(8): 25,35, 2009; Published online in Wiley InterScience ( DOI 10.1002/ecj.10101 [source]

A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

Bo Gao
Abstract In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub-graph. However, finding the minimum connected dominating set (MCDS) is a well-known NP-hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one-hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright 2005 John Wiley & Sons, Ltd. [source]

State-space analysis for an experimental drive-by-wire vehicle

M. Halton
Abstract This paper considers the application of the skewed structured singular value to the robust stability of systems subject to strictly real parametric uncertainty. Three state-space formulations that counteract the discontinuous nature of this problem are detailed. It is shown that the calculation of the supremum of the structured singular value over a frequency range using these formulations transforms into a single skewed structured singular value calculation. Similar to the structured singular value, the exact calculation of the skewed structured singular value is an NP-hard problem. In this work, two efficient algorithms that determine upper and lower bounds on the skewed structured singular value are presented. These algorithms are critically assessed using a series of robustness analysis tests on a safety-critical experimental drive-by-wire vehicle. Copyright 2008 John Wiley & Sons, Ltd. [source]

Minimizing SONET Add-Drop Multiplexers in optical UPSR networks using the minimum number of wavelengths

Yong Wang
Abstract In SONET/WDM optical networks, a high-speed wavelength channel is usually shared by multiplexed low-rate network traffic demands. The multiplexing is known as traffic grooming and carried out by SONET Add-Drop Multiplexers (SADM). The maximum number of low-rate traffic demands that can be multiplexed into one wavelength is called the grooming factor. Because SADMs are expensive network devices, a key optimization problem in optical network design is to groom a given set of low-rate traffic demands such that the number of required SADMs is minimized. This optimization problem is challenging and NP-hard even for Unidirectional Path-Switched Ring networks with unitary duplex traffic demands. In this article, we propose two linear-time approximation algorithms for this NP-hard problem based on a novel graph partitioning approach. Both algorithms achieve better worst case performance than the previous algorithms. We also show that the upper bounds obtained by our algorithms are very close to the lower bounds for some instances. In addition, both of our algorithms use the minimum number of wavelengths, which are precious resources as well in optical networks. 2008 Wiley Periodicals, Inc. NETWORKS, 2009 [source]

Improved controllability test for dependent siphons in S3PR based on elementary siphons

Daniel Y. Chao
Abstract When siphons in a flexible manufacturing system (FMS) modeled by an ordinary Petri net (OPN) become unmarked, the net gets deadlocked. To prevent deadlocks, some control places and related arcs are added to strict minimal siphons (SMS) so that no siphon can be emptied. For large systems, it is infeasible to add a monitor to every SMS since the number of SMS or control elements grows exponentially with respect to the size of a Petri net. To tackle this problem, Li and Zhou propose to add control nodes and arcs for only elementary siphons. The rest of siphons, called dependent ones, may be controlled by adjusting control depth variables of elementary siphons associated with a dependent siphon after the failure of two tests. First, they test a Marking Linear Inequality (MLI); if it fails, then they perform a Linear Integer Programming (LIP) test which is an NP-hard problem. This implies that the MLI test is only sufficient, but not necessary. We propose a sufficient and necessary test for adjusting control depth variables in an S3PR to avoid the sufficient-only time-consuming linear integer programming (LIP) test (NP-complete problem) required previously for some cases. We theoretically prove the following: i) no need for LIP test for Type II siphons; and ii) Type I strongly n-dependent (n>2) siphons being always marked. As a result, the total time complexity to check controllability of all strongly dependent siphons is no longer exponential but reduced to linear if all siphons are of Type I. The total time complexity is O(|,E||,D|) (order of the product of total number of elementary siphons and total number of dependent siphons) if all siphons are of Type II. A well-known S3PR example has been illustrated to show the advantages. Copyright 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society [source]

An Explicit Solution of a Generalized Optimum Requirement Spanning Tree Problem With a Property Related to Monge

Tsutomu Anazawa
The paper considers a generalization of the optimum requirement spanning tree problem (ORST problem) first studied by Hu in 1974. Originally, ORST was regarded as a communication network of tree type with the minimum average cost, and it is obtained by the well-known Gomory,Hu algorithm when the degrees of vertices are not restricted. The ORST problem is generalized by (i) generalizing the objective function and (ii) imposing maximum degree constraints. The generalized ORST problem includes some practical problems, one of which is proposed in this paper, but is not efficiently solvable in general. However, I show that a particular tree (which is obtained by a sort of greedy algorithm but is explicitly definable) is a solution of the generalized problem when a certain practical condition is satisfied. The condition is closely related to the Monge property, which is originally discussed in the Hitchcock transportation problem, and is known to make some NP-hard problems efficiently solvable. [source]