Some iterative algorithms for the obstacle problems

In this paper we propose some iterative algorithms for the obstacle problems discretized by the finite difference method. We rewrite the obstacle problem to an equivalent complementarity problem. We use the regularization trick to non-smooth absolute function. Then we apply the Newton's method to obtain an iterative algorithm. Some other two algorithms based on this algorithm are derived. Numerical experiments show the effective of the algorithm.     

Two new algorithms for minimal cost flow problems

Two new algorithms for minimal cost flow problems in lower and upper bound capacitated flow networks and an ALGOL-procedure for one of them are given. On the average both methods need less than half of the computing time of the Out-of-Kilter-algorithm.     

Some issues of designing genetic algorithms for traveling salesman problems

This paper demonstrates that a robust genetic algorithm for the traveling salesman problem (TSP) should preserve and add good edges efficiently, and at the same time, maintain the population diversity well. We analyzed the strengths and limitations of several well-known genetic operators for TSPs by the experiments. To evaluate these factors, we propose a new genetic algorithm integrating two genetic operators and a heterogeneous pairing selection. The former can preserve and add good edges efficiently and the later will be able to keep the population diversity. The proposed approach was evaluated on 15 well-known TSPs whose numbers of cities range from 101 to 13509. Experimental results indicated that our approach, somewhat slower, performs very robustly and is very competitive with other approaches in our best surveys. We believe that a genetic algorithm can be a stable approach for TSPs if its operators can preserve and add edges efficiently and it maintains population diversity.     

A review of strongly coupled algorithms for viscous flow problems

Numerical solution of the fluid dynamic equations requires appropriate discretization, quasi-linearization and choice of algorithm. For the latter, approximate factorization procedures put forth by Beam and Warming have played a significant role in the successful completion of this task. The present authors have demonstrated that another element, strong coupling of the discrete equations with the discrete form of the boundary conditions, can play an equally important role. In the present study, the significance of this coupling on the effectiveness of several approximate factorization techniques for the solution of the Navier–Stokes equations is reviewed. It it shown that, even with strong coupling, no single iterative solution algorithm is optimal for the entire spectrum of the flow problems considered.     

Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs

We present two efficient algorithms for the minimum-cost flow problem in which arc costs are piecewise-linear and convex. Our algorithms are based on novel algorithms of Orlin, which were developed for the case of linear arc costs. Our first algorithm uses the Edmonds-Karp scaling technique. Its complexity isO(M logU(m+n logM)) for a network withn vertices,m arcs, M linear cost segments, and an upper boundU on the supplies and the capacities. The second algorithm is a strongly polynomial version of the first, and it uses Tardos's idea of contraction. Its complexity isO(M logM(m+n logM)). Both algorithms improve by a factor of at leastM/m the complexity of directly applying existing algorithms to a transformed network in which arc costs are linear.The final stage of this work was performed while Ron Shamir was a visitor at DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), Rutgers University. Supported in part by National Science Foundation Grant NSF-STC88-09648, and by Air Force Grants AFOSR-89-0512 and AFOSR-90-0008.     

Some symbolic computation algorithms in cosmic dynamics problems

An algorithm for computing fundamental solutions to a linear system of differential equations with a periodic matrix represented by a power series in terms of a small parameter is discussed. An algorithm based on the infinite determinant method for determining boundaries between regions of stability and instability for such a system in the parameter space is also discussed. The corresponding procedures implemented in the Mathematica system and computation results related to the elliptic restricted five-body problem are presented.     

Some remarks on Kalman filters for the multisensor fusion

Multisensor data fusion has found widespread application in industry and commerce. The purpose of data fusion is to produce an improved model or estimate of a system from a set of independent data sources. There are various multisensor data fusion approaches, of which Kalman filtering is one of the most significant. Methods for Kalman filter based data fusion includes measurement fusion and state fusion. This paper gives first a simple a review of both measurement fusion and state fusion, and secondly proposes two new methods of state fusion based on fusion procedures at the prediction and update level, respectively, of the Kalman filter. The theoretical derivation for these algorithms are derived. To illustrate their application, a simple example is performed to evaluate the proposed methods and compare their performance with the conventional state fusion method and measurement fusion methods.     

Solution algorithms for synchronous flow shop problems with two dominating machines

