Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n2) algorithm performing O(log n·log e(P)) comparisons; an O(n2.5) algorithm performing at most (1+ε) log e(P) + Oε(n) comparisons; an O(n2.5) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement. © 2010 ACM.

A toolset for the analysis of et-lotos specifications

info:eu-repo/semantics/published

A simulator of real-time systems specified in et-lotos

info:eu-repo/semantics/published

Water vapor line parameters in the 13 000-9250 cm-1 region.

info:eu-repo/semantics/published

Health networks: Actors, professional relationships, and controversies

In recent years international policies have aimed to stimulate the use of information and communication technologies (ICT) in the field of health care. Belgium has also been affected by these developments and, for example, health electronic regional networks ("HNs") are established. Thanks to a qualitative case study we have explored the implementation of such innovations (HN) to better understand how health professionals collaborate through the HN and how the HN affect their relationships. Within the HNs studied a common good unites the actors: the continuity of care for a better quality of care. However behind this objective of continuity of care other individual motivations emerge. Some controversies need also to be resolved in order to achieve cooperative relationships. HNs have notably to take national developments into account. These developments raise the question of the control of medical knowledge and medical practice. Professional issues, and not only practical changes, are involved in these innovations. © 2008 The authors and IOS Press. All rights reserved.

New data inversion formulae in confocal scanning microscopy

Whereas the resolving power of an ordinary optical microscope is determined by the classical Rayleigh distance, significant super-resolution, i.e. resolution improvement beyond that Rayleigh limit, has been achieved by confocal scanning light microscopy. Furthermore is has been shown that the resolution of a confocal scanning microscope can still be significantly enhanced by measuring, for each scanning position, the full diffraction image by means of an array of detectors and by inverting these data to recover the value of the object at the focus. We discuss the associated inverse problem and show how to generalize the data inversion procedure by allowing, for reconstructing the object at a given point, to make use also of the diffraction images recorded at other scanning positions. This leads us to a whole family of generalized inversion formulae, which contains as special cases some previously known formulae. We also show how these exact inversion formulae can be implemented in practice.

UV, visible and near-IR spectroscopy of atmospheric species

info:eu-repo/semantics/published

Long-distance quantum communication just around the corner?

info:eu-repo/semantics/published

Cannibal Animal Games: A new variant of Tic-Tac-Toe

This paper presents a new partial two-player game, called the cannibal animal game, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino P (called an animal). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of P. An animal is a cannibal if Bob has a winning strategy, and a non-cannibal otherwise. This paper presents some new tools, such as the bounding strategy and the punching lemma, to classify animals into cannibals or non-cannibals. We also show that the pairing strategy works for this problem.

Gamma-rays from heavy minimal dark matter

Motivated by the Minimal Dark Matter scenario, we consider the annihilation into gamma rays of candidates in the fermionic 5-plet and scalar 7-plet representations of SU(2)L, taking into account both the Sommerfeld effect and the internal bremsstrahlung. Assuming the Einasto profile, we show that present measurements of the Galactic Center by the H.E.S.S. instrument exclude the 5-plet and 7-plet as the dominant form of dark matter for masses between 1 TeV and 20 TeV, in particular, the 5-plet mass leading to the observed dark matter density via thermal freeze-out. We also discuss prospects for the upcoming Cherenkov Telescope Array, which will be able to probe even heavier dark matter masses, including the scenario where the scalar 7-plet is thermally produced.

Efficient energy distribution in a smart grid using multi-player games

info:eu-repo/semantics/submittedForPublication

Hopf hypersurfaces in pseudo-Riemannian complex and para-complex space forms

The study of real hypersurfaces in pseudo-Riemannian complex space forms and para-complex space forms, which are the pseudo-Riemannian generalizations of the complex space forms, is addressed. It is proved that there are no umbilic hypersurfaces, nor real hypersurfaces with parallel shape operator in such spaces. Denoting by J be the complex or para-complex structure of a pseudo-complex or para-complex space form respectively, a non-degenerate hypersurface of such space with unit normal vector field N is said to be Hopf if the tangent vector field JN is a principal direction. It is proved that if a hypersurface is Hopf, then the corresponding principal curvature (the Hopf curvature) is constant. It is also observed that in some cases a Hopf hypersurface must be, locally, a tube over a complex (or para-complex) submanifold, thus generalizing previous results of Cecil, Ryan and Montiel.

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.

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.

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.