Nous nous intéressons dans ce travail au problème d'approximation d'une matrice donnée par une matrice bistochastique. Des instances de ce problème peuvent apparaître dans différents domaines : en recherche opérationnelle dans un problème d'agrégation de préférence, en calcul de variations et optimisation de forme entre autres. Nous en proposons dans cet article une étude directe via le théorème de projection et une résolution numérique inspirée par la méthode de projections alternées de Boyle-Dykstra.

We show that the problem of deciding if there is a scheduleof length three for the multiprocessor scheduling problem on identicalmachines and unit execution time tasks in -complete even for bipartitegraphs, i.e. for precedence graphs of depth one. This complexity resultextends a classical result of Lenstra and Rinnoy Kan [5].

This paper is devoted to the following version of the single machine preemptive scheduling problem of minimizing the weighted number of late jobs. A processing time, a release date, a due date and a weight of each job are given. Certain jobs are specified to be completed in time, i.e., their due dates are assigned to be deadlines, while the other jobs are allowed to be completed after their due dates. The release/due date intervals are nested, i.e., no two of them overlap (either they have at most one common point or one covers the other). Necessary and sufficient conditions for the completion of all jobs in time are considered, and an O(nlogn) algorithm (where n is the number of jobs) is proposed for solving the problem of minimizing the weighted number of late jobs in case of oppositely ordered processing times and weights.

We propose here a pricing Model which is an extension of the Cooperative Game concept and which includes a notion of Elastic Demand. We present some existence results as well as some algorithms. We conclude by discussing this model in the context of some Production and Transportation problems.

In this paper, we propose a new class of adaptive trust region methods for unconstrained optimization problems and develop some convergence properties. In the new algorithms, we use the current iterative information to define a suitable initial trust region radius at each iteration. The initial trust region radius is more reasonable in the sense that the trust region model and theobjective function are more consistent at the current iterate. The global convergence, super-linear and quadratic convergence rate are analyzed under some mild conditions. Numericalresults show that some special adaptive trust region methods are available and efficient in practical computation.

In a multi server queuing system, buffer size is often larger than the number of servers.This necessitates queuing and waiting for some customers. Customers become impatient whilewaiting for service. Additionally, they may also become impatient if service is notoffered at the desired rate. This paper analyses a finite buffer multi server queuingsystem with the additional restriction that customers may balk as well as renege. Closedform expressions of a number of performance measures are presented. A design problem isdiscussed to demonstrate the results derived.

Dans cet article nous caractérisons, par les facettes, l'enveloppe convexe des vecteurs caractéristiques des hyperplans d'un espace projectif fini et d'un espace affine fini.

We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than 5/4 (unless P = NP). This result is an extension of the result of Hoogeveen et al. [CITE] who proved that there is no polynomial time ρ-approximation algorithm with p < 7/6 for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines.

We first describe four recent methods to cluster vertices of anundirected non weighted connected graph. They are all based onvery different principles. The fifth is a combination of classicalideas in optimization applied to graph partitioning. We comparethese methods according to their ability to recover classesinitially introduced in random graphs with more edges within theclasses than between them.

This paper investigates the problem of maximizing the revenue of a telecommunications operator by simultaneously pricing point-to-point services and allocating bandwidth in its network, while facing competition. Customers are distributed into market segments, i.e., groups of customers with a similar preference for the services. This preference is expressed using utility functions, and customers choose between the offers of the operator and of the competition according to their utility. We model the problem as a leader-follower game between the operator and the customers. This kind of problem has classically been modeled as a bilevel program. A market segmentation is usually defined by a discrete distribution function of the total demand for a service; in this case, the problem can be modeled as a combinatorial optimization problem. In this paper, however, we motivate the use of a continuous distribution function and investigate the nonlinear continuous optimization problem obtained in this case. We analyze the mathematical properties of the problem, and in particular we give a necessary and sufficient condition for its convexity. We introduce methods to solve the problem and we provide encouraging numerical results on realistic telecommunications instances of the problem, showing that it can be solved efficiently.

