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.

Quality of care for cancer patients on home parenteral nutrition: Development of key interventions and outcome indicators using a two-round Delphi approach

Purpose: Clear recommendations on how to guide patients with cancer on home parenteral nutrition (HPN) are lacking as the use of HPN in this population remains a controversial issue. Therefore, the aims of this study were to rank treatment recommendations and main outcome indicators to ensure high-quality care and to indicate differences in care concerning benign versus malignant patients. Methods: Treatment recommendations, identified from published guidelines, were used as a starting point for a two-round Delphi approach. Comments and additional interventions proposed in the first round were reevaluated in the second round. Ordinal logistic regression with SPSS 2.0 was used to identify differences in care concerning benign versus malignant patients. Results: Twenty-seven experts from five European countries completed two Delphi rounds. After the second Delphi round, the top three most important outcome indicators were (1) quality of life (QoL), (2) incidence of hospital readmission and (3) incidence of catheter-related infections. Forty-two interventions were considered as important for quality of care (28/42 based on published guidelines; 14/42 newly suggested by Delphi panel). The topics 'Liver disease' and 'Metabolic bone disease' were considered less important for cancer patients, together with use of infusion pumps (p = 0.004) and monitoring of vitamins and trace elements (p = 0.000). Monitoring of QoL is considered more important for cancer patients (p = 0.03). Conclusion: Using a two-round Delphi approach, we developed a minimal set of 42 interventions that may be used to determine quality of care in HPN patients with malignancies. This set of interventions differs from a similar set developed for benign patients. © 2012 Springer-Verlag Berlin Heidelberg.

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.

Covering Partial Cubes with Zones

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p31