Search

We study the decomposition of multivariate polynomials as sums of powers of linear forms. As one of our main results, we give a randomized algorithm for the following problem: given a homogeneous polynomial f (x 1 , ... , x n) of degree 3, decide whether it can be written as a sum of cubes of linearly independent linear forms with complex coefficients. Compared to previous algorithms for the same problem, the two main novel features of this algorithm are: (i) It is an algebraic algorithm, i.e., it performs only arithmetic operations and equality tests on the coefficients of the input polynomial f. In particular, it does not make any appeal to polynomial factorization. (ii) For f ∈ Q [ x 1 , ... , x n ] , the algorithm runs in polynomial time when implemented in the bit model of computation. The algorithm relies on methods from linear and multilinear algebra (symmetric tensor decomposition by simultaneous diagonalization). We also give a version of our algorithm for decomposition over the field of real numbers. In this case, the algorithm performs arithmetic operations and comparisons on the input coefficients. Finally we give several related derandomization results on black box polynomial identity testing, the minimization of the number of variables in a polynomial, the computation of Lie algebras and factorization into products of linear forms. [ABSTRACT FROM AUTHOR]

In this paper, for a real number ϵ ∈ [ 0 , 1 ] , we put forward the notion of fuzzy ϵ -approximate regular languages and study their properties, especially the Pumping lemma in the context of this kind of languages. By comparing sets of fuzzy ϵ -approximate regular languages under the order of set inclusion, we get an (infinite) hierarchy of fuzzy languages, the smallest is the set of fuzzy regular languages and the biggest is the set of fuzzy languages, and the sets of ϵ -approximate regular languages are different for different ϵ ∈ (0 , 1 2). We also investigate whether operations closed in the set of fuzzy regular languages are still closed in the set of fuzzy ϵ -approximate regular languages. Furthermore, for a fuzzy ϵ -approximate regular language f , ϵ -approximate equivalence relations for f are characterized in order to construct deterministic fuzzy automata ϵ -accepting f. If a fuzzy ϵ -approximate regular language f is also a fuzzy regular language and accepted by a given accessible deterministic fuzzy automaton A , then we give a polynomial-time algorithm to construct at least one minimal deterministic fuzzy automaton ϵ -accepting f by means of A. Finally, we point out that the number of states of minimal deterministic fuzzy automata ϵ -accepting a fuzzy regular language is smaller than or equal to that of minimal deterministic fuzzy automata accepting this language. [ABSTRACT FROM AUTHOR]

The sequential stabilizing spline (SSS) algorithm is a remarkable algorithm for identifying linear dynamical systems. It can guarantee the stability of an estimated model by polishing the maximum modulus roots of an equation. Therefore, the root structure of an equation plays an important role in the SSS algorithm. Although the traditional power iterative method can be applied to approximate the extremal eigenvalues which have the largest modulus, it has two limitations: (1) the extremal eigenvalues must be real numbers, and (2) the structures of the extremal eigenvalues should be known a priori. In this paper, a novel power iterative method is proposed to approximate the extremal eigenvalues. Compared with the traditional power iterative method, the method in this paper can (1) determine the types of the extremal eigenvalues without prior knowledge of the matrix; (2) approximate the true values of the extremal eigenvalues regardless of their type; (3) become a worthy addition to SSS algorithm and gradient descent algorithm. Simulation examples demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed b and can change speed or direction at any time. The two robots can communicate with each other at any distance and at any time. The task is completed when the last robot arrives at the exit and evacuates. We study time-energy tradeoffs for the above evacuation problem. The evacuation time is the time it takes the last robot to reach the exit. The energy it takes for a robot to travel a distance x at speed s is measured as x s 2. The total and makespan evacuation energies are respectively the sum and maximum of the energy consumption of the two robots while executing the evacuation algorithm. Assuming that the maximum speed is b , and the evacuation time is at most cd , where d is the distance of the exit from the origin and c is some positive real number, we study the problem of minimizing the total energy consumption of the robots. We prove that the problem is solvable only for b c ≥ 3. For the case b c = 3 , we give an optimal algorithm, and give upper bounds on the energy for the case b c > 3. We also consider the problem of minimizing the evacuation time when the available energy is bounded by Δ. Surprisingly, when Δ is a constant, independent of the distance d of the exit from the origin, we prove that evacuation is possible in time O (d 3 / 2 log ⁡ d) , and this is optimal up to a logarithmic factor. When Δ is linear in d , we give upper bounds on the evacuation time. [ABSTRACT FROM AUTHOR]

