Approximation algorithms for the traveling salesman problem with range condition
Approximation Algorithms for the Traveling Salesman Problem with Range Condition
We prove that the Christofides algorithm gives a approximation ratio for the special case of traveling salesman problem (TSP) in which the maximum weight in the given graph is at most twice the minimum weight for the odd degree restricted graphs. A graph is odd degree restricted if the number of odd degree vertices in any minimum spanning tree of the given graph is less than times the number of vertices in the graph. We prove that the Christofides algorithm is more efficient (in terms...
Approximations of weighted independent set and hereditary subset problems.
Arrow's Impossibility Theorem
A formalization of the first proof from [6].
Assignment of Distributed Processing Software: A Comparative Study
Asymptotic normality of recursive algorithms via martingale difference arrays.
Automated proofs for some Stirling number identities.
Automated proofs of upper bounds on the running time of splitting algorithms.
Automatic differentiation and its program realization
Automatic differentiation is an effective method for evaluating derivatives of function, which is defined by a formula or a program. Program for evaluating of value of function is by automatic differentiation modified to program, which also evaluates values of derivatives. Computed values are exact up to computer precision and their evaluation is very quick. In this article, we describe a program realization of automatic differentiation. This implementation is prepared in the system UFO, but its...
Automatic differentiation platform : design
Automatic differentiation (AD) has proven its interest in many fields of applied mathematics, but it is still not widely used. Furthermore, existing numerical methods have been developed under the hypotheses that computing program derivatives is not affordable for real size problems. Exact derivatives have therefore been avoided, or replaced by approximations computed by divided differences. The hypotheses is no longer true due to the maturity of AD added to the quick evolution of machine capacity....
Automatic Differentiation Platform: Design
Automatic differentiation (AD) has proven its interest in many fields of applied mathematics, but it is still not widely used. Furthermore, existing numerical methods have been developed under the hypotheses that computing program derivatives is not affordable for real size problems. Exact derivatives have therefore been avoided, or replaced by approximations computed by divided differences. The hypotheses is no longer true due to the maturity of AD added to the quick evolution of machine capacity....
Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation
The main objective of the polynomial approximation is the development of polynomial time algorithms for NP-hard problems, these algorithms guaranteeing feasible solutions lying “as near as possible” to the optimal ones. This work is the fist part of a couple of papers where we introduce the key-concepts of the polynomial approximation and present the main lines of a new formalism. Our purposes are, on the one hand, to present this theory and its objectives and, on the other hand, to discuss the...
Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : de la structure de NPO à la structure des instances
Cet article est la suite de l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation» où nous avons présenté et discuté, dans le cadre d’un nouveau formalisme pour l’approximation polynomiale (algorithmique polynomiale à garanties de performances pour des problèmes NP-difficiles), des outils permettant d’évaluer, dans l’absolu, les proporiétés d’approximation de problèmes difficiles. Afin de répondre pleinement à l’objectif...
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse des algorithmes d'approximation: Formalisme unifié et classes d'approximation” where a new formalism for polynomial approximation and its basic tools allowing an “absolute” (individual) evaluation the approximability properties of NP-hard problems have been presented and discussed. In order to be used for exhibiting a structure for the class NPO (the optimization problems of NP), these tools must be enriched...
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
Cet article est le premier d'une série de deux articles où nous présentons les principales caractéristiques d'un nouveau formalisme pour l'approximation polynomiale (algorithmique polynomiale à garanties de performances pour les problèmes NP-difficiles). Ce travail est l'occasion d'un regard critique sur ce domaine et de discussions sur la pertinence des notions usuelles. Il est aussi l'occasion de se familiariser avec l'approximation polynomiale, de comprendre ses enjeux et ses méthodes. Ces deux...
Axiomatisation des manipulations symboliques en calcul des prédicats