Comparaison d'algorithmes de plus courts chemins sur des graphes routiers de grande taille
Comparaison de deux méthodes de résolution d'un problème combinatoire quadratique
Comparaison expérimentale d'algorithmes pour les problèmes de recouvrement et de maximisation d'une fonction pseudo-booléenne
Comparaisons par paires : une interprétation et une généralisation de la méthode des scores
Comparing classification tree structures : a special case of comparing -ary relations
Comparing classification tree structures : a special case of comparing -ary relations II
Comparing classification tree structures: A special case of comparing q-ary relations II
Comparing q-ary relations on a set of elementary objects is one of the most fundamental problems of classification and combinatorial data analysis. In this paper the specific comparison task that involves classification tree structures (binary or not) is considered in this context. Two mathematical representations are 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 the context...
Comparing classification tree structures: a special case of comparing q-ary relations
Comparing q-ary relations on a set of elementary objects is one of the most fundamental problems of classification and combinatorial data analysis. In this paper the specific comparison task that involves classification tree structures (binary or not) is considered in this context. Two mathematical representations are 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 the context...
Comparing imperfection ratio and imperfection index for graph classes
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 where the stable set polytope coincides with the fractional stable set polytope . For all imperfect graphs it holds that . 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...
Comparing Imperfection Ratio and Imperfection Index for Graph Classes
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...
Comparing notions of approximation.
In this note we discuss some drawbacks of some approaches to the classification of NP-complete optimization problems. Then we analyze the Theory of Analytical Computational Complexity to gain some insight about the notions of approximation and approximate algorithms. We stress the different roles played by these notions within the theories of Analytical and Algebraic Complexity. We finally outline a possible strategy to capture a more useful notion of approximation which is inspired by some results...
Comparison between different duals in multiobjective fractional programming
The present paper is a continuation of [2] where we deal with the duality for a multiobjective fractional optimization problem. The basic idea in [2] consists in attaching an intermediate multiobjective convex optimization problem to the primal fractional problem, using an approach due to Dinkelbach ([6]), for which we construct then a dual problem expressed in terms of the conjugates of the functions involved. The weak, strong and converse duality statements for the intermediate problems allow...
Comparison of algorithms in graph partitioning
We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.
Comparison of algorithms in graph partitioning
We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.
Complementarity problem for -monotone-type maps.
Completely generalized nonlinear variational inclusions for fuzzy mappings
In this paper, we introduce and study a new class of completely generalized nonlinear variational inclusions for fuzzy mappings and construct some new iterative algorithms. We prove the existence of solutions for this kind of completely generalized nonlinear variational inclusions and the convergence of iterative sequences generated by the algorithms.
Complexity of partial inverse assignment problem and partial inverse cut problem
For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.
Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem
For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.
Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions
In this paper, we first present a polynomial-time primal-dual interior-point method (IPM) for solving linear programming (LP) problems, based on a new kernel function (KF) with a hyperbolic-logarithmic barrier term. To improve the iteration bound, we propose a parameterized version of this function. We show that the complexity result meets the currently best iteration bound for large-update methods by choosing a special value of the parameter. Numerical experiments reveal that the new KFs have better...
Composite semi-infinite optimization