An upper bound on the space complexity of random formulae in resolution
We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in -CNF on variables and clauses is .
An Upper Bound on the Space Complexity of Random Formulae in Resolution
We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in k-CNF on n variables and m = Δn clauses is .
Applications of Random Sampling in Computational Geometry, II.
Applications of Random Sampling to On-Line Algorithms in Computational Geometry.
Approximate counting : an alternative approach
Approximating the Minimum Weight Steiner Triangulation.
Approximating the Volume of Convex Bodies.
Are linear algorithms always good for linear problems?
Arrangements of Segments that Share Endpoints: Single Face Results.
Asymptotic analysis of a class of functional equations and applications
Flajolet and Richmond have invented a method to solve a large class of divide-and-conquer recursions. The essential part of it is the asymptotic analysis of a certain generating function for by means of the Mellin transform. In this paper this type of analysis is performed for a reasonably large class of generating functions fulfilling a functional equation with polynomial coefficients. As an application, the average life time of a party of people is computed, where each person advances one...
Automated proofs of upper bounds on the running time of splitting algorithms.
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...
Average case analysis of fully dynamic reachability for directed graphs
Batch scheduling problem with due-date and fuzzy precedence relation
A single-machine batch scheduling problem is investigated. Each job has a positive processing time and due-date. Setup times are assumed to be identical for all batches. All batch sizes cannot exceed a common upper bound. As in many practical situations, jobs have to be subject to flexible precedence constraints. The aim of this paper is to find an optimal batch sequence. The sequence is to minimize the maximal completion time and maximize the minimum value of desirability of the fuzzy precedence....
Berkowitz's algorithm and clow sequences.
Block decomposition approach to compute a minimum geodetic set
In this paper, we develop a divide-and-conquer approach, called block decomposition, to solve the minimum geodetic set problem. This provides us with a unified approach for all graphs admitting blocks for which the problem of finding a minimum geodetic set containing a given set of vertices (g-extension problem) can be efficiently solved. Our method allows us to derive linear time algorithms for the minimum geodetic set problem in (a proper superclass of) block-cacti and monopolar chordal graphs....
Bounds for on-line selection