We present a regularization method to approach a solution of the pessimistic formulation of ill-posed bilevel problems. This allows to overcome the difficulty arising from the non uniqueness of the lower level problems solutions and responses. We prove existence of approximated solutions, give convergence result using Hoffman-like assumptions. We end with objective value error estimates.

In this paper, we present anew mathematical programming formulation for the Euclidean SteinerTree Problem (ESTP) in ℜ. We relax the integralityconstrains on this formulation and transform the resultingrelaxation, which is convex, but not everywhere differentiable,into a standard convex programming problem in conic form. Weconsider then an efficient computation of an ϵ-optimalsolution for this latter problem using interior-point algorithm.

In on-line computation, the instance of the problem dealt is notentirely known from the beginning of the solution process, but itis revealed step-by-step. In this paper we deal with on-lineindependent set. On-line models studied until now for this problemsuppose that the input graph is initially empty and revealedeither vertex-by-vertex, or cluster-by-cluster. Here we present anew on-line model quite different to the ones already studied. Itassumes that a superset of the final graph is initially present(in our case the complete graph on the order n of the finalgraph) and edges are progressively removed until the achievementof the final graph. Next, we revisit the model introduced in[Demange, Paradon and Paschos, Lect. Notes Comput. Sci.1963 (2000)326–334] and study relaxations assuming that somepaying backtracking is allowed.

We study a continuous version of the capacity and flow assignment problem(CFA) where the design cost is combined with an average delay measureto yield a non convex objective function coupled with multicommodity flowconstraints. A separable convexification of each arc cost function is proposedto obtain approximate feasible solutions within easily computable gaps fromoptimality. On the other hand, DC (difference of convex functions) programming can be usedto compute accurate upper bounds and reduce the gap.The technique is shown to be effective when topology is assumedfixed and capacity expansion on some arcs is considered.

This work studies a new strategic game called delegation game. A delegation game isassociated to a basic game with a finite number of players where each player has a finiteinteger weight and her strategy consists in dividing it into several integer parts andassigning each part to one subset of finitely many facilities. In the associateddelegation game, a player divides her weight into several integer parts, commits each partto an independent delegate and collects the sum of their payoffs in the basic game playedby these delegates. Delegation equilibrium payoffs, consistent delegation equilibriumpayoffs and consistent chains inducing these ones in a delegation game are defined.Several examples are provided.

We consider a special packing-covering pair of problems. Thepacking problem is a natural generalization of finding a(weighted) maximum independent set in an interval graph, thecovering problem generalizes the problem of finding a (weighted)minimum clique cover in an interval graph. The problem pairinvolves weights and capacities; we consider the case of unitweights and the case of unit capacities. In each case we describea simple algorithm that outputs a solution to the packing problemand to the covering problem that are within a factor of 2 of eachother. Each of these results implies an approximative min-maxresult. For the general case of arbitrary weights and capacitieswe describe an LP-based (2 + ε)-approximation algorithm forthe covering problem. Finally, we show that, unlessP = NP, the covering problem cannot be approximated inpolynomial time within arbitrarily good precision.

Individual items of flow in a telecommunications or a transportation network may need to beseparated by a minimum distance or time, called a “headway”. If link dependent, such restrictions in general have the effect that the minimum time path for a “convoy” of items to travel from a given origin to a given destinationwill depend on the size of the convoy. The Quickest Path problemseeks a path to minimise this convoy travel time.A closely related bicriterion problem is the Maximum Capacity Shortest Path problem. For this latter problem,an effective implementation is devised for an algorithm to determine desired sets of efficient solutions which in turn facilitates the searchfor a “best” compromise solution. Numerical experience with the algorithm is reported.

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.

In this paper we propose a family of finite approximations for the departure process of an ME/ME/1 queue indexed by a parameter k defined as the system size of the finite approximation. The approximations capture the interdeparture times from an ME/ME/1 queue exactly and preserve the lag correlations of inter-event times of the departures from an ME/ME/1 queue up to lag (k - 1).

This paper analyzes a discrete-time finite buffer renewal input queue with multipleworking vacations where services are performed in batches of maximum size “b”. The service times bothduring a regular service period and vacation period and vacation times are geometricallydistributed. Employing the supplementary variable and imbedded Markov chain techniques, wederive the steady-state queue length distributions at pre-arrival, arbitrary and outsideobserver’s observation epochs. Based on the queue length distributions, some performancemeasures and waiting time distribution in the queue have been discussed. Finally,numerical results showing the effect of model parameters on the key performance measuresare presented.

Many real-world scheduling problems can be modeled as Multi-mode Resource ConstrainedProject Scheduling Problems (MRCPSP). However, the MRCPSP is a strong NP-hard problem andvery difficult to be solved. The purpose of this research is to investigate a moreefficient alternative based on ant algorithm to solve MRCPSP. To enhance the generalityalong with efficiency of the algorithm, the rule pool is designed to manage numerouspriority rules for MRCPSP. Each ant is provided with an independent thread and endowedwith the learning ability to dynamically select the excellent priority rules. In addition,all the ants in the ant algorithm have the prejudgment ability to avoid infeasible routesbased on the branch and bound method. The algorithm is tested on the well-known benchmarkinstances in PSPLIB. The computational results validate the effectiveness of the proposedalgorithm.

