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...

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 $\mathrm{STAB}\left(G\right)$ coincides with the fractional stable set polytope $\mathrm{QSTAB}\left(G\right)$. For all imperfect graphs $G$ it holds that $\mathrm{STAB}\left(G\right)\subset \mathrm{QSTAB}\left(G\right)$. 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...

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...

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...

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...

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.

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.

The paper is motivated by the stochastic comparison of the reliability of non-repairable $k$-out-of-$n$ systems. The lifetime of such a system with nonidentical components is compared with the lifetime of a system with identical components. Formally the problem is as follows. Let $U_i,i=1,...,n,$ be positive independent random variables with common distribution $F$. For ${\lambda }_i\>0$ and $\mu \>0$, let consider $X_i=U_i/{\lambda }_i$ and $Y_i=U_i/\mu ,i=1,...,n$. Remark that this is no more than a change of scale for each term. For $k\in \{1,2,...,n\},$ let us define $X_{k:n}$ to be the $k$th order statistics...

The paper is motivated by the stochastic comparison of the reliability of non-repairable k-out-of-n systems. The lifetime of such a system with nonidentical components is compared with the lifetime of a system with identical components. Formally the problem is as follows. Let Ui,i = 1,...,n, be positive independent random variables with common distribution F. For λi > 0 and µ > 0, let consider Xi = Ui/λi and Yi = Ui/µ, i = 1,...,n. Remark that this is no more than a change of scale for each...

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.

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.

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.

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...

In this paper, we present the simple and double compression algorithms with an error control for compressing satellite data corresponding to several revolutions. The compressions are performed by means of approximations in the norm L∞ by finite series of Chebyshev polynomials, with their known properties of fast evaluation, uniform distribution of the error, and validity over large intervals of time. By using the error control here introduced, the number of terms of the series is given automatically...