Fractional programming consists in optimizing a ratio oftwo functions subject to some constraints. Different versions of thismodel, linear or nonlinear, have applications in various fields likecombinatorial optimization, stochastic programming, data bases, andeconomy. Three resolution methods are presented: direct solution,parametric approach and solution of an equivalent problem.

Given a graph with colored edges, a Hamiltonian cycle iscalled alternating if its successive edges differ in color. The problemof finding such a cycle, even for 2-edge-colored graphs, is triviallyNP-complete, while it is known to be polynomial for 2-edge-coloredcomplete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We givea new characterization for such a graph admitting an alternatingHamiltonian cycle which allows us to derive a parallel algorithm forthe problem. Our parallel solution uses a perfect matching algorithmputting the alternating Hamiltonian cycle problem to the RNC class. Inaddition, a sequential version of our parallel algorithm improves thecomputation time of the fastest known sequential algorithm for thealternating Hamiltonian cycle problem by a factor of $O(\sqrt {n} )$ .

We address the 3-Machine Assembly-Type Flowshop Scheduling Problem (3MAF). This problem is known to be NP-complete in the strongsense. We propose an exact branch and bound method based on a recursiveenumeration of potential inputs and outputs of the machines. Using this algorithm,several large size instances have been solved to optimality.

We consider a generalized proximal point method (GPPA) forsolving the nonlinear complementarity problem with monotone operators inRn . It differs from the classical proximal point method discussedby Rockafellar for the problem of finding zeroes of monotone operatorsin the use of generalized distances, called φ-divergences,instead of the Euclidean one. These distances play not only aregularization role but also a penalization one, forcing the sequencegenerated by the method to remain in the interior of the feasible set,so that the method behaves like an interior point one. Under appropriateassumptions on the φ-divergence and the monotone operator weprove that the sequence converges if and only if the problem hassolutions, in which case the limit is a solution. If the problem doesnot have solutions, then the sequence is unbounded. We extend previousresults for the proximal point method concerning convex optimizationproblems.

We first motivate and define a notion of asymptoticdifferential approximation ratio. For this, we introduce a new class ofproblems called radial problems including in particular the hereditaryones. Next, we validate the definition of the asymptotic differentialapproximation ratio by proving positive, conditional and negativeapproximation results for some combinatorial problems. We first derive adifferential approximation analysis of a classical greedy algorithm forbin packing, the “first fit decreasing”. Next we deal with minimumvertex-covering-by-cliques of a graph and the minimumedge-covering-by-complete-bipartite-subgraphs of a bipartite graph anddevise a differential-approximation preserving reduction from the formerto the latter. Finally, we prove two negative differential approximationresults about the ability of minimum vertex-coloring to be approximatedby a polynomial time approximation schema.

In this paper, we develop some stochastic dominancetheorems for the location and scale family and linear combinations ofrandom variables and for risk lovers as well as risk averters thatextend results in Hadar and Russell (1971) and Tesfatsion (1976). Theresults are discussed and applied to decision-making.

The relations between automatic clustering methods and inferentiel statistical models have mostely been studied when the data involves only one set. We propose to study these relations in the caseof data involving two sets. We shall look at cross clustering methods assuggested by Govaert [6]; we show that these methods, like the simple clusteringmethods, can be considered as a clustering approach of a mixture model. Weintroduce the notion of crossed mixture from a concret example and define thenotions of likelihood and associated clustered likelihood. Then, we study therelations which exist between the crossed mixture models and simple models and weshow that these relations are completely similar to those which exist betweenthe crossed clustering methods and simple clustering methods.

This paper presents an application of Multiple Attribute Utility Theory onstrategic choices concerning energy transportation. The environmental assessmentof a network reinforcement strategy is emphasized. Our assessment bringsabout to consider multidimensional variables in MCDM. However, Multi-AttributedUtility Theory (MAUT) cannot, as a practical matter, manage such variables. We therefore work out a methodology to transform multidimensional variablesinto unidimensional ones. We apply it then to a pratical case. From the application, we draw some conclusions on Multi-Attributed Utility Theoryand on its interest for strategic choices dealing with environmental consequences.

Our concern here, is the characterization of dissimilarity indexes defined over finite sets, whose spatial representation is spherical. Consequently, we propose a methodology (NormedMultiDimensional Scaling) to determine the spherical euclidean representation of a set ofitems best accounting for the initial dissimilarity between items. Thismethodology has the advantage of being graphically readable on individual qualitiesof projection like the normed PCA, of which it constitutes a generalization. Moreover, it avoids the arbitrary character of spherical encoding which the use of similitude functions currently used in MDS, implies.