• Analysis of non-linear extensions of the Lane-Riesenfeld algorithm. • Using the Laurent polynomial representation for analyzing non-uniform subdivision. • Analyzing non-linear subdivision as perturbations of non-uniform linear schemes. We investigate some variants of the linear Lane-Riesenfeld algorithm in the functional setting, generated by replacing the standard binary arithmetic averages between real numbers by non-linear, binary, symmetric averages between real numbers. For certain classes of non-linear averages we show that such generalized r -th order Lane-Riesenfeld algorithms generate limit functions with the same smoothness as the linear r -th order Lane-Riesenfeld algorithm. The analysis is based on the observation that a non-linear subdivision scheme can be regarded as a non-uniform linear scheme with mask coefficients depending on the initial data, and on ideas from a recent investigation of smoothly varying non-uniform linear subdivision schemes (Dyn et al., 2014). Our main result is motivated by an example in Duchamp et al. (2016). It extends a result in Duchamp et al. (2018) , derived for subdivision schemes on smooth manifolds, and applied to the non-linear Lane-Riesenfeld algorithm in the functional setting, by allowing different non-linear averages at different locations in a smoothing step. [ABSTRACT FROM AUTHOR]

In this paper, we propose and discuss a class of inverse eigenvalue problems for real symmetric banded matrices with odd bandwidth. For an odd 2 p + 1 with a positive integer p , the problem is to construct an n × n real symmetric banded matrix with bandwidth 2 p + 1 whose m × m leading principal submatrix is a given m × m real symmetric banded matrix with bandwidth 2 p + 1 and spectrum is a given set of real numbers { λ i } i = 1 n , where the number of distinct real numbers of { λ i } i = 1 n is 2 k when m = p k , or 2 k + 1 when p k < m < p ( k + 1 ) , where m , n and k are positive integers and m < n . We point out that the well-known double dimensional (DD) problem is a special case of our proposed inverse eigenvalue problems. The necessary and sufficient condition for the solvability of the above inverse eigenvalue problem is derived, and the target real symmetric banded matrix can be constructed by the block Lanczos algorithms when the inverse eigenvalue problem is solvable. Several numerical examples show that our algorithms are feasible. Some concluding remarks are introduced. [ABSTRACT FROM AUTHOR]

The 1.5D terrain guarding problem examines a 1.5D terrain as an x -monotone polygonal chain in a plane to find the minimum guarding set for a given input terrain. This problem is NP-complete. In real world applications, guard power is limited and can only cover things within a range. Considering this limitation, the present study introduces the “ terrain guard range ” as a new geometric parameter by discretizing the definition of range, then presents a fixed-parameter algorithm to demonstrate that the 1.5D terrain guarding problem is fixed-parameter tractable with respect to the introduced parameter. [ABSTRACT FROM AUTHOR]

The maximal sum of a sequence A of n real numbers is the greatest sum of all elements of any linearly contiguous and possibly empty subsequence of A . It can be computed in O ( n ) time by means of Kadane's algorithm. Letting A ( x → p ) denote the sequence which results from inserting a real number x just after element A [ p − 1 ] , we show how the maximal sum of A ( x → p ) can be computed in O ( 1 ) worst-case time for any given x and p , provided that an O ( n ) time preprocessing step has already been executed on A . In particular, this implies that, given m pairs ( x 0 , p 0 ) , … , ( x m − 1 , p m − 1 ) , we can compute the maximal sums of sequences A ( x 0 → p 0 ) , … , A ( x m − 1 → p m − 1 ) optimally in O ( n + m ) time, improving on the straightforward and suboptimal strategy of applying Kadane's algorithm to each sequence A ( x i → p i ) , which takes a total of Θ ( n m ) time. We also show that the same time bound is attainable when circular subsequences of A ( x → p ) are taken into account. Our algorithms are easy to implement in practice, and they were motivated by a buffer minimization problem on wireless mesh networks. [ABSTRACT FROM AUTHOR]

Discrete Fourier transform (DFT) is used widely in almost all fields of science and engineering, and is generally calculated using the fast Fourier transform (FFT) algorithm. In this paper, we present a fast algorithm for efficiently computing a DFT of size 3×2 m . The proposed algorithm decomposes the DFT, obtaining one length-2 m unscaled sub-DFT and two length-2 m sub-DFTs scaled by constant real numbers. For efficiently computing the scaled sub-DFTs, the constant real factors are attached to twiddle factors, combining them into new twiddle factors. By using this approach, the number of real multiplications is reduced compared with existing algorithms. To obtain regular datapath, a novel implementation method is presented aiming at the implementation of the proposed algorithm and making its datapath regular like the radix-2 FFT algorithm. The method can be applied to other algorithms with L-shape butterfly. Experimental result shows that, the proposed algorithm consumes less processing time than the existing algorithms for all scale DFTs, and than FFTW, a C subroutine library of FFTs, just for small scale DFTs. [ABSTRACT FROM AUTHOR]