In this paper, we present solution algorithms for synchronous flow shop problems with two dominating machines. In such an environment, jobs have to be moved from one machine to the next by an unpaced synchronous transportation system, which implies that the processing is organized in synchronized cycles. This means that in each cycle the current jobs start at the same time on the corresponding machines and after processing have to wait until the last job is finished. Afterwards, all jobs are moved to the next machine simultaneously. Motivated by a practical application, we investigate the special case of two dominating machines where the processing times of all jobs on these two machines are at least as large as the processing times of all jobs on the other machines and hence always determine the cycle times. After formulating the considered problem as a special vehicle routing problem, we propose mixed integer linear programming formulations and a tabu search algorithm. Finally, we present computational results for randomly generated data and show the efficiency of the approaches.     

Some remarks on Boolean sums

Summary Neciporuk, Lamagna/Savage and Tarjan determined the monotone network complexity of a set of Boolean sums if any two sums have at most one variable in common. Wegener then solved the case that any two sums have at most k variables in common. We extend his methods and results and consider the case that any set of h +1 distinct sums have at most k variables in common. We use our general results to explicitly construct a set of n Boolean sums over n variables whose monotone complexity is of order n ^5/3. The best previously known bound was of order n ^3/2. Related results were obtained independently by Pippenger.This paper was presented at the MFCS 79 Symposium, Olomouc, Sept. 79     

Some remarks on fuzzy graphs

We show that a fuzzy group can be associated with a fuzzy graph in a natural way. Some properties of fuzzy graphs are considered and we introduce the notions of eccentricity and center. Our examples indicate that results from (crisp) graph theory do not always have analogs for fuzzy graphs.     

Some remarks on optimal interpolation

We give in this note very simple new formula for the optimal solution of a generalized interpolation problem which arises in the weighted sensitivity H^∞-minimization for distributed systems. This is based on our work on skew Toeplitz operators from [2].     

Some remarks on estimation algebras

A necessary condition for the finite dimensionality of the estimation algebra of a single input, single output nonlinear system is derived and then extended to cover the multi-input case. A result of Hijab concerning the finite computability of the output function is also generalised.     

Some remarks on recognizable treeseries

Let K be a commutative ring, Σ a finite ranked alphabet and T _Σ the set of trees over Σ. We show that for any recognizable treeseries S:T → K having finite range and any subset A of K, the forest of all trees t ? T _Σ such that the corresponding coefficient (s, t) belongs to Ais recognizable.

In the case _Σ collapses to a monadic alphabet, we refind an analogous result concerning rational wordseries due to Schutzenberger [11] and Sontag [12]. Some applications are also given.     

Some remarks on non-algebraic adherences

We present some properties of non-algebraic adherences of languages, which can be consistently called context-sensitive adherences, because it is proved that in the Chomsky hierarchy of adherences, context-sensitive and recursive-enumerable adherences coincide. Concerning the center-mapping the traversing from algebraic to non-algebraic takes simple recursive to not necessarily recursive-enumerable. Except for the last equality, the Chomsky hierarchy of adherences is proper: R_Adh ? CF_Adh ? CS_Adh = RE_Adh and moreover, it can be refined in the non-algebraic case by considering the McNaughton-Nivat adherences.Regarding the programming context, adherences occur when we consider the set of divergent computations ‘shapes’ of a program or a program scheme. In this respect, the ‘interpretation’ is powerful enough to translate R_Adh to CS_Adh.     

Some remarks on static-feedback linearization for time-varying systems

This work summarizes some results about static state feedback linearization for time-varying systems. Three different necessary and sufficient conditions are stated in this paper. The first condition is the one by [Sluis, W. M. (1993). A necessary condition for dynamic feedback linearization. Systems & Control Letters, 21, 277–283]. The second and the third are the generalizations of known results due respectively to [Aranda-Bricaire, E., Moog, C. H., Pomet, J. B. (1995). A linear algebraic framework for dynamic feedback linearization. IEEE Transactions on Automatic Control, 40, 127–132] and to [Jakubczyk, B., Respondek, W. (1980). On linearization of control systems. Bulletin del’Academie Polonaise des Sciences. Serie des Sciences Mathematiques, 28, 517–522]. The proofs of the second and third conditions are established by showing the equivalence between these three conditions. The results are re-stated in the infinite dimensional geometric approach of [Fliess, M., Lévine J., Martin, P., Rouchon, P. (1999). A Lie–Bäcklund approach to equivalence and flatness of nonlinear systems. IEEE Transactions on Automatic Control, 44(5), 922–937].