Page 1 Next

Displaying 1 – 20 of 55

Showing per page

A cooperative sensor network : optimal deployment and functioning

Alfonso Farina, Antonio Graziano, Francesca Mariani, Francesco Zirilli (2010)

RAIRO - Operations Research - Recherche Opérationnelle

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

Alfonso Farina, Antonio Graziano, Francesca Mariani, Francesco Zirilli (2011)

RAIRO - Operations Research

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 Polynomial-time Interior-point Algorithm for Convex Quadratic Semidefinite Optimization

Y. Q. Bai, F. Y. Wang, X. W. Luo (2010)

RAIRO - Operations Research

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( n log n ε ), which is best-known bound so far.

Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems

Marc Demange, Vangelis Th. Paschos (2010)

RAIRO - Operations Research

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

Marc Demange, Vangelis Paschos (2002)

RAIRO - Operations Research - Recherche Opérationnelle

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

Marc Demange, Vangelis Paschos (2010)

RAIRO - Operations Research

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

Štefan Berežný, Vladimír Lacko (2003)

Discussiones Mathematicae Graph Theory

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: L ( D ) = m a x 1 i p ( m a x e S i D w ( e ) - m i n e S i D w ( e ) ) 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

Imed Kacem, Nizar Souayah, Mohamed Haouari (2012)

RAIRO - Operations Research

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

Imed Kacem, Nizar Souayah, Mohamed Haouari (2012)

RAIRO - Operations Research

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...

Currently displaying 1 – 20 of 55

Page 1 Next