A real matrix A = ( a i j ) 1 ≤ i , j , ≤ n is said to be almost strictly totally negative if it is almost strictly sign regular with signature ε = ( − 1 , − 1 , … , − 1 ) , which is equivalent to the property that all its nontrivial minors are negative. In this paper an algorithmic characterization of nonsingular almost strictly totally negative matrices is presented. [ABSTRACT FROM AUTHOR]

• We have addressed the problem of precoder design for the secondary user (SU) in MIMO cognitive radio by maintaining the QoS for the primary user (PU), in the presence of CSIT uncertainty between the SU-Transmitter and SU-Receiver and between the SU-Transmitter and PU-Receiver. • We have developed a better performance and more efficient alternate iterate precoder solution having higher SU rate and lower computation complexity than the solution from the literature. • We have analyzed the developed solution and shown that it reaches a stationary point with a sublinear rate of convergence. • We have evaluated the computational cost of the proposed solution by providing an upper bound for the number of real arithmetic operations needed in one iteration of alternate projection cycle for completing the three subproblems. • We have compared the performance of the proposed precoder with the solutions from the literature and demonstrated it has better results. This paper advances the design of transmit precoder for a secondary user (SU) coexisting with a primary user (PU) in multiple-input multiple-output (MIMO) cognitive radio, where the channel state information at transmitter (CSIT) of SU is inaccurate in both the desired link (DL) to its receiver and the interference link (IL) to the PU. The design seeks to maximize performance in the worst scenario, by optimizing the capacity of SU while maintaining a given quality of service (QoS) of PU at the most unfavorable uncertainty errors of the two links. The proposed technique improves the previous design by solving for the precoder in a more accurate and efficient manner, and by using the variable metric projected subgradient method. The most unfavorable realization in the DL is obtained by the alternate-iterate optimization method and the worst uncertainty realization in the IL is derived from the projected subgradient method. The convergence properties and computational complexity of the proposed algorithm are analyzed. Numerical results confirm the proposed precoder has better performance than the previous solution while having lower practical time complexity, especially when the PU has higher tolerance level of SU interference. [ABSTRACT FROM AUTHOR]

The three-parameter (3-p) Weibull distribution is an extremely important distribution to characterise the statistical behaviour of a large number of real world phenomenons. It is also useful as a failure model in analysing the reliability of different types of mechanical and electrical components/systems. Successful applications of the distribution rely on an accurate estimation of its three parameters because it directly affects the reliability and lifetime analysis. Due to the intricate system of nonlinear equations and the complexity of the likelihood function, derivative-based optimisation methods may fail to converge. Thus, an efficient and effective method for estimating the parameters of the model is important from the practical viewpoint. In this paper, an optimisation scheme based on an acceptance–rejection (AR) mechanism coupled with an elegant nested sampling (NS) technique is proposed to tackle this problem. The idea is to gradually approach the region of optimal solutions through an efficient sampling technique and a reweighting scheme. The AR-NS algorithm allows a good exploration of the parameter space and converges towards higher likelihood regions by decreasing progressively a pre-specified tolerance threshold. The proposed approach gives the entire distributions of the optimal estimates rather than a single point estimates. To demonstrate the practicality and the efficiency of the proposed approach, numerous numerical examples using simulated data and real-world engineering cases will be given. The obtained results show that the AR-NS algorithm is a suitable method for estimating the parameters of lifetime distributions using different distances. • An efficient algorithm for estimating the parameters of parametric lifetime distributions is proposed. • The optimisation scheme approaches gradually the optimal solutions by propagating "good" particles. • The proposed algorithm provides the entire distributions of the optimal estimates rather than a single point estimates. • The efficiency of the optimisation algorithm has been demonstrated through numerous examples. [ABSTRACT FROM AUTHOR]

Abstract: We show that the generalized Bernstein bases in Müntz spaces defined by Hirschman and Widder (1949) and extended by Gelfond (1950) can be obtained as pointwise limits of the Chebyshev–Bernstein bases in Müntz spaces with respect to an interval as the positive real number a converges to zero. Such a realization allows for concepts of curve design such as de Casteljau algorithm, blossom, dimension elevation to be transferred from the general theory of Chebyshev blossoms in Müntz spaces to these generalized Bernstein bases that we termed here as Gelfond–Bernstein bases. The advantage of working with Gelfond–Bernstein bases lies in the simplicity of the obtained concepts and algorithms as compared to their Chebyshev–Bernstein bases counterparts. [Copyright &y& Elsevier]

