Calculation des valeurs numcute{e}riques des polynomes au moyen des spectres mathematiques
Can Adaption Help on the Average.
Can Visibility Graphs Be Represented Compactly?.
Chance constrained bottleneck transportation problem with preference of routes
This paper considers a variant of the bottleneck transportation problem. For each supply-demand point pair, the transportation time is an independent random variable. Preference of each route is attached. Our model has two criteria, namely: minimize the transportation time target subject to a chance constraint and maximize the minimal preference among the used routes. Since usually a transportation pattern optimizing two objectives simultaneously does not exist, we define non-domination in this...
Chaos and complexity in a simple model of production dynamics.
Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
Checking positive definiteness or stability of symmetric interval matrices is NP-hard
It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard.
Circuit lower bounds and linear codes.
Classes of Graphs Which Approximate the Complete Euclidean Graph.
Combinatorial analysis of quicksort algorithm
Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.
Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers
Combined complexity classes for finite functions
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...
Complexité algébrique
Complexité de l'arboricité linéaire d'un graphe II
Complexité de problèmes liés aux graphes sans circuit
Complexity arguments in algebraic language theory
Complexity aspects of the Helly property: graphs and hypergraphs.
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.