Maximum cardinality 1-restricted simple 2-matchings.
Méthode d'aide à la décision sur des évaluations multicritères par plusieurs juges
L'évaluation multicritère est un problème bien connu souvent traité par des méthodes de surclassement. Nous avons ici envisagé le cas général de plusieurs juges et agrégé les différentes évaluations pour construire une matrice de préférences, ramenant ainsi le problème à un problème de comparaisons par paires. Nous avons cherché des solutions optimales de classement en appliquant un algorithme d'affectation quadratique particulier.
Minmax regret combinatorial optimization problems: an Algorithmic Perspective
Uncertainty in optimization is not a new ingredient. Diverse models considering uncertainty have been developed over the last 40 years. In our paper we essentially discuss a particular uncertainty model associated with combinatorial optimization problems, developed in the 90's and broadly studied in the past years. This approach named minmax regret (in particular our emphasis is on the robust deviation criteria) is different from the classical approach for handling uncertainty, stochastic approach,...
Minmax regret combinatorial optimization problems: an Algorithmic Perspective
Uncertainty in optimization is not a new ingredient. Diverse models considering uncertainty have been developed over the last 40 years. In our paper we essentially discuss a particular uncertainty model associated with combinatorial optimization problems, developed in the 90's and broadly studied in the past years. This approach named minmax regret (in particular our emphasis is on the robust deviation criteria) is different from the classical approach for handling uncertainty, stochastic approach,...
Modelli di ottimizzazione combinatoria per problemi di coordinamento nei sistemi di produzione multi-stadio
Moderní pohled na „jistý problém minimální‟
New algorithms for coupled tasks scheduling – a survey
The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various variants of...
Non orthogonal cutting problem the case of trapezoidal pieces.
On a Construction of Digital Convex -gons of Minimum Diameter
On a dual network exterior point simplex type algorithm and its computational behavior
The minimum cost network flow problem, (MCNFP) constitutes a wide category of network flow problems. Recently a new dual network exterior point simplex algorithm (DNEPSA) for the MCNFP has been developed. This algorithm belongs to a special “exterior point simplex type” category. Similar to the classical dual network simplex algorithm (DNSA), this algorithm starts with a dual feasible tree-solution and after a number of iterations, it produces a solution that is both primal and dual feasible, i.e....
On a dual network exterior point simplex type algorithm and its computational behavior∗
The minimum cost network flow problem, (MCNFP) constitutes a wide category of network flow problems. Recently a new dual network exterior point simplex algorithm (DNEPSA) for the MCNFP has been developed. This algorithm belongs to a special “exterior point simplex type” category. Similar to the classical dual network simplex algorithm (DNSA), this algorithm starts with a dual feasible tree-solution and after a number of iterations, it produces a...
On a facet of the balanced subgraph polytope
On blockers in bounded posets.
On cycling in the simplex method of the transportation problem
This paper shows that cycling of the simplex method for the m × n transportation problem where k-1 zero basic variables are leaving and reentering the basis does not occur once it does not occur in the k × k assignment problem. A method to disprove cycling for a particular k is applied for k=2,3,4,5 and 6.
On Geometric Optimization with Few Violated Constraints.
On minimizing total tardiness in a serial batching problem
We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time occurs. This problem s-batch is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.
On Minimizing Total Tardiness in a Serial Batching Problem
We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time s occurs. This problem 1|s-batch | ∑Ti is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.
On some Interconnections Between Combinatorial Optimization and Extremal Graph Theory
On the coefficients of the max-algebraic characteristic polynomial and equation
No polynomial algorithms are known for finding the coefficients of the characteristic polynomial and characteristic equation of a matrix in max- algebra. The following are proved: (1) The task of finding the max-algebraic characteristic polynomial for permutation matrices encoded using the lengths of their constituent cycles is NP-complete. (2) The task of finding the lowest order finite term of the max-algebraic characteristic polynomial for a matrix can be converted to the assignment problem....
On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems
This paper studies the complexity of sensitivity analysis for optimal and ε-optimal solutions to general 0-1 combinatorial optimization problems with min-max objectives. Van Hoesel and Wagelmans [9] have studied the complexity of sensitivity analysis of optimal and ε-optimal solutions to min-sum problems, and Ramaswamy et al. [17] the complexity of sensitivity analysis of optimal solutions to min-max problems. We show that under some mild assumptions the sensitivity analysis of ε-optimal solutions...