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

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.

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.

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.

Approximation limits of linear programs (beyond hierarchies)

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^1/2-ε)-approximations for CLIQUE require LPs of size 2^nΩ(ε). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.

On the extension complexity of combinatorial polytopes

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.

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.

La notion de « qualité » des publications dans l’évaluation de la recherche et des chercheurs en sciences humaines et sociales: Le potentiel de l’Open Access pour dépasser le paradoxe des prescriptions en matière de qualité et l’ambivalence de leur perception par les chercheurs en sciences de la communication

1. Un premier apport de notre travail consiste à proposer un cadre théorique, analytique et conceptuel original, permettant d'approcher la notion de qualité des publications en SHS (sciences humaines et sociales) et en sciences de la communication de façon à la fois holistique et dynamique, en tant qu'elle fait l'objet de descriptions et de jugements multiples, émis par une diversité de parties prenantes, au sein et en dehors des milieux académiques. Pour ce faire, il s'agira de considérer la qualité dans ses différentes dimensions constitutives (approche holistique) tout en l'inscrivant dans le cadre d'évolutions tendancielles en matière de publication scientifique (approche dynamique) et en tenant compte de la qualité telle qu'elle est prescrite, souhaitée et mise en oeuvre par les différentes parties prenantes (chercheurs et entités prescriptrices, aux niveaux politique et managérial). En croisant de façon systématique ces trois approches - approche multidimensionnelle, rapport aux prescrits et aux souhaits, et étude des évolutions tendancielles -, il s’avérera possible d'évaluer l'incidence des différentes tendances en matière de publication scientifique – i.e. tendances à la massification, à l'internationalisation, à l' « exotérisation » (i.e. à l'ouverture vers le monde extérieur, au-delà des pairs), à la « gestionnarisation » (i.e. à l'usage des publications dans la gestion dela recherche et des chercheurs, en particulier en situation d'évaluation), à la commercialisation et à l' « enlignement » (i.e. à la mise en ligne, sur Internet) – ainsi que des prescriptions managériales et politiques qui les initient, les stimulent ou les prolongent à des degrés divers, sur la qualité de l'activité même de publier, et sur celle des différents types génériques et spécifiques d'objets publiés.2. En appliquant cette triple approche aux SHS et, plus particulièrement, au cas des sciences de la communication, nous montrerons comment la plupart des évolutions tendancielles qui sont discutées ici ainsi que des prescrits politiques et managériaux qui y affèrent aboutissent à valoriser principalement, en situation d'évaluation de la recherche et des chercheurs, la publication d'un grand nombre d'articles dans des revues savantes internationales de premier plan, destinés avant tout aux pairs, et à dévaloriser les publications, ouvertes à des publics plus locaux, rédigées en langue vernaculaire, ou qui se consacreraient à la résolution de problèmes de société. En particulier, à la faveur de la tendance à la « gestionnarisation » des publications, l'article de revue savante internationale de premier plan, ainsi que les citations qui lui sont faites par les seuls pairs, sont posés en indicateurs de performance de tout premier plan, « fixant » ainsi les pratiques de recherche et de publication des chercheurs. Cette « fixion » sera d'autant plus marquée que les indicateurs bibliométriques, à l'échelon national, seront intégrés à des processus de financement public de la recherche fondés sur les performances, et que, à l'échelon international, les indicateurs joueront un rôle prépondérant dans l'établissement des rankings des universités ainsi que des benchmarks des systèmes nationaux et régionaux de recherche. Pour autant, des prescriptions politiques sont également édictées, principalement au niveau européen, dans l'optique de la mise en oeuvre, au sein de l'Espace européen de la recherche et, dans une moindre mesure, de l'Espace européen de l'enseignement supérieur, d'une économie de la connaissance compétitive à l'échelon global et, plus particulièrement, d'un « mode 2 » de production des connaissances, qui insistent sur l'importance de davantage valoriser les résultats de la recherche, interdisciplinaire et coopérative, auprès de parties prenantes extra-académiques. En résulte une relation paradoxale entre la tendance à l'exotérisation de la recherche et des publications, et les prescrits de gestionnarisation des publications, ainsi qu'entre les prescriptions qui les sous-tendent respectivement.3. Or l'enquête que nous avons menée auprès des membres de trois sociétés savantes internationales en sciences de la communication montre combien les chercheurs de cette discipline ont désormais bien intégré les critères de qualité promus par les prescrits politiques et managériaux soutenant l'instauration d'une nouvelle « culture de la publication », à la croisée des tendances à la massification, à l'internationalisation et à la gestionnarisation des publications. Pour autant, des entretiens approfondis menés auprès de chercheurs en sciences de la communication actifs en Belgique francophone et néerlandophone n'en révèlent pas moins que ces derniers développent une attitude foncièrement ambivalente envers la culture du « publish or perish » et à l'égard de prescriptions qui sur-valorisent les revues savantes internationales de premier plan, en situation d'évaluation de la recherche et des chercheurs. D'une part, en effet, les chercheurs avec qui nous nous sommes entretenus estiment que la nouvelle culture de la publication joue un rôle bénéfique dans la professionnalisation et dans le développement d'une culture véritablement scientifique dans les sciences de la communication. Partant, la plupart d'entre eux développent des stratégies visant à aligner leurs pratiques de publication sur les prescrits. D'autre part, plusieurs répondants n'en regrettent pas moins le caractère réducteur de la survalorisation des revues savantes internationales de premier plan dans l'évaluation, et souhaitent qu'une plus grande diversité de types de publication soit prise en compte par les évaluateurs. Afin de concilier « qualité prescrite » et « qualité souhaitée » dans la qualité de leur activité effective de publication et dans celle des objets effectivement publiés (« qualité réelle »), il arrive dès lors à ces chercheurs de « bricoler » avec les prescriptions. Par ailleurs, la plupart des répondants, davantage cependant en FédérationWallonie-Bruxelles qu'en Flandre, où le financement public de la recherche est d'ores et déjà fondé en partie sur des indicateurs bibliométriques et revue-métriques, regrettent le manque d'explicite dans la formulation des prescriptions – ces dernières prenant régulièrement la forme de « scripts » plus indirects et/ou implicites, plutôt que de normes et de règles stricto sensu –, ainsi que l'absence de seuil quantitatif minimal à atteindre.4. Il nous semble par conséquent, dans une optique plus normative, que le dépôt systématique des différents types de publication produits par les chercheurs en SHS et en sciences de la communication sur des répertoires numériques institutionnels (Open Access Green) serait de nature à (contribuer à) résoudre le paradoxe des prescriptions en matière de « qualité prescrite », ainsi que l'ambivalence des perceptions des chercheurs en matière de « qualité souhaitée ». En effet, le dépôt des publications sur des répertoires institutionnels ouvre des opportunités inédites de renouveler la conversation savante qui se structure autour des objets publiés, au sein de la communauté argumentative (Kommunikationsgemeinschaft) des pairs, par le biais notamment de la revue par les pairs ouverte et grâce à la possibilité de commenter ad libitum les publications disséminées en Open Access. mais également en rendant les résultats de la recherche aisément accessibles et ré-utilisables par des parties prenantes extra-académiques. Les opportunités liées au dépôt des publications sur des répertoires Open Access (Green), en termes de qualité tant épistémique que pragmatiquede ces dernières, seront d'autant plus fécondes que le dépôt des travaux sur les répertoires institutionnels s'articulera à l'usage, par le chercheur, des instruments idoines, génériques ou dédiés, du Web participatif (Wikis, blogues, micro-blogues, réseaux sociaux, outils de partage de signets et de listes bibliographiques). Par ailleurs, les dépôts numériques fonctionnent désormais en tant qu'« outils de transparence », susceptibles de donner davantage de visibilité à des productions de recherche et des types de publication diversifiés. En situation d'évaluation de la recherche et des chercheurs, le recours aux dépôts institutionnels - pour autant qu'un mandat prescrive le dépôt de tous les travaux produits par les chercheurs de l'institution – permettrait aux évaluateurs de fonder leur jugement sur une gamme plus large et plus représentative de types de publication et de formes de communication en SHS et en sciences de la communication. De plus, grâce à la dissémination en Open Access, en conjonction avec l'usage d'une diversité d'outils du Web participatif, il devient mieux possible de soumettre les différents types de publication archivés et publiés en libre accès à des indicateurs de performance eux-mêmes diversifiés – bibliométriques, mais également « webométriques » et « altmétriques » -, fondés sur les articles plutôt que sur les revues et mieux adaptés à la diversité de leurs impacts, tant au sein qu'en dehors du cercle des pairs.5. Partant, l'Open Access (Green) nous apparaît in fine comme étant doté d'un potentiel important, en matière d'intégration de la recherche et des chercheurs en SHS et en sciences de la communication à la mise en place – au-delà d'une économie de la connaissance - d'une véritable société de la connaissance, ainsi qu'aux processus d'innovation techno-industrielle, sociale et intellectuelle qui la sous-tendent.