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.

Self non self discrimination within the immune system: A view from the bridge

SCOPUS: cp.j

Nuclear ingredients for cross section calculation of exotic nuclei

The increasing need for cross sections far from the valley of stability, especially for applications such as nuclear astrophysics, poses a challenge for nuclear reaction models. So far, predictions of cross sections have relied on more or less phenomenological approaches, depending on parameters adjusted to available experimental data or deduced from systematic relations. While such predictions are expected to be reliable for nuclei not too far from the experimentally known regions, it is clearly preferable to use more fundamental approaches, based on sound physical bases, when dealing with very exotic nuclei. Thanks to the high computer power available today, all major ingredients required to model a nuclear reaction can now be (and have been) microscopically (or semi-microscopically) determined starting from the information provided by an effective nucleon-nucleon interaction. All these microscopic ingredients have been included in the latest version of the TALYS nuclear reaction code (http://www.talys.eu/).

Latest development of the combinatorial model of nuclear level densities

The combinatorial model of nuclear level densities has now reached a level of accuracy comparable to that of the best global analytical expressions without suffering from the limits imposed by the statistical hypothesis on which the latter expressions rely. In particular, it provides, naturally, non-Gaussian spin distribution as well as non-equipartition of parities which are known to have an impact on cross section predictions at low energies [1, 2, 3]. Our previous global models developed in Refs. [1, 2] suffered from deficiencies, in particular in the way the collective effects - both vibrational and rotational - were treated. We have recently improved this treatment using simultaneously the single-particle levels and collective properties predicted by a newly derived Gogny interaction [4], therefore enabling a microscopic description of energy-dependent shell, pairing and deformation effects. In addition for deformed nuclei, the transition to sphericity is coherently taken into account on the basis of a temperature-dependent Hartree-Fock calculation which provides at each temperature the structure properties needed to build the level densities. This new method is described and shown to give promising results with respect to available experimental data.

Workshop summary: Hormonal suppression in the neoadjuvant setting and advanced disease

SCOPUS: cp.j

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.