Asymmetric polygons with maximum area

We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given n diameters of a circle and a positive integer k < n, this paper addresses the problem of computing a maximum area asymmetric k-gon having as vertices k < n endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.

Classic Nintendo games are (computationally) hard

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros.1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.

Insufficient Evidence of Jatropha curcas L. Invasiveness: Experimental Observations in Burkina Faso, West Africa

Biofuel plants such as Jatropha curcas L. have potential to support the livelihoods of rural communities and contribute to sustainable rural development in Africa, if risks and uncertainties are minimized. Yet, recent papers have warned of the risk of biological invasions in such tropical regions as a consequence of the introduction of exotic biofuel crops. We investigated the seed dispersal risk and invasiveness potential of both J. curcas monoculture plantations and live fences into adjacent cultivated and uncultivated land use systems in Sissili province, Burkina Faso. Invasiveness potential was assessed through (i) detecting evidence of natural regeneration in perimeters around J. curcas plantations and live fences, (ii) assessing seed dispersal mechanisms, and (iii) assessing seedling establishment potential through in situ direct seed sowing. Spontaneous regeneration around the plantation perimeters of the three sites was very low. Individual seedling density around J. curcas live fences was less than 0.01 m⁻² in all sites. Seventy percent of the seedlings were found close to the live fence and most of them derived from the same year (96 %), which indicates low seed-bank longevity and seedling survival. J. curcas can be dispersed by small mammals and arthropods, particularly rodents and ants. In some sites, such as in Onliassan, high secondary seed dispersal by animals (up to 98 %) was recorded. There were highly significant differences in germination rates between seeds at the soil surface (11 %) and those buried artificially at 1–2-cm depth (64 %). In conclusion, we failed to find convincing evidence of the spreading of J. curcas or any significant impact on the surrounding environment.

Comments on: Static and dynamic source locations in undirected networks

SCOPUS: ed.j

Extended formulations, nonnegative factorizations, and randomized communication protocols

An extended formulation of a polyhedron P is a linear description of a polyhedron Q together with a linear map π such that π(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix S. Moreover, Yannakakis also shows that the nonnegative rank of S is at most 2^c, where c is the complexity of any deterministic protocol computing S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope P equals the minimum complexity of a randomized communication protocol computing the slack matrix of P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.