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.

Incidence of febrile neutropenia and neutropenic infections in elderly patients receiving anthracycline-based chemotherapy for breast cancer without primary prophylaxis with colony-stimulating factors

There is concern about the potential increase of hematological toxicity in elderly patients treated with chemotherapy. Recently, primary prophylaxis with colony-stimulating factors (CSFs) was proposed for elderly patients receiving moderately toxic chemotherapy. However, evidence for the benefits of this primary prophylaxis for elderly breast cancer patients is currently lacking. We retrospectively analyzed the incidence of febrile neutropenia (FN) and neutropenic infections in elderly breast cancer patients receiving anthracycline-based chemotherapy without primary prophylaxis with colony-stimulating factors. In addition, we assessed the direct costs of hospitalization for these complications. Febrile neutropenia or neutropenic infection occurred in 13% of the 46 patients. Further studies are needed to adequately evaluate the risk of neutropenic complications (NC) in elderly patients receiving standard-dose chemotherapy for breast cancer and the potential benefits of primary prophylaxis with colony-stimulating factors. © 2004 Elsevier Ireland Ltd. All rights reserved.