Volume 20, 2001, No. 4

A Rule-Based Scalar Tuning Fuzzy Control System

Hsuan-Ming FENG, Wen-Hsing KAO   Abstract A rule-based scalar tuning fuzzy control system is proposed in this paper. A fuzzy controller with three scalar factors is considered to directly control the plant, and a scalar tuning mechanism through a fuzzy inference method is used to dynamically generate appropriate scalar factors for the fuzzy controller at each sampling time. A state evaluator is used to estimate a critic score to indicate the current state of the system, and to provide this score to a parameter modifier to create a modifiable value. A scalar making mechanism is proposed such that the rule-based fuzzy control system has the powerful ability to automatically select the consequent parameters in the scalar tuning mechanism such that the controlled system has a better performance. Finally, the inverted pendulum control problem is used to illustrate the effectiveness of the rule-based tuning control scheme.

 

A Minimal Reduction Approach for the Collapsing Knapsack Problem

Wu JIGANG, Lei YUNFEI, Heiko SCHRÖDER   Abstract Within the research releated to NP-hard problems major emphasis is now placed on the attempt to solve as large problems as possible within a given time. This paper follows this approach in relation to Collapsing Knapsack Problem (CKP). The collapsing knapsack problem is a generalized 0-1 knapsack problem where the capacity of the knapsack is a non-increasing function of the number of items included. We generalize a well known reduction approach to a standard knapsack problem (SKP), and propose a new reduction approach which leads to a significantly smaller capacity and to smaller coefficients of the resulting SKP. With the new reduction approach, the capacity of the resulting SKP is reduced from 3nA to 2(n+2)b(1) with b(1) <= A, where A is the total weight of all the items. The MINKNAP algorithm, proposed by Pisinger (1997) to solve SKP, is directly improved because of the moderate coefficients of the resulting SKP. The pseudo-polynomial solution time to solve CKP is reduced from O(n^3a') to O(n^2b(1)), where a' is the upper bound of the weights.

 

Data Flow Computing Model: Application for Parallel Computer Systems Diagnosis

Liberios VOKOROKOS   Abstract This paper concerns the issue of recovery of a fault-tolerant parallel system without spares. A fault-tolerant system must be able to proceed its operation despite the occurrence of faults. In such a system recovery can be considered as a support function that retains the fault tolerant features of the system. We present here a data flow model that comprises functional blocks and activating signs in accordance with message flow in a parallel system. A fault in a system occurs according to the continuity of message routing providing the communication between processes and enables the fault diagnosis. Messages in a system are generated and processed in message routing.

 

All-to-All Scatter in de Bruijn and Kautz Networks

Petr SALINGER, Pavel TVRDÍK   Abstract In this paper, we describe algorithms for all-to-all scatter in all-port de Bruijn and Kautz networks. The algorithms are memory-optimal and asymptotically time- and transmission-optimal. We give algorithms for the noncombining model and their modifications for the limited combining model. The algorithms achieve asymptotic optimality on both store-and-forward and wormhole switched networks.

 

On the Approximation Ratio of the Group-Merge Algorithm for the Shortest Common Superstring Problem

Dirk BONGARTZ   Abstract The shortest common superstring problem (SCS) is one of the fundamental optimization problems in the area of data compression and DNA sequencing. The SCS is known to be APX-hard. This paper focuses on the analysis of the approximation ratio of two greedy-based approximation algorithms for it, namely the naive Greedy algorithm and the Group-Merge algorithm. The main results of this paper are: I. We disprove the claim that the input instances of Jiang and Li {JL96} show that the Group-Merge algorithm does not provide any constant approximation for the SCS. We even prove that the Group-Merge algorithm always finds optimal solutions for these instances (except in one trivial case). II. We show that the Greedy algorithm and the Group-Merge algorithm are incomparable according to the approximation ratio.

 

Volume 20, 2001, No. 4