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.

Examining Relationships between Culture, Creativity and Business Stage in an Emerging Market: A Categorical Data Analysis of Vietnam’s Data Set

In this article, we offer a new way of exploring relationships between three different dimensions of a business operation, namely the stage of business development, the methods of creativity and the major cultural values. Although separately, each of these has gained enormous attention from the management research community, evidenced by a large volume of research studies, there have been not many studies that attempt to describe the logic that connect these three important aspects of a business; let alone empirical evidences that support any significant relationships among these variables. The paper also provides a data set and an empirical investigation on that data set, using a categorical data analysis, to conclude that examinations of these possible relationships are meaningful and possible for seemingly unquantifiable information. The results also show that the most significant category among all creativity methods employed in Vietnamese enterprises is the “creative disciplines” rule in the “entrepreneurial phase,” while in general creative disciplines have played a critical role in explaining the structure of our data sample, for both stages of development in our consideration.

The Fantasio set-up: High resolution overtone spectroscopy of acetylene containing van der Waals dimers

info:eu-repo/semantics/nonPublished

15N NMR relaxation data reveal significant chemical exchange broadening in the alpha-domain of human α-lactalbumin

Human alpha-lactalbumin (alpha-LA), a 123-residue calcium-binding protein, has been studied using (15)N NMR relaxation methods in order to characterize backbone dynamics of the native state at the level of individual residues. Relaxation data were collected at three magnetic field strengths and analyzed using the model-free formalism of Lipari and Szabo. The order parameters derived from this analysis are generally high, indicating a rigid backbone. A total of 46 residues required an exchange contribution to T(2); 43 of these residues are located in the alpha-domain of the protein. The largest exchange contributions are observed in the A-, B-, D-, and C-terminal 3(10)-helices of the alpha-domain; these residues have been shown previously to form a highly stable core in the alpha-LA molten globule. The observed exchange broadening, along with previous hydrogen/deuterium amide exchange data, suggests that this part of the alpha-domain may undergo a local structural transition between the well-ordered native structure and a less-ordered molten-globule-like structure.

FANTASIO: a versatile experimental set-up to investigate jet-cooled molecules

The design of a new apparatus, named FANTASIO, for studying jet-cooled molecules is described. It includes, around the same supersonic expansion cell, a high resolution Fourier transform spectrometer with single or multipass optics, a tunable diode laser spectrometer with optional cavity ring-down facilities, and a quadrupole mass spectrometer. Performance and operational procedures are illustrated.