Abstract: Ray nonsingular (RNS) matrices are a generalization of sign nonsingular (SNS) matrices from the real field to complex field. The problem of how to recognize ray nonsingular matrices is still open. In this paper, we give an algorithm to recognize the ray nonsingularity for the so called “cycle chain matrices”, whose associated digraphs are of certain simple structure. Furthermore, the cycle chain matrices that are not ray nonsingular are classified into two classes according to whether or not they can be majorized by some RNS cycle chain matrices, and the case when they can is characterized. [Copyright &y& Elsevier]

Abstract: An algorithm based on Linear Matrix Inequalities (LMIs) is proposed to find a constant output feedback matrix and a constant output tandem matrix such that the controlled system is Strictly Positive Real (SPR). The number of output variables of the plant is greater than or equal to the number of its input variables. Considering that SPR systems with static output feedback are related to SPR systems with static state feedback, as shown in this manuscript, the first step of the algorithm is to find a matrix such that all transmission zeros of the system have negative real parts. After finding this matrix , an output feedback matrix such that the system is SPR is found. Another algorithm is proposed to specify a decay rate. The results are applied to the simulation of electrical stimulation for paraplegic patients, to vary knee joint angle from 0° to 60°. [Copyright &y& Elsevier]

Abstract: This paper is concerned with iterative solutions to a class of complex matrix equations, which include some previously investigated matrix equations as special cases. By applying the hierarchical identification principle, an iterative algorithm is constructed to solve this class of matrix equations. A sufficient condition is presented to guarantee that the proposed algorithm is convergent for an arbitrary initial matrix with a real representation of a complex matrix as tools. By using some properties of the real representation, a convergence condition that is easier to compute is also given in terms of original coefficient matrices. A numerical example is employed to illustrate the effectiveness of the proposed methods. [Copyright &y& Elsevier]

Abstract: In this paper, application of the rough set theory (RST) to feature selection in customer relationship management (CRM) is introduced. Compared to other methods, the RST approach has the advantage of combining both qualitative and quantitative information in the decision analysis, which is extremely important for CRM. Automated decision support for CRM has been proposed in recent years. However, little work has been devoted to the development of computer-based systems to support CRM in rule induction. This paper presents a novel rough set based algorithm for automated decision support for CRM. Particularly, the approach is capable to handle real numbers instead of integer numbers through introduction of converted numbers involving tolerances. Being unique and useful in solving CRM problems, an alternative rule extraction algorithm (AREA) is presented for discovering preference-based rules according to the reducts which contain the maximum of strength index (SI) in the same case, where the data with tolerance. The empirical data set associated with CRM has proven the validity and reliability of these approaches. This research thus contributes to developing and validating a useful approach to automated decision support for CRM. This paper forms the basis for solving many other similar problems that occur in the service industry. [ABSTRACT FROM AUTHOR]

Abstract: Given a sequence of real numbers and a positive integer , the Sum Selection Problem is to find the segment such that the rank of the sum is over all segments. We present a deterministic algorithm for this problem that runs in time. The previously best known result for this problem is a randomized algorithm that runs in expected time. Applying this algorithm we can obtain a deterministic algorithm for the k Maximum Sums Problem, i.e., the problem of enumerating the largest sum segments, that runs in time. The previously best known randomized and deterministic algorithms for the k Maximum Sums Problem run respectively in expected time and in worst case time. [Copyright &y& Elsevier]

Abstract: We consider the problem of determining the rational number which best approximates the real number and such that its denominator belongs to an interval . There is a related geometric problem consisting in finding the integer point lying in the vertical domain of the form such that the straight line passing through the origin and through this point best approximates the straight line of slope passing through the origin. The computation of this point is interlinked with the computation of both the convex hulls of the integer points located above and below the straight line respectively and lying in the vertical domain . In the literature, many general convex hull algorithms exist, as the gift wrapping algorithm for example. However, we focus on two interesting approaches to compute these convex hulls which are especially appropriated in our special configuration. The first one mainly uses number theory and runs in time. The other is in line with computational geometry as the method proposed in 1999 by Balza-Gomez et al. [H. Balza-Gomez, J.-M. Moreau, D. Michelucci, Convex hull of grid points below a line or a convex curve, in: DGCI ’99: Proceedings of the 8th International Conference on Discrete Geometry for Computer Imagery, Springer, Marne-la-Vallée, France, 1999, pp. 361–374] which runs in time. We propose a new method for the computation of these convex hulls which combines number theory and computational geometry. Our method preserves the optimal time complexity and is the first being output sensitive. Indeed, we compute the convex hulls in time linear in their vertex number. Moreover, the resulting algorithm is very simple and so is suitable for implementation. [Copyright &y& Elsevier]

