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.

Head repositioning accuracy in patients with neck pain and asymptomatic subjects: concurrent validity, influence of motion speed, motion direction and target distance

Background: Cervicocephalic kinesthetic deficiencies have been demonstrated in patients with chronic neck pain (NP). On the other hand, authors emphasized the use of different motion speeds for assessing functional impairment of the cervical spine. Purpose: The objectives of this study were (1) to investigate the head repositioning accuracy in NP patients and control subjects and (2) to assess the influence of target distance, motion speed, motion direction and pain. Materials and methods: Seventy-one subjects (36 healthy subjects and 35 NP patients; age 30–55 years) performed the head repositioning test (HRT) at two different speeds for horizontal and vertical movements and at two different distances. For each condition, six consecutive trials were sampled. Results: The study showed the validity and reproducibility of the HRT, confirming a dysfunctional threshold of 4.5°. Normative values of head repositioning error up to 3.6° and 7.1° were identified for healthy and NP subjects, respectively. A distance of 180 cm from the target and a natural motion speed increased HRT accuracy. Repositioning after extension movement showed a significantly larger error in both groups. Intensity, duration of pain as well as pain level did not significantly alter head repositioning error. Conclusions: The assessment of proprioceptive performance in healthy and NP subjects allowed the validation of the HRT. The HRT is a simple, not expensive and fast test, easily implementable in daily practice to assess and monitor treatment and evolution of proprioceptive cervical deficits.