On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme \[ \underline{b}_{n} \, \le \, g\,\oplus \,i\, \le \, \overline{b}_{n}\] où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne $\overline{l}$ , l'index λ1, l'indice de Randić R et le nombre de domination β, $\oplus$ désigne l'une des opérations+, -, ×, /, $\underline{b}_{n}$ et $\overline{b}_{n}$ des fonctions de l'ordre n du graphe qui bornent l'expression $g\oplus i$ et sont atteintes pour tout n (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous ont déjà été présentés, sousforme de conjectures, dans un article précédent paru dans RAIRO Recherche Opérationnelle [RAIRO Oper. Res. 39 (2005) 275–293].


Matthews and Sumner have proved in [10] that if G is a 2-connectedclaw-free graph of order n such that δ(G) ≥ (n-2)/3, then G isHamiltonian. We say that a graph is almost claw-free if for every vertexv of G, 〈N(v)〉 is 2-dominated and the set A of centers of claws of G isan independent set. Broersma et al. [5] have proved that if G isa 2-connected almost claw-free graph of order n such that n such that δ(G) ≥ (n-2)/3, then G is Hamiltonian. We generalize these resultsby considering the graphs satisfying the following property: for everyvertex v ∈ A, there exist exactly two vertices x and y of V\A such that N(v) ⊆ N[x] ∪ N[y]. We extend some other knownresults on claw-free graphs to this new class of graphs.

In this paper we give the expression of the multiplecorrelation coefficient in a linear model according to the coefficientsof correlation. This expression makes it possible to analyze from anumerical point of view the instability of estimates in the case ofcollinear explanatory variables in the linear model or in theautoregressive model. This numerical approach, that we show on twoexamples, thus supplements the usual approach of the quasi colinearity,founded on the statistical properties of the estimators.

We consider the maximum weight perfectly matchable subgraph problemon a bipartite graph G=(UV,E) with respect to given nonnegativeweights of its edges. We show that G has a perfect matching if andonly if some vector indexed by the nodes in UV is a base of anextended polymatroid associated with a submodular function definedon the subsets of UV. The dual problem of the separation problemfor the extended polymatroid is transformed to the special maximumflow problem on G. In this paper, we give a linear programmingformulation for the maximum weight perfectly matchable subgraphproblem and propose an O(n 3) algorithm to solve it.

This article focuses on data aggregation in vehicular ad hoc networks. In such networks, sensor data are usually produced and exchanged between vehicles in order to warn or inform the drivers when an event is detected (e.g., accident, emergency braking, parking space released, vehicle with non-functioning brake lights, etc.).In the following, we present a solution to aggregate and store these data in order to have a history of past events. We therefore use Flajolet-Martin sketches. Our goal is to generate additional knowledge to assist drivers by providing them useful information even if no event is transmitted by vehicles in the vicinity.

In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J.Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (2005) 81–88, using aself improving operation in some hard instances. It is interestingto note that this self improving operation does not work for allinstances. Moreover, based on this approach we deduce that theproblem does not admit constant approximation algorithms forconnected planar cubic bipartite graphs.

In this note, we present a slight modification of an algorithm for thestrict feasibility problem. This modification reducesthe number of iterations.

Cet article est le premier d'une série de deux articles oùnous présentons les principales caractéristiques d'un nouveauformalisme pour l'approximation polynomiale (algorithmiquepolynomiale à garanties de performances pour les problèmesNP-difficiles). Ce travail est l'occasion d'unregard critique sur ce domaine et de discussions sur la pertinencedes notions usuelles. Il est aussi l'occasion de se familiariseravec l'approximation polynomiale, de comprendre ses enjeux etses méthodes. Ces deux articles s'adressent donc autant auxspécialistes qu'aux non spécialistes de ce domaine. Nous insistons toutparticulièrementsur l'intérêt, tant théorique qu'opérationnel, de mettre enévidence une structure au sein de la classe NPO desproblèmes d'optimisation de NP. Dans ce premier article, nousnous intéressons aux outils qui permettent d'évaluer,dans l'absolu, les propriétés d'approximation de problèmesdifficiles. Nous discutons notamment les notions de chaînesd'approximation, de niveau d'approximation, d'ordre de difficultéainsi que deux notions de limites (par rapport à une suited'algorithmes et par rapport aux instances). Chaque notion estlargement discutée et illustrée par de nombreux exempleschoisis essentiellement pour leur valeur pédagogique.
Mots Clés. Complexité, difficulté intrinsèque, analyse des algorithmes et des problèmes,algorithmes d'approximation. Classification Mathématique. 68Q15, 68Q17, 68Q25, 68W25.

In this paper, we describe the methodology used to tackle FranceTelecom workforce scheduling problem (the subject of the RoadefChallenge 2007) and we report the results obtained on the different data sets provided for the competition. Since the problem at hand appears to be NP-hard and due to the highdimensions of the instance sets, we use a two-step heuristical approach. Wefirst devise a problem-tailored heuristic that provides good feasiblesolutions and then we use a meta-heuristic scheme to improve the currentresults. The tailored heuristic makes use of sophisticated integer programming modelsand the corresponding sub-problems are solved using CPLEXwhile the meta-heuristic framework is a randomized local search algorithm. The approach herein described allowed us to rank 5th in this challenge.