Abstract: In this paper, a real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep, M. Thakur, A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation 188 (2007) 895–912; K. Deep, M. Thakur, A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation 193 (2007) 211–230]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. Performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of genetic algorithm and also with random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered. [Copyright &y& Elsevier]

Abstract: In this paper we study optimization problems with verifiable one-parameter selfish agents introduced by Auletta et al. [V. Auletta, R. De Prisco, P. Penna, P. Persiano, The power of verification for one-parameter agents, in: Proceedings of the 31st International Colloquium on Automata, Languages and Programming, ICALP, in: LNCS, vol. 3142, 2004, pp. 171–182]. Our goal is to allocate load among the agents, provided that the secret data of each agent is a single positive real number: the cost they incur per unit load. In such a setting the payment is given after the load completion, therefore if a positive load is assigned to an agent, we are able to verify if the agent declared to be faster than she actually is. We design truthful mechanisms when the agents’ type sets are upper-bounded by a finite value. We provide a truthful mechanism that is -approximate if the underlying algorithm is -approximate and weakly-monotone. Moreover, if type sets are also discrete, we provide a truthful mechanism preserving the approximation ratio of its algorithmic part. Our results improve the existing ones which provide truthful mechanisms dealing only with finite type sets and do not preserve the approximation ratio of the underlying algorithm. Finally, we give applications for our payment schemes. Firstly, we give a full characterization of the problem by using our techniques. Even if our payment schemes need upper-bounded type sets, every instance of can be “mapped” into an instance with upper-bounded type sets preserving the approximation ratio. In conclusion, we turn our attention to binary demand games. In particular, we show that the Minimum Radius Spanning Tree admits an exact truthful mechanism with verification achieving time (and space) complexity of the fastest centralized algorithm for it. This contrasts with a recent truthful mechanism for the same problem [G. Proietti, P. Widmayer, A truthful mechanism for the non-utilitarian minimum radius spanning tree problem, in: Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, ACM Press, 2005, pp. 195–202] which pays a linear factor with respect to the complexity of the fastest centralized algorithm. Such a result is extended to several binary demand games studied in literature. [Copyright &y& Elsevier]

Abstract: Two modifications of Newton’s method to accelerate the convergence of the th root computation of a strictly positive real number are revisited. Both modifications lead to methods with prefixed order of convergence . We consider affine combinations of the two modified th-order methods which lead to a family of methods of order with arbitrarily small asymptotic constants. Moreover the methods are of order for some specific values of a parameter. Then we consider affine combinations of the three methods of order to get methods of order again with arbitrarily small asymptotic constants. The methods can be of order with arbitrarily small asymptotic constants, and also of order for some specific values of the parameters of the affine combination. It is shown that infinitely many th-order methods exist for the th root computation of a strictly positive real number for any . [Copyright &y& Elsevier]

• DisC-EDM that can measure the size and number of the droplets in real time. • Hybrid device consisting of a disposable microchannel and a reusable sensing substrate. • A simple and cost-effective device fabricated with a film-chip technique for single use. • No complex calculation algorithm or expensive equipment required to determine the droplet size. • The sensitivity that does not change depending on the conductivity and velocity of the droplets. For droplet-based microfluidics, a simple and easy-to-use method to measure the size and number of droplets in real-time is required to generate droplets with high uniformity, stability, and throughput. This study introduces a disposable capacitive electrical droplet measurement (DisC-EDM) technique that consists of a disposable microchannel superstrate and a reusable sensing substrate, which can be assembled and disassembled by vacuum pressure. Because the disposable microchannel superstrates can be fabricated easily and cost-effectively with an ultrathin polymer film, it can be replaced after a single use to prevent biological contamination and can also be used to detect the droplet size with a high sensitivity. Meanwhile, the sensing substrate can be continuously reused to achieve cost reduction and ease of use. Owing to three interdigitated electrode configurations, the amplitude of the output signal is linearly proportional to the size of the droplets. Consequently, the need for a complex calculation algorithm or expensive equipment to determine the droplet size is eliminated. Furthermore, because the sensing principle of the DisC-EDM is based on a capacitive detection method, its sensitivity remains constant, even for changes in the conductivity and velocity of the droplets. To demonstrate the effectiveness of the DisC-EDM, it was used to evaluate and compare the performance of a pressure-driven pump and a screw-driven syringe pump in droplet generation. As a cost-effective, reliable, and easy-to-use technique, the DisC-EDM can be used to control the size and uniformity of the droplets in a variety of droplet-based applications. [ABSTRACT FROM AUTHOR]

