In this paper, we focus on some specific optimization problems from graphtheory, those for which all feasible solutions have an equal sizethat depends on the instance size.Once having provided a formal definition of this class ofproblems, we try to extract some of its basic properties; most ofthese are deduced from the equivalence, under differentialapproximation, between two versions of a problem π which onlydiffer on a linear transformation of their objective functions.This is notably the case of maximization and minimization versionsof π, as well as general minimization and minimization withtriangular inequality versions of π. Then, we prove that somewell known problems do belong to this class, such as special casesof both spanning tree and vehicles routing problems. Inparticular, we study the strict rural postman problem(called SRPP) and show that both the maximization and theminimization versions can be approximately solved, in polynomialtime, within a differential ratio bounded above by 1/2.From these results, we derive new bounds for standard ratiowhen restricting edge weights to the interval [a,ta] (theSRPP[t] problem): we respectively provide a 2/(t+1)- and a(t+1)/2t-standard approximation for the minimization and themaximization versions.

Retrial queueing systems are characterized by the requirement that customersfinding the service area busy must join the retrial group and reapply forservice at random intervals. This paper deals with the M/G/1 retrial queuesubjected to breakdowns. We use its stochastic decomposition property toapproximate the model performance in the case of general retrial times.

This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse desalgorithmes d'approximation: Formalisme unifié et classesd'approximation” where a new formalism for polynomialapproximation and its basic tools allowing an “absolute”(individual) evaluation the approximability properties ofNP-hard problems have been presented and discussed. Inorder to be used for exhibiting a structure for theclass NPO (the optimization problems of NP),these tools must be enriched with an “instrument” allowingcomparisons between approximability properties of differentproblems (these comparisons must be independent on any specificapproximation result of the problems concerned). This instrumentis the approximability-preserving reductions. We show how tointegrate them in the formalism presented and propose thedefinition of a new reduction unifying, under a specific point ofview a great number of existing ones. This new reduction allowsalso to widen the use of the reductions, restricted until noweither between versions of a problem, or between problems, inorder to enhance structural relations between frameworks. Theyallow, for example, to study how standard-approximation propertiesof a problem transform into differential-approximation ones (forthe same problem, or for another one). Finally, we apply theseveral concepts introduced to the study of the structure (andhardness) of the instances of a problem. This point of view seemsparticurarly fruitful for a better apprehension of the hardness ofcertain problems and of the mechanisms for the design of efficientsolutions for them.

In the present paper a complete procedure for solvingMultiple Objective Integer Linear Programming Problems is presented. The algorithm can be regarded as a corrected form and an alternative to the method that was proposed by Gupta and Malhotra. A numerical illustration is given to show that this latter can miss some efficient solutions. Whereas, the algorithm stated bellow determines all efficient solutions without missing any one.

We show that a particular dynamic priority given to jobs in a multitasks operating system of computers is a deteriorating jobs or a delaying jobs scheduling. Under some assumptions we also show that it is an index rule. To do this, we present the tool of bandit processes to solve stochastic scheduling problems on a single machine.