Volume 5, numéro 1, spring 2009

EN :

Linear Complementarity Problems (LCPs) belong to the class of NP-complete problems. Therefore we can not expect a polynomial time solution method for LCPs without requiring some special property of the coefficient matrix. Following our recently published ideas we generalize affine scaling and predictor-corrector interior point algorithms to solve LCPs with general matrices in EP-sense, namely, our generalized interior point algorithms either solve the problems with rational coefficient matrix in polynomial time or give a polynomial size certificate that our matrix does not belong to the set of P (~κ) matrices, with arbitrary large, but apriori fixed, rational, positive ~κ.

EN :

This paper deals with the 2-Peripatetic Salesman Problem for the case where costs respect the triangle inequality. The aim is to determine 2 edge disjoint Hamiltonian cycles of minimum total cost on a graph. We first present a straightforward 9/4 approximation algorithm based on the well known Christofides algorithm for the travelling salesman problem. Then we propose a 2(n−1)/n-approximation polynomial time algorithm based on the solution of the minimum cost two-edge-disjoint spanning trees problem. Finally, we show that by partially combining these two algorithms, a 15/8 approximation ratio can be reached if a 5/4 approximation algorithm can be found for the related problem of finding two edge disjoint subgraphs consisting of a spanning tree and a Hamiltonian cycle of minimum total cost.

EN :

The sphere method for solving linear programs operates with only a subset of constraints in the model in each iteration, and thus has the advantage of handling instances which may not be very sparse. In this paper we discuss enhancements, and improved versions Sphere Methods 2, 2.1 which improve performance by 20 to 80%. Additional steps that can improve performance even more are also presented.

EN :

In the paper we mainly study the C_max problem of scheduling n groups of jobs on n special-purpose processors and m general-purpose processors at the same speed provided the ready time of each job is less than times of its processing time. We first propose an improved LS algorithm. We then show that the bound for the ratio of the approximate solution T ^LS to the optimal solution T is less than (1 + )(2 − 1 n+m ). Moreover, we give an example to illustrate that it is tight for any ≥ 0.

EN :

This paper consists in constructing and modeling Dynamic Multi Generative Network Flows in which the flow commodities is dynamically generated at source nodes and dynamically consumed at sink nodes. It is assumed that the source nodes produce the flow commodities according to k time generative functions and the sink nodes absorb the flow commodities according to k time consumption functions. The minimum cost dynamic flow problem in such networks that extend the classical optimal flow problems on static networks, for a pre-specified time horizon T is defined and mathematically formulated. Moreover, it is showed that the dynamic problem on these networks can be formulated as a linear program whose special structure permits efficient computations of its solution and can be solved by one minimum cost static flow computation on an auxiliary time-commodity expanded network. By using flow decomposition theorem, we elaborate a different model of the problem to reduce its complexity. We consider the problem in the general case when the cost and capacity functions depend on time and commodity.

EN :

We study a probabilistic optimization model for graph-problems under vertex-uncertainty. We assume that any vertex v_i of the input-graph G(V, E) has only a probability p_i to be present in the final graph to be optimized (i.e., the final instance for the problem tackled will be only a sub-graph of the initial graph). Under this model, the original “deterministic” problem gives rise to a new (deterministic) problem on the same input-graph G, having the same set of feasible solutions as the former one, but its objective function can be very different from the original one, the set of its optimal solutions too. Moreover, this objective function is a sum of 2^{|V |} terms; hence, its computation is not immediately polynomial. We give sufficient conditions for large classes of graph-problems under which objective functions of their probabilistic counterparts are polynomially computable and optimal solutions are well-characterized. Finally, we apply these general results to natural and well-known combinatorial problems that belong to the classes considered.