• Combining algorithms of Abrarov / Quine and Kuntz using method by Schreier. • Use Abrarov / Quine and Kuntz algorithms in place of those by Weideman and Humlíček. • Voigt profile algorithm for lower processing power hardware targeting HITRAN. In this note it is suggested that the complex number rational approximations of Weideman and Humlíček may be replaced with the real number approximations of Abrarov / Quine and Kuntz respectively in the technique suggested by F. Schreier (JQSRT 112(6) (2011) 1010–1025) to provide an accurate Voigt function calculation algorithm with reduced calculation time targeting HITRAN database calculations. The resulting algorithm may be useful in applications using electronics with lower processing power. [ABSTRACT FROM AUTHOR]

Abstract: Given a sequence of real numbers and an integer parameter , the problem studied in this paper is to compute subsequences of consecutive elements with the sums of their elements being the largest, the second largest, …, and the th largest among all possible range sums of the input sequence. For any value of , , we design a fast algorithm that takes time in the worst case to compute and rank all such subsequences. We also prove that our algorithm is optimal for by providing a matching lower bound. Moreover, our algorithm is an improvement over the previous results on the maximum sum subsequences problem (where only the subsequences are requested and no ordering with respect to their relative sums will be determined). Furthermore, given the fact that we have computed the th largest sums, our algorithm retrieves the th largest sum in time, after time of preprocessing. [Copyright &y& Elsevier]

Abstract: Let be a sequence of real numbers . We consider the Sum Selection Problem as that of finding the segment such that the rank of over all possible feasible segments is , where a feasible segment is a consecutive subsequence of , and its width satisfies for some given integers and , and . It is a generalization of two well-known problems: the Selection Problem in computer science for which , and the Maximum Sum Segment Problem in bioinformatics for which the rank is the total number of possible feasible segments. We will give a randomized algorithm for the Sum Selection Problem that runs in expected time. It matches the optimal time randomized algorithm for the Selection Problem. We can also solve the k Maximum Sums Problem, to enumerate the largest sums, in expected time. The previously best known result was an algorithm that solves this problem for the case when , and runs in time in the worst case. [Copyright &y& Elsevier]

Abstract: In an unpublished manuscript, Alan Turing gave a computable construction to show that absolutely normal real numbers between 0 and 1 have Lebesgue measure 1; furthermore, he gave an algorithm for computing instances in this set. We complete his manuscript by giving full proofs and correcting minor errors. While doing this, we recreate Turing’s ideas as accurately as possible. One of his original lemmas remained unproved, but we have replaced it with a weaker lemma that still allows us to maintain Turing’s proof idea and obtain his result. [Copyright &y& Elsevier]

Abstract: To any sequence of real numbers , we can associate another sequence , which Knuth calls its binomial transform. This transform is defined through the rule We study the properties of this transform, obtaining rules for its manipulation and a table of transforms, that allow us to invert many transforms by inspection. We use these methods to perform a detailed analysis of skip lists, a probabilistic data structure introduced by Pugh as an alternative to balanced trees. In particular, we obtain the mean and variance for the cost of searching for the first or the last element in the list (confirming results obtained previously by other methods), and also for the cost of searching for a random element (whose variance was not known). We obtain exact solutions, although not always in closed form. From them we are able to find the corresponding asymptotic expressions. [Copyright &y& Elsevier]

Abstract: We implement exact real numbers in the logical framework Coq using streams, i.e., infinite sequences, of digits, and characterize constructive real numbers through a minimal axiomatization. We prove that our construction inhabits the axiomatization, working formally with coinductive types and corecursive proofs. Thus we obtain reliable, corecursive algorithms for computing on real numbers. [Copyright &y& Elsevier]

Abstract: As we know, the performance of the mean–variance approach depends on the accurate forecast of the return rate. However, the conventional method (e.g. arithmetic mean or regression-based method) usually cannot obtain a satisfied solution especially under the small sample situation. In this paper, the proposed method which incorporates the grey and possibilistic regression models formulates the novel portfolio selection model. In order to solve the multi-objective quadric programming problem, multi-objective evolution algorithms (MOEA) is employed. A numerical example is also illustrated to show the procedures of the proposed method. On the basis of the numerical results, we can conclude that the proposed method can provide the more flexible and accurate results. [Copyright &y& Elsevier]