The soft-capacitated facility location problem, where each facility is composed of a variable number of fixed-capacity production units, has been recently studied in several papers, especially in the metric case. In this paper, we only consider the general problem where connection costs do not systematically satisfy the triangle inequality property. We show that an adaptation of the set covering greedy heuristic, where the subproblem is approximately solved by a fully polynomial-time approximation scheme based on cost scaling and dynamic programming, achieves a logaritmic approximation ratio of (1 + ε)H(n) for the problem, where n is the number of customers to be served and H is the harmonic series. This improves the previous bound of 2H(n) for this problem.

Fractionnal mathematical programs appear in numerous operations research, computer science and economic domains. We consider in this paper the problem of maximizing the sum of 0–1 hyperbolic ratios (SRH). In contrast to the single ratio problem, there has been little work inthe literature concerning this problem. We propose two mixed-integer linear programming formulations of SRH and develop two different strategies to solve them. The first one consists in using directly a general-purpose mixed-integer programming solver. The second one is based on a specialized branch and bound algorithm that reformulates more precisely the problem at every node of search tree. We also propose a heuristic method and we exploit the obtained solution in order to improve the first strategy. We present computational experiments that allow to compare the different approaches.

The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.

Given a tree T with n vertices, we show, by using a dynamicprogramming approach, that the problem of finding a 3-coloring ofT respecting local (i.e., associated with p prespecified subsetsof vertices) color bounds can be solved in O(n6p-1 logn)time. We also show that our algorithm can be adapted to the case ofk-colorings for fixed k.

Comparing q-ary relations on a set $\cal O$ of elementary objects is one of the most fundamental problems ofclassification and combinatorial data analysis. In this paper the specific comparison task that involves classificationtree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One isdefined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches totree comparison are discussed in the context of a set theoretic representation of these relations. Formal andcombinatorial computing aspects of a construction method for a very general family of association coeficients betweenrelations are presented. The main purpose of this article is to specify the components of this construction, based on apermutational procedure, when the structures to be compared are classification trees.

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.

Comparing q-ary relations on a set ${\cal O}$ ofelementary objects is one of the most fundamental problems ofclassification and combinatorial data analysis. In this paper thespecific comparison task that involvesclassification tree structures (binary or not) is considered in thiscontext. Two mathematical representationsare proposed. One is defined in terms of a weighted binary relation; the second uses a 4-ary relation.The most classical approaches to tree comparison are discussed in thecontext of a set theoretic representation of these relations. Formalandcombinatorial computing aspects of a construction method for a verygeneralfamily of association coefficients between relations are presented. The main purpose of this article is to specify the componentsof this construction, based on a permutational procedure, when thestructuresto be compared are classification trees.

In this paper we give necessary and sufficient optimality conditions for a vectoroptimization problem over cones involving support functions in objective as well asconstraints, using cone-convex and other related functions. We also associate a unifieddual to the primal problem and establish weak, strong and converse duality results. Anumber of previously studied problems appear as special cases.

We present a hybrid approach for the FrequencyAssignment Problem with Polarization. This problem, viewed asMax-CSP, is treated as a sequence of decision problems, CSPlike. The proposed approach combines the Arc-Consistencytechniques with a performed Tabu Search heuristic. The resultingalgorithm gives some high quality solutions and has proved itsrobustness on instances with approximately a thousand variablesand nearly ten thousand constraints.

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) coincides with the fractional stable set polytope QSTAB(G). For all imperfect graphs G it holds that STAB(G) ⊂ QSTAB(G). It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss three different concepts, involving the facet set of STAB(G), the disjunctive index of QSTAB(G), and the dilation ratio of the two polytopes.
Including only certain types of facets for STAB(G), we obtain graphs that are in some sense close to perfect graphs, for example minimally imperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by Gerke and McDiarmid [12] as the dilation ratio of STAB(G) and QSTAB(G), whereas Aguilera et al. [1] suggest to take the disjunctive index of QSTAB(G) as the imperfection index of G.For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graphclasses [7,12].
Outgoing from a graph-theoretical interpretation of the imperfectionindex, we prove that there exists no upper bound on the imperfection indexfor those graph classes with a known bounded imperfection ratio.Comparing the two invariants on those classes, it seems that theimperfection index measures imperfection much more roughly than theimperfection ratio; we, therefore, discuss possible directions forrefinements.