Related Experiment Video
Updated: Jun 9, 2025
Probing the Limits of Egg Recognition Using Egg Rejection Experiments Along Phenotypic Gradients
Published on: August 22, 2018
A Cross-Entropy Approach to the Domination Problem and Its Variants
Ryan Burdett1, Michael Haythorpe1, Alex Newcombe1
1College of Science and Engineering, Flinders University, 1284 South Road, Tonsley Park, SA 5042, Australia.
Abstract:
The domination problem and three of its variants (total domination, 2-domination, and secure domination) are considered. These problems have various real-world applications, including error correction codes, ad hoc routing for wireless networks, and social network analysis, among others. However, each of them is NP-hard to solve to provable optimality, making fast heuristics for these problems desirable. There are a wealth of highly developed heuristics and approximation algorithms for the domination problem; however, such heuristics are much less common for variants of the domination problem. We redress this gap in the literature by proposing a novel implementation of the cross-entropy method that can be applied to any sensible variant of domination. We present results from experiments that demonstrate that this approach can produce good results in an efficient manner even for larger graphs and that it works roughly as well for any of the domination variants considered.
Related Concept Videos
01:43Incomplete Dominance
01:19Routh-Hurwitz Criterion II
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
01:15Routh-Hurwitz Criterion I
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
01:24Generalization, Discrimination, and Extinction
Generalization occurs when a behavior reinforced in one context is performed in similar situations. For instance, a student who studies diligently for calculus and receives excellent grades might apply the same study habits to psychology and history, expecting similar results. Generalization shows how learning in one setting can influence behavior in...
01:09Decision Making: P-value Method
First, a specific claim about the population parameter is proposed. The claim is based on the research question and is stated in a simple form. Further, an opposing statement to the claim is also stated. These statements can act as null and alternative hypotheses: a null hypothesis would be a neutral statement while the alternative hypothesis can...
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...