Abstract: We describe here a representation of computable real numbers and a set of algorithms for the elementary functions associated to this representation. A real number is represented as a sequence of finite B-adic numbers and for each classical function (rational, algebraic or transcendental), we describe how to produce a sequence representing the result of the application of this function to its arguments, according to the sequences representing these arguments. For each algorithm we prove that the resulting sequence is a valid representation of the exact real result. This arithmetic is the first real arithmetic with mathematically proved algorithms. [Copyright &y& Elsevier]

In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: given two points p and q of S and a real number L, compute (or approximate) a shortest path between p and q in the subgraph of the complete graph on S consisting of all edges whose lengths are less than or equal to L. We present efficient algorithms for answering several query problems of this type. Our solutions are based on Euclidean minimum spanning trees, spanners, and the Delaunay triangulation. A result of independent interest is the following. For any two points p and q of S, there is a path between p and q in the Delaunay triangulation, whose length is less than or equal to 2π/(3cos(π/6)) times the Euclidean distance &z.sfnc;pq&z.sfnc; between p and q, and all of whose edges have length at most &z.sfnc;pq&z.sfnc;. [Copyright &y& Elsevier]

Abstract: In an optical mesh network operation, lightpaths are setup when requested, without prior knowledge of future requests. The concerns of increasing the sharing of backup paths and reducing capacity consumption are addressed on a best-of-now basis. As the number of lightpaths increases, it is possible to reroute existing paths to increase sharing further and free up more network capacity. This paper proposes several rerouting algorithms and compares their performance on test networks. All the described algorithms reroute the backup paths only and do not affect ongoing service. Also, the effect of network load factor and the number of lightpaths on the rerouting gain is examined. [Copyright &y& Elsevier]

The rank of an eigenvector of an unreduced real symmetric tridiagonal matrix can be determined by just knowing the signs of the elements of the eigenvector and the signs of the off-diagonal entries of the tridiagonal matrix. Surprisingly, no arithmetic operations involving real numbers are required to determine this ordinal count. The absence of real arithmetic operations guarantees an error free algorithm. Thus, it is possible to rank and order eigenvectors without knowing the corresponding eigenvalues.It is known that the singular value decomposition (SVD) of bidiagonal matrices are closely related to three tridiagonal eigenvalue problems. Using this connection, it is possible to order singular vectors of bidiagonal matrices without knowing the singular values. Again, no real arithmetic is needed.The ordinal count is a theoretical result, which is valid in exact arithmetic. If eigenvectors and singular vectors are poorly determined in floating-point arithmetic then the ordering procedure can detect faulty eigenpairs. Three standard symmetric eigenproblem routines and two SVD routines from LAPACK are investigated to verify whether the ordinal counts give valid results for computed eigenvectors. For some difficult problems such as the Wilkinson Wn+ matrix, the ordinal counts disagree with that given by the routines for n&ges;25. In general, standard LAPACK routines appear to be reasonably resilient even though the routines are not particularly designed to be robust in this context. For some classes of tridiagonals, no failures were detected for n exceeding 3000. However, one of the new LAPACK routines cannot be considered to be robust since it destroys information by thresholding small eigenvector elements to zero. An SVD routine also gave poor results for graded matrices. This could be due to a bug.Many eigenvalue algorithms do a global sort of the eigenvalues. However, if the ordinal count is reliable then ranking of eigenvectors across processors can be achieved without global communication. [Copyright &y& Elsevier]

Computer simulations based on numerical methods applied to the equilibrium equations of Newtonian mechanics have significant impact in many industries, because they provide cheaper development of products. Using computer simulations, it is possible to investigate behavior of product parts and assemblies under different boundary conditions, loads and applied materials, which significantly reduces the number of real expensive experiments. A large number of simulations can be conducted in order to optimize the geometry, materials, product price, etc. or to confirm that the product satisfies technical and safety requirements. By discretization of equilibrium equations, it is possible to simulate only continuous models, i.e. models whose all parts are physically connected. But a problem that occurs very often is mechanical contact between two or more independent mechanical parts. In case the parts are not physically connected, it is necessary to provide an additional boundary condition using a contact algorithm so that the independent parts would be aware of each other. Because of that, the contact problem between deformable moving bodies is always an interesting topic in computational mechanics and mechanical engineering in general. The problem that initiated the development of the contact algorithm presented in this paper is the possibility of numerical simulation of mechanical tests performed during the development of medical stents with the aim to provide a look inside, to show the state of stress or strain in material of the stent. During the implementation of the contact algorithm, two problems arise: 1. finding contact surfaces between different elastic bodies and 2. preventing the penetration of one body into another body by additional boundary condition. This paper presents the implementation of a contact algorithm by finding boundary surface nodes of a deformable body that have penetrated the boundary surface elements of another deformable bodies, and adding boundary conditions that reverse the penetrated nodes to the body boundary. The algorithm is implemented within the in-house software package for finite element analysis. The software is written in Fortran, which is another challenge, given that Fortran does not have as powerful geometry libraries as other modern programming languages do. The main reason for this was compatibility with existing finite element code and facilitated implementation of future parallelization with the aim of reducing computing time. [ABSTRACT FROM AUTHOR]

