( , )k s is the propositional satisfiable problem restricted to instances where each clause has exactly k distinct literals and every variable occurs at most s times. It is known that there exits an exponential is already NP- function f such that for complete ( are only known 3 k = , and it(cid:146)s open whether k = and for is computable. The best known lower and upper bounds 3 Ω − ≈ on ( ) , respectively. In this paper, analogous to the , where f k are randomized algorithm for finding two coloring of k − uniform hypergraph, we first present a similar randomize algorithm for outputting an assignment for a given formula. Based on it and by probabilistic

In this paper an interesting property of the restarted FOM algorithm for solving large nonsymmetric linear systems is presented and studied. By establishing a relationship between the convergence of its residual vectors and the convergence of Ritz values in the Arnoldi procedure, it is shown that some important information of previous FOM(m) cycles may be saved by the iteration approximates at the time of restarting, with which the FOM(m) cycles can complement one another harmoniously in reducing the iteration residual. Based on the study of FOM(m), two polynomial preconditioning techniques are proposed; one is for solving nonsymmetric linear systems and another is for forming an effective starting vector in the restarted Arnoldi method for solving nonsymmetric eigenvalue problems.

In this paper, we gave a fairing algorithm for parametric quintic spline curves. This new algorithm gives a clear modification to the bad point's position, tangent vector, and second tangent vector. We also proved that this algorithm is of energy optimization.

Since their introduction in a classic paper by Rudin, Osher and Fetemi [1], total variation minimizing models have become one of the most popular and successful methodology for image restoration. More recently, there has been a resurgence of interest and exciting new developments, some extending the applicabilities to inpainting, blind deconvolution and vector-valued images, while others offer improvements in better preservation of contrast, geometry and textures, in ameliorating the staircasing effect, and in exploiting the multiscale nature of the models. In addition, new computational methods have been proposed with improved computational speed and robustness. In this paper, a predictor-Corrector techniques are pointed out and applied in to the total variation-based image denoising.The numerical experiments shows the improvement are fairly valid.

Time Petri Nets (TPNs) are a popular Petri net model for specification and verification of real-time systems. A widely applied method for analyzing Petri nets is component-level reduction analysis. The existing technique for component-level reduction analysis transforms a TPN component to a constant size of simple one while maintains the net external observable timing properties, but it neglects the internal properties of component such as synchronization, conflict and concurrency. Based on Delay Time Petri Net (DTPN), the paper transforms a TPN component to DTPN model in order to preserve such properties as synchronization, conflict and concurrency during the reduction. For the sake of analyzing the DTPN model, the paper proposes new schedule analysis method. Finally, reduction rules based on DTPN are applied to the TPN model analysis in the command and control (C2) system.

This paper presents an efficient and sufficient algorithm to approximate general interpolating Spline curve which goes through the given set of design-data points by using asymptotic iterative B-spline curves. Firstly, the given set is considered as the control points of a B-spline, to create the initial approximate curve, then the iterative grade is built based on the error between the initial approximate curve and given set, it is used to generate an iterative function sequence to approximate the interpolating function of the cover. New algorithms and approaches are successfully employed to create realistic and flexible geometry models for the centerline of yarns in woven fabrics. The algorithm described on this paper will be generalized to wide range for general 2D and 3D geometry and computer graphics with regard to curves and surfaces, especially for complex geometrical models on CAD and CAM.

This paper gives a new inpainting model based on curve and horizontal line evolution. By connecting the level lines that reach the edges and let the connected lines have minimum curvature, the model can finish the task successfully. What’s more, the algorithm has no request on the topology of the inpainting area and can deal with all areas simultaneously.

The bin packing problem based on item sequencing is defined as follows: given a set of sequenced items of different sizes, how should one pack them all into bins of different capacity, in order to make the utility ratio of bin capacity as higher as possible? In this paper, next fit algorithm, a heuristic method for bin packing problem, is introduced into simple genetic algorithm, and a hybrid genetic algorithm is proposed for solving bin-packing problem based on item sequencing. In the hybrid genetic algorithm, the idea of simple genetic algorithm is used to search the solution of the bins sequence, and the idea of next fit algorithm is used to pack the sequenced items into the bins sequence obtained. Finally, the effectiveness of the hybrid genetic algorithm is convinced through computational results of an example.