Results 31 to 40 of about 212 (69)
Combinatorial Dominance Guarantees for Heuristic Algorithms [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 An $f(n)$ $\textit{dominance bound}$ on a heuristic for some problem is a guarantee that the heuristic always returns a solution not worse than at least $f(n)$ solutions.
Daniel Berend +2 more
doaj +1 more source
Matching solid shapes in arbitrary dimension via random sampling [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 We give simple probabilistic algorithms that approximately maximize the volume of overlap of two solid, i.e. full-dimensional, shapes under translations and rigid motions. The shapes are subsets of $ℝ^d$ where $d≥ 2$.
Daria Schymura
doaj +1 more source
Constructions for Clumps Statistics. [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 We consider a component of the word statistics known as clump; starting from a finite set of words, clumps are maximal overlapping sets of these occurrences. This object has first been studied by Schbath with the aim of counting the number of occurrences
Frédérique Bassino +3 more
doaj +1 more source
Samples of geometric random variables with multiplicity constraints [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We investigate the probability that a sample $\Gamma=(\Gamma_1,\Gamma_2,\ldots,\Gamma_n)$ of independent, identically distributed random variables with a geometric distribution has no elements occurring exactly $j$ times, where $j$ belongs to a specified
Margaret Archibald, Arnold Knopfmacher
doaj +1 more source
Structure of Stable Sand Piles Model [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 In this paper we study a variant of the Sand Piles Model, where the evolution rule consists of the falling down of one grain to a random column and an avalanche to reach a stable configuration.
Thi Ha Duong Phan, Thi Thu Huong Tran
doaj +1 more source
Density of truth in modal logics [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 The aim of this paper is counting the probability that a random modal formula is a tautology. We examine $\{ \to,\Box \}$ fragment of two modal logics $\mathbf{S5}$ and $\mathbf{S4}$ over the language with one propositional variable.
Zofia Kostrzycka
doaj +1 more source
Linear time recognition of P4-indifference graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 A graph is a P4-indifference graph if it admits an ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has ...
Michel Habib +2 more
doaj +1 more source
Analysis of a new skip list variant [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 For a skip list variant, introduced by Cho and Sahni, we analyse what is the analogue of horizontal plus vertical search cost in the original skip list model.
Guy Louchard, Helmut Prodinger
doaj +1 more source
Accessible and Deterministic Automata: Enumeration and Boltzmann Samplers [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We present a bijection between the set $\mathcal{A}_n$ of deterministic and accessible automata with $n$ states on a $k$-letters alphabet and some diagrams, which can themselves be represented as partitions of the set $[\![ 1..(kn+1) ]\!]$ into $n$ non ...
Frédérique Bassino, Cyril Nicaud
doaj +1 more source
Explicit computation of the variance of the number of maxima in hypercubes [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We present a combinatorial approach of the variance for the number of maxima in hypercubes. This leads to an explicit expression, in terms of Multiple Zeta Values, of the dominant term in the asymptotic expansion of this variance.Moreover, we get an ...
Christian Costermans, Hoang Ngoc Minh
doaj +1 more source