Feature selection is an important task in machine learning. As multi-label classification tasks appear in various fields, researchers have investigated multi-label feature selection algorithms to reduce data dimensions. Most of the existing wrapper multi-label feature selection algorithms use multi-objective method to obtain the selected features. However, there are multiple criteria to measure the quality of multi-label classification results. In view of this, this study presents a many-objective optimization based multi-label feature selection algorithm (MMFS). To improve the diversity and convergence of NSGA III, we propose an improved NSGA III algorithm with two archives. In this algorithm, new crossover and mutation operators for feature selection are designed to improve the exploration capability, and the influence of the selection threshold θ on feature scale and multi-label classification performance in real number coding is studied. Finally, we conduct experiments on 11 multi-label datasets. The experiments demonstrate that MMFS can balance multiple objectives, remove irrelevant and redundant features, and obtain satisfactory classification results. [ABSTRACT FROM AUTHOR]

Diversity reception is an effective technology to mitigate the atmospheric turbulence effect on the performance of the coherent free-space optical (FSO) communications. Furthermore, considering high-speed optical communications and the state-of-art clock frequency of state-of-the-art field-programmable gate array (FPGA) or application-specific integrated circuits (ASIC), reducing the computational complexity of digital combining algorithm and analyzing the performance of parallel structure algorithm has become important research issues for diversity reception system. In this paper, we experimentally investigate the performance of a low complexity digital combining algorithm (CA) based on adaptive filter By replacing complex weight with real-valued weight, the number of real multiplications required in digital CA can be reduced by 62.5%. real-valued weight CA also ensuring the similar BER and outage probability performance in terms of serial structure under three different turbulence strengths. For parallel structure algorithm, the performance of real-valued weight CA is superior to that of complex-valued weight CA. [ABSTRACT FROM AUTHOR]

This research proposes a new route decision-making strategy, a real-number grid method, that challenges the state-of-the-art method in route decision-making. The key features of the proposed method compared to the conventional route decision making method are implementing a real number grid in the grid generation procedure, global speed optimization in the speed optimization procedure, and a Monte Carlo evaluation in the cost evaluation procedure. The newly suggested method not only improves the optimization performance of the conventional method but also upgrades constraint satisfaction in route decision making. The performance index of route decision making using the proposed method shows a noticeable difference compared to three-dimensional dynamic programming that is the state of art. For performance validation, an intuitively designed cost function is analyzed. The efficacy of this proposed method is proven based on a simulation of the mathematical cost function and actual voyage cases. The performance of the proposed method is demonstrated on a 173K LNG carrier in the Pacific and Atlantic Oceans. This proposed method demonstrates notable performance improvement in the simulation and actual voyage cases. [ABSTRACT FROM AUTHOR]

Detecting communities or clusters of networks is a considerable interesting problem in various fields and interdisciplinary subjects in recent years. Tens of hundreds of methods with significant efforts devoted to community detection in networks, while an open problem in all methods is the unknown number of communities in real networks. It is believed that the central node in a community might be highly surrounded by its neighbors and any two centers of the community reside far from each other, and also believed the similarity among nodes in the same community is larger than the others. Therefore, the local and the global structures' information shed important light on community detection. In this work, we present a three-stage algorithm to detect communities based on the local and the global information without giving the number of communities beforehand. The three stages include the central nodes identification, the label propagation and the communities combination. The central nodes are identified according to the distance between them larger than the average; the label propagation is to label nodes with the same colors when they reach to the maximum similarity; the communities combination is to merge two communities into one if the increment of the modularity is positive and maximum when the two communities were combined. Experiments and simulation results both on real world and synthetic networks show that the three-stage algorithm possesses well matched properties compared with seven other widely used algorithms, which indicates that three-stage algorithm can be used to detect community in social networks. • The presented three-stage algorithm detects communities without knowing the number of them beforehand. • The central nodes' identification completely depends on the node degree and the distance of nodes in networks. • The number of communities is determined by the size of central nodes' set. • The three-stage algorithm converges to global optimum because of the integrated local and global structure information in it. [ABSTRACT FROM AUTHOR]