Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Producing a GIS based multiple criteria analysis tool for regional sustainability assessment: the problem of weighting

Decision support tools will be useful in guiding regions to sustainability. These need to be simple but effective at identifying, for regional managers, areas most in need of initiatives to progress sustainability. Multiple criteria analysis (MCA) is often used as a decision support tool for a wide range of applications. This method allows many criteria to be considered at one time. It does this by giving a ranking of possible options based on how closely each option meets the criteria. Thus, it is suited to the assessment of regional sustainability as it can consider a number of indicators simultaneously and demonstrates how sustainability can vary at small scales across the region. Coupling MCA with GIS to produce maps, allows this analysis to become visual giving the manager a picture of sustainability across the region. To do this each indicator is standardised to a common scale so that it can be compared to other indicators. A weighting is then applied to each indicator to calculate weighted summation for each area in the region. This paper argues that this is the critical step in developing a useful decision support tool. A study being conducted in south west Victoria demonstrates that the weights chosen can have a dramatic impact on the results of the sustainability assessment. It is therefore imperative that careful consideration be given to determining indicator weights in a way that is objective and fully considers the impact of that indicator on regional sustainability.

Impossible triangles: flat actors in telematic theatre

In fact, in this scene, both A and B are online. A is in a classroom at the University of Amsterdam in The Netherlands, and B is in a television studio at Deakin University in Melbourne, Australia. The two locations are connected through video conference and, in each space, a local audience watches the local performer in the room, and the remote performer projected on a screen. The performers are captured in profile, and appear to be looking at computer screens in front of them but cannot actually see one another. The text is consciously banal, composed to replicate the broken rhythms and sequences, flattened tone and repetitions of scrolling words in a text box on a screen. Information about presence and absence (A or B is offline or online) is spoken as text. Although the two performers speak in accents that declare their different language/ cultures, the vernacular is generic 'internetslang'. The relatively monotonous and unpunctuated delivery of the textual rhythms is interrupted and counterpointed by a sound lag of nearly a second, and by a faint audio echo as one voice 'lands' in the second location. Its orchestration allows the sound fracture and dispersal in some moments. In other moments, the actors anticipate or absorb the gaps in transmission, driving the speech rhythms through so that the utterance 'arrives' precisely at the end of the prompt line.

Dynamics of inter-modality re-weighting during human postural control

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Adaptive Visual Re-Weighting in Children's Postural Control

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

The Fundamental Gap For Hyperbolic Triangles

In 1983, M. van den Berg made his Fundamental Gap Conjecture about the difference between the first two Dirichlet eigenvalues (the fundamental gap) of any convex domain in the Euclidean plane. Recently, progress has been made in the case where the domains are polygons and, in particular, triangles. We examine the conjecture for triangles in hyperbolic geometry, though we seek an for an upper bound for the fundamental gap rather than a lower bound.

Time-order errors and standard-position effects in duration discrimination: An experimental study and an analysis by the sensation-weighting model

Studies have shown that the discriminability of successive time intervals depends on the presentation order of the standard (St) and the comparison (Co) stimuli. Also, this order affects the point of subjective equality. The first effect is here called the standard-position effect (SPE); the latter is known as the time-order error. In the present study, we investigated how these two effects vary across interval types and standard durations, using Hellström’s sensation-weighting model to describe the results and relate them to stimulus comparison mechanisms. In Experiment 1, four modes of interval presentation were used, factorially combining interval type (filled, empty) and sensory modality (auditory, visual). For each mode, two presentation orders (St–Co, Co–St) and two standard durations (100 ms, 1,000 ms) were used; half of the participants received correctness feedback, and half of them did not. The interstimulus interval was 900 ms. The SPEs were negative (i.e., a smaller difference limen for St–Co than for Co–St), except for the filled-auditory and empty-visual 100-ms standards, for which a positive effect was obtained. In Experiment 2, duration discrimination was investigated for filled auditory intervals with four standards between 100 and 1,000 ms, an interstimulus interval of 900 ms, and no feedback. Standard duration interacted with presentation order, here yielding SPEs that were negative for standards of 100 and 1,000 ms, but positive for 215 and 464 ms. Our findings indicate that the SPE can be positive as well as negative, depending on the interval type and standard duration, reflecting the relative weighting of the stimulus information, as is described by the sensation-weighting model.

Kinematic geometry of mass-triangles and reduction of Schrödinger’s equation of three-body systems to partial differential equations solely defined on triangular parameters

Schrödinger’s equation of a three-body system is a linear partial differential equation (PDE) defined on the 9-dimensional configuration space, ℝ9, naturally equipped with Jacobi’s kinematic metric and with translational and rotational symmetries. The natural invariance of Schrödinger’s equation with respect to the translational symmetry enables us to reduce the configuration space to that of a 6-dimensional one, while that of the rotational symmetry provides the quantum mechanical version of angular momentum conservation. However, the problem of maximizing the use of rotational invariance so as to enable us to reduce Schrödinger’s equation to corresponding PDEs solely defined on triangular parameters—i.e., at the level of ℝ6/SO(3)—has never been adequately treated. This article describes the results on the orbital geometry and the harmonic analysis of (SO(3),ℝ6) which enable us to obtain such a reduction of Schrödinger’s equation of three-body systems to PDEs solely defined on triangular parameters.

Dynamic weighting in Monte Carlo and optimization

Dynamic importance weighting is proposed as a Monte Carlo method that has the capability to sample relevant parts of the configuration space even in the presence of many steep energy minima. The method relies on an additional dynamic variable (the importance weight) to help the system overcome steep barriers. A non-Metropolis theory is developed for the construction of such weighted samplers. Algorithms based on this method are designed for simulation and global optimization tasks arising from multimodal sampling, neural network training, and the traveling salesman problem. Numerical tests on these problems confirm the effectiveness of the method.