Browsing by Author "TSENG, SS"

Now showing 1 - 19 of 19

A HEURISTIC TASK ASSIGNMENT ALGORITHM TO MAXIMIZE RELIABILITY OF A DISTRIBUTED SYSTEM
(1993-09-01)
HWANG, GJ
;
TSENG, SS
;
資訊工程學系
;
Department of Computer Science
Distributed systems potentially provide high reliability owing to the program and data-file redundancy possible. In many applications, high reliability is the major consideration for system design. Some work by Kumar, Hariri, Raghavendra shows that the distribution of programs and data-files can affect the system reliability appreciably, and that redundancy in resources such as computers, programs, and data-files can improve the reliability of distributed system. This paper first formulates a practical application for a reliability-oriented distributed task assignment problem which is NP-hard. Then, to cope with this challenging problem, we propose a greedy algorithm, based upon some heuristics, to find an approximate solution. The simulation shows that, in most cases tested, the algorithm finds suboptimal solutions efficiently; therefore, it is a desirable approach to solve these problems.
A NEW PARALLEL SORTING ALGORITHM BASED UPON MIN-MID-MAX OPERATIONS
(1984-01-01)
TSENG, SS
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
A NEW PARALLEL SORTING ALGORITHM BASED UPON MIN-MID-MAX OPERATIONS
(1984-01-01)
TSENG, SS
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
A PARALLEL ALGORITHM TO SOLVE THE STABLE MARRIAGE PROBLEM
(1984)
TSENG, SS
;
LEE, RCT
;
工學院
;
資訊工程學系
;
College of Engineering
A PARALLEL SORTING SCHEME WHOSE BASIC OPERATION SORTS N ELEMENTS
(1985-12-01)
TSENG, SS
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
AN OPTIMAL PARALLEL PERCEPTRON LEARNING ALGORITHM FOR A LARGE TRAINING SET
(1994-03-01)
HONG, TP
;
TSENG, SS
;
資訊工程學系
;
Department of Computer Science
In [2], a parallel perceptron learning algorithm on the single-channel broadcast communication model was proposed to speed up the learning of weights of perceptrons [3]. The results in [2] showed that given n training examples, the average speedup is 1.48*n0.91/log n by n processors. Here, we explain how the parallelization may be modified so that it is applicable to any number of processors. Both analytical and experimental results show that the average speedup can reach nearly O(r) by r processors if r is much less than n.
ARRANGING APPROPRIATE TRAINING ORDER IN NOISY DOMAINS
(1994)
HSU, YT
;
TSENG, SS
;
HONG, TP
;
資訊工程學系
;
Department of Computer Science
GENERATING THE BEST K-SEQUENCES IN RELOCATION PROBLEMS
(1993-08-27)
LIN, BMT
;
TSENG, SS
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
There is a set J of h jobs to be processed. For every i, job J(i) demands n(i) units of resources and returns a(i) units after completion. The problem is to find the best K schedules whose resource requirements are minimum among all h! ones. In this paper, we present some important structural properties and then propose an O(h log h + hK log K) time algorithm, which runs in polynomial time if K is fixed.
LEARNING CONCEPTS IN PARALLEL BASED UPON THE STRATEGY OF VERSION SPACE
(1994-12-01)
HONG, TP
;
TSENG, SS
;
資訊工程學系
;
Department of Computer Science
In this paper, we have attempted to apply the technique of parallel processing to concept learning. A parallel version-space learning algorithm based upon the principle of divide-and-conquer is proposed. Its time complexity is analyzed to be O(k log(2) n) with n processors, where n is the number of given training instances and k is a coefficient depending on application domains. For a bounded number of processors in the real situations, a modified parallel learning algorithm is then proposed. Experimental results are then performed on a real learning problem, showing our parallel learning algorithm works and being quite consistent with results of theoretic analysis. We have finally concluded that when the number of training instances is large, it is worth learning in parallel because of its faster execution.
MAXIMIZING THE NUMBER OF SPANNING-TREES OF NETWORKS BASED ON CYCLE BASIS REPRESENTATION
(1989)
TSENG, SS
;
WANG, LR
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
MAXIMIZING THE NUMBER OF SPANNING-TREES OF NETWORKS BASED ON CYCLE BASIS REPRESENTATION
(1989-01-01)
TSENG, SS
;
WANG, LR
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
MAXIMIZING THE NUMBER OF SPANNING-TREES OF NETWORKS BASED ON CYCLE BASIS REPRESENTATION
(1989)
TSENG, SS
;
WANG, LR
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
ON THE INVARIANCE OF MALE OPTIMAL STABLE MATCHING
(1990)
KUO, RT
;
TSENG, SS
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
The stable matching problem is that of matching two sets of agents in such a manner that no two unmatched agents prefer each other to their actual partners under the matching. In this paper, we present a set of sufficient conditions on the preference lists of any given stable matching instance, under which the optimality of the original male optimal stable matching is still preserved.
PARALLEL PERCEPTRON LEARNING ON A SINGLE-CHANNEL BROADCAST COMMUNICATION MODEL
(1992-02-01)
HONG, TP
;
TSENG, SS
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
A parallel perceptron learning algorithm based upon a single-channel broadcast communication model has been proposed here. Since it can process training instances in parallel, instead of one by one in the conventional algorithm, large speedup can be expected. Theoretical analysis shows: with n processors, the average speedup ranges from O(log n) to O(n) under a variety ot assumptions (where n is the number of training instances). Experimental results further show the actual average speedup is approximately being O(n0.91/log n). Extensions to a bounded number of processors and to the backpropagation learning have also been discussed.
RELOCATION PROBLEMS OF MAXIMIZING NEW CAPACITIES UNDER A COMMON DUE DATE
(1992-09-01)
LIN, MT
;
TSENG, SS
;
資訊工程學系
;
Department of Computer Science
Given a set of h buildings to be torn down and rebuilt, each building B(i) demands n(i) units of temporary vacancies for reconstruction (i.e. the reconstruction of B(i) can be started only if there are at least n(i) temporary vacancies available) and returns a(i) units of vacancies when it is rebuilt. The reconstruction time of each building is assumed to be unitary. Under the initial provision of V0 units of vacancies and a specified due date d, SIGMA(Bi is-an-element-of S)a(i), where S is a feasible sequence such that absolute value of S less-than-or-equal-to d, is the objective function to be maximized. We show that the problem is NP-complete. Based on a dominance heuristics, we further propose a branch-and-bound algorithm. Experimental results are included to elucidate the effectiveness of our algorithm. Two further restricted versions are also polynomially solvable.
SOME RESULTS OF THE RELOCATION PROBLEMS WITH PROCESSING TIMES AND DEADLINES
(1991)
LIN, MT
;
TSENG, SS
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
STABLE MATCHING WITH SPECIAL PREFERENCE PATTERNS
(1991)
KUO, RT
;
TSENG, SS
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
THE AVERAGE PERFORMANCE OF A PARALLEL STABLE MARRIAGE ALGORITHM
(1989)
TSENG, SS
;
資訊工程學系
;
Department of Computer Science
THE NECESSARY AND SUFFICIENT CONDITION FOR THE WORST-CASE MALE OPTIMAL STABLE MATCHING
(1990-05-07)
KUO, RT
;
TSENG, SS
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering