A comparison of multiobjective evolutionary algorithms.
A cooperative sensor network : optimal deployment and functioning
A network of mobile cooperative sensors is considered. The following problems are studied: (1) the “optimal“deployment of the sensors on a given territory; (2) the detection of local anomalies in the noisy data measured by the sensors. In absence of an information fusion center in the network, from “local” interactions between sensors “global“solutions of these problems are found.
A Cooperative Sensor Network: Optimal Deployment and Functioning
A network of mobile cooperative sensors is considered. The following problems are studied: (1) the “optimal" deployment of the sensors on a given territory; (2) the detection of local anomalies in the noisy data measured by the sensors. In absence of an information fusion center in the network, from “local" interactions between sensors “global" solutions of these problems are found.
A dual feasible forest algorithm for the linear assignment problem
A Note on the Improvement of the Maximum Independent Set's Approximation Ratio
A Polynomial-time Interior-point Algorithm for Convex Quadratic Semidefinite Optimization
In this paper we propose a primal-dual interior-point algorithm for convex quadratic semidefinite optimization problem. The search direction of algorithm is defined in terms of a matrix function and the iteration is generated by full-Newton step. Furthermore, we derive the iteration bound for the algorithm with small-update method, namely, O( log ), which is best-known bound so far.
A Survey of some Non-Standard Traveling Salesman Problems
A View of Interior Point Methods for Linear Programming
An Algorithm for M Asymmetric Travelling Salesman Problem on a Bandwidth-Limited Graph
An algorithm for the minimum variance point of a network
An Overview on Polynomial Approximation of NP-Hard Problems
Applications of a Special Polynomial Class of Tsp
Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
We first motivate and define a notion of asymptotic differential approximation ratio. For this, we introduce a new class of problems called radial problems including in particular the hereditary ones. Next, we validate the definition of the asymptotic differential approximation ratio by proving positive, conditional and negative approximation results for some combinatorial problems. We first derive a differential approximation analysis of a classical greedy algorithm for bin packing, the “first...
Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : de la structure de NPO à la structure des instances
Cet article est la suite de l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation» où nous avons présenté et discuté, dans le cadre d’un nouveau formalisme pour l’approximation polynomiale (algorithmique polynomiale à garanties de performances pour des problèmes NP-difficiles), des outils permettant d’évaluer, dans l’absolu, les proporiétés d’approximation de problèmes difficiles. Afin de répondre pleinement à l’objectif...
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse des algorithmes d'approximation: Formalisme unifié et classes d'approximation” where a new formalism for polynomial approximation and its basic tools allowing an “absolute” (individual) evaluation the approximability properties of NP-hard problems have been presented and discussed. In order to be used for exhibiting a structure for the class NPO (the optimization problems of NP), these tools must be enriched...
Balanced problems on graphs with categorization of edges
Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function: For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete. We also summarize polynomiality results concerning above objective functions for arbitrary...
Branch-and-bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions
This paper deals with the parallel-machine scheduling problem with the aim of minimizing the total (weighted) tardiness under the assumption of different release dates. This problem has been proven to be NP-hard. We introduce some new lower and upper bounds based on different approaches. We propose a branch-and-bound algorithm to solve the weighted and unweighted total tardiness. Computational experiments were performed on a large set of instances...
Branch-and-bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions
This paper deals with the parallel-machine scheduling problem with the aim of minimizing the total (weighted) tardiness under the assumption of different release dates. This problem has been proven to be NP-hard. We introduce some new lower and upper bounds based on different approaches. We propose a branch-and-bound algorithm to solve the weighted and unweighted total tardiness. Computational experiments were performed on a large set of instances...
Calcul des idéaux d'un ordonné fini