A characterization of the set of fixed points of the quicksort transformation.
A comparison of multiobjective evolutionary algorithms.
A complete characterization of primitive recursive intensional behaviours
We give a complete characterization of the class of functions that are the intensional behaviours of primitive recursive (PR) algorithms. This class is the set of primitive recursive functions that have a null basic case of recursion. This result is obtained using the property of ultimate unarity and a geometrical approach of sequential functions on N the set of positive integers.
A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs
ACM Computing Classification System (1998): G.2.2.We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach and computes...
A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs
For large N, we consider the ordinary continued fraction of x=p/q with 1≤p≤q≤N, or, equivalently, Euclid’s gcd algorithm for two integers 1≤p≤q≤N, putting the uniform distribution on the set of p and qs. We study the distribution of the total cost of execution of the algorithm for an additive cost function c on the set ℤ+* of possible digits, asymptotically for N→∞. If c is nonlattice and satisfies mild growth conditions, the local limit theorem was proved previously by the second named author....
A novel generalized oppositional biogeography-based optimization algorithm: application to peak to average power ratio reduction in OFDM systems
A major drawback of orthogonal frequency division multiplexing (OFDM) signals is the high value of peak to average power ratio (PAPR). Partial transmit sequences (PTS) is a popular PAPR reduction method with good PAPR reduction performance, but its search complexity is high. In this paper, in order to reduce PTS search complexity we propose a new technique based on biogeography-based optimization (BBO). More specifically, we present a new Generalized Oppositional Biogeography Based Optimization...
An algebraic approach to Pólya processes
Pólya processes are natural generalizations of Pólya–Eggenberger urn models. This article presents a new approach of their asymptotic behaviour via moments, based on the spectral decomposition of a suitable finite difference transition operator on polynomial functions. Especially, it provides new results for large processes (a Pólya process is called small when 1 is a simple eigenvalue of its replacement matrix and when any other eigenvalue has a real part ≤1/2; otherwise, it is called large).
Analysis of Algorithms: An Example of a Sort Algorithm
We analyse three algorithms: exponentiation by squaring, calculation of maximum, and sorting by exchanging in terms of program algebra over an algebra.
Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs
We analyse a natural edge exchange Markov chain on the set of spanning trees of an undirected graph by the method of multicommodity flows. The analysis is then refined to obtain a canonical path analysis. The construction of the flow and of the canonical paths is based on related path constructions in a paper of Cordovil and Moreira (1993) on block matroids. The estimates of the congestion measure imply a polynomial bound on the mixing time. The canonical paths for spanning trees also yield polynomial...
Approximation algorithms for the traveling salesman problem with range condition
Approximation Algorithms for the Traveling Salesman Problem with Range Condition
We prove that the Christofides algorithm gives a approximation ratio for the special case of traveling salesman problem (TSP) in which the maximum weight in the given graph is at most twice the minimum weight for the odd degree restricted graphs. A graph is odd degree restricted if the number of odd degree vertices in any minimum spanning tree of the given graph is less than times the number of vertices in the graph. We prove that the Christofides algorithm is more efficient (in terms...
Automated proofs of upper bounds on the running time of splitting algorithms.
Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation
The main objective of the polynomial approximation is the development of polynomial time algorithms for NP-hard problems, these algorithms guaranteeing feasible solutions lying “as near as possible” to the optimal ones. This work is the fist part of a couple of papers where we introduce the key-concepts of the polynomial approximation and present the main lines of a new formalism. Our purposes are, on the one hand, to present this theory and its objectives and, on the other hand, to discuss the...
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
Cet article est le premier d'une série de deux articles où nous présentons les principales caractéristiques d'un nouveau formalisme pour l'approximation polynomiale (algorithmique polynomiale à garanties de performances pour les problèmes NP-difficiles). Ce travail est l'occasion d'un regard critique sur ce domaine et de discussions sur la pertinence des notions usuelles. Il est aussi l'occasion de se familiariser avec l'approximation polynomiale, de comprendre ses enjeux et ses méthodes. Ces deux...
Bias-variance decomposition in Genetic Programming
We study properties of Linear Genetic Programming (LGP) through several regression and classification benchmarks. In each problem, we decompose the results into bias and variance components, and explore the effect of varying certain key parameters on the overall error and its decomposed contributions. These parameters are the maximum program size, the initial population, and the function set used. We confirm and quantify several insights into the practical usage of GP, most notably that (a) the...
Branching random walks on binary search trees: convergence of the occupation measure
We consider branching random walks with binary search trees as underlying trees. We show that the occupation measure of the branching random walk, up to some scaling factors, converges weakly to a deterministic measure. The limit depends on the stable law whose domain of attraction contains the law of the increments. The existence of such stable law is our fundamental hypothesis. As a consequence, using a one-to-one correspondence between binary trees and plane trees, we give a description of the...
Convergence of the time-discretized monotonic schemes
Many numerical simulations in (bilinear) quantum control use the monotonically convergent Krotov algorithms (introduced by Tannor et al. [Time Dependent Quantum Molecular Dynamics (1992) 347–360]), Zhu and Rabitz [J. Chem. Phys. (1998) 385–391] or their unified form described in Maday and Turinici [J. Chem. Phys. (2003) 8191–8196]. In Maday et al. [Num. Math. (2006) 323–338], a time discretization which preserves the property of monotonicity has been presented. This paper introduces a proof of...
Differential approximation of NP-hard problems with equal size feasible solutions
In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem which only differ on a linear transformation of their objective functions. This is notably...
Differential approximation of NP-hard problems with equal size feasible solutions
In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem π which only differ on a linear transformation of their objective functions. This is notably...
Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems
We obtain new results regarding the precise average-case analysis of the main quantities that intervene in algorithms of a broad Euclidean type. We develop a general framework for the analysis of such algorithms, where the average-case complexity of an algorithm is related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithms. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory and provide...