A backward selection procedure for approximating a discrete probability distribution by decomposable models

Francesco M. Malvestuto

Displaying similar documents to “A backward selection procedure for approximating a discrete probability distribution by decomposable models”

Tree and local computations in a cross–entropy minimization problem with marginal constraints

Francesco M. Malvestuto (2010)

Kybernetika

Similarity:

In probability theory, Bayesian statistics, artificial intelligence and database theory the minimum cross-entropy principle is often used to estimate a distribution with a given set $P$ of marginal distributions under the proportionality assumption with respect to a given “prior” distribution $q$ . Such an estimation problem admits a solution if and only if there exists an extension of $P$ that is dominated by $q$ . In this paper we consider the case that $q$ is not given explicitly, but is specified...

On signed edge domination numbers of trees

Bohdan Zelinka (2002)

Mathematica Bohemica

Similarity:

The signed edge domination number of a graph is an edge variant of the signed domination number. The closed neighbourhood $N_{G} [e]$ of an edge $e$ in a graph $G$ is the set consisting of $e$ and of all edges having a common end vertex with $e$ . Let $f$ be a mapping of the edge set $E (G)$ of $G$ into the set ${- 1, 1}$ . If $\sum_{x \in N [e]} f (x) \geq 1$ for each $e \in E (G)$ , then $f$ is called a signed edge dominating function on $G$ . The minimum of the values $\sum_{x \in E (G)} f (x)$ , taken over all signed edge dominating function $f$ on $G$ , is called the signed edge domination number...

The complexity of lexicographic sorting and searching

Juraj Wiedermann (1981)

Aplikace matematiky

Similarity:

An asymptotically optimal sorting algorithm that uses $Θ (n (l o g n + k))$ component comparisons to lexicographically sort the set of $n$ $k$ -tuples is presented. This sorting algorithm builds the static data structure - the so called optimal lexicographic search tree - in which it is possible to perform member searching for an unknown $k$ -tuple in at most $[(l o g_{2} (n + 1)] + k - 1$ comparisons. The number of comparisons used by this search algorithm is optimal.

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2002)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem $π$ which only differ on a linear transformation of their objective functions. This...