ABSTRACT
Given an undirected graph with weights on the vertices, the maximum weight clique problem (MWCP) is to find a subset of mutually adjacent vertices (i.e., a clique) having the largest total weight. This is a generalization of the classical problem of finding the maximum cardinality clique of an unweighted graph, which arises as a special case of the MWCP when all the weights associated to the vertices are equal. The problem is known to be NP-hard for arbitrary graphs and, according to recent theoretical results, so is the problem of approximating it within a constant factor. Although there has recently been much interest around neural-network algorithms for the unweighted maximum clique problem, no effort has been directed so far toward its weighted counterpart. In this paper, we present a parallel, distributed heuristic for approximating the MWCP based on dynamics principles developed and studied in various branches of mathematical biology. The proposed framework centers around a recently introduced continuous characterization of the MWCP which generalizes an earlier remarkable result by Motzkin and Straus. This allows us to formulate the MWCP (a purely combinatorial problem) in terms of a continuous quadratic programming problem. One drawback associated with this formulation, however, is the presence of "spurious" solutions, and we present characterizations of these solutions. To avoid them we introduce a new regularized continuous formulation of the MWCP inspired by previous works on the unweighted problem, and show how this approach completely solves the problem. The continuous formulation of the MWCP naturally maps onto a parallel, distributed computational network whose dynamical behavior is governed by the so-called replicator equations. These are dynamical systems introduced in evolutionary game theory and population genetics to model evolutionary processes on a macroscopic scale.We present theoretical results which guarantee that the solutions provided by our clique finding replicator network are actually the ones being sought. Extensive experiments on both randomly generated and standard benchmark graphs have been conducted, and the results obtained confirm the effectiveness of the proposed approach.
ABSTRACT
After an introduction to the problems of binocular vision and an overview of the literature, the authors report on the reasons for undertaking this study and on its practical implications. Up to now, no other randomized study has been undertaken to our knowledge on children of this age group in such a large city as Vienna. All children in primary 3 classes in 20 out of the 256 elementary schools were examined ophthalmologically and orthoptically. It was found that hereditary factors are of statistically significant importance. Especially important for the ophthalmologist is also the statistically significant relation between the diagnosis poor range of fusion, poor fixation, incorrect Worth test for distance and/or proximity, and poor or lacking stereoscopic vision with the occurrence of strabism. The authors were astonished to find a remarkably high percentage of exophoria (58%), in contrast to esophoria (16%). It is interesting for prophylaxis and therapy that children originating from families where spectacles are worn, acted more cooperatively and tended to take the orders of the physician more seriously than those coming from families without eye problems. The promotion of genetic research related to squint and more counselling for couples wishing to have children or confronted with risk factor problems would be desirable, as well as the inclusion of more obligatory ophthalmological examinations in the mother-child medical "passport".
Subject(s)
Strabismus/etiology , Austria/epidemiology , Child , Cross-Sectional Studies , Female , Humans , Incidence , Male , Patient Care Team , Refraction, Ocular , Risk Factors , Strabismus/epidemiology , Strabismus/genetics , Vision ScreeningABSTRACT
The authors combine known models for the evolution of (a) strategies in animal conflicts, and (b) gene frequencies for differential fecundity in order to relate the sociobiological notion of evolutionarily stable strategy with the genetic mechanism of Mendelian populations.
