4 papers
The asymptotic complexity of partial sorting -- How to learn large posets by pairwise comparisons
Jobst Heitzig
The expected number of pairwise comparisons needed to learn a partial order on n elements is shown to be at least n*n/4-o(n*n), and an algorithm is given that needs only n*n/4+o(n*…
A Characterization of Similarity Maps Between Euclidean Spaces Related to the Beckman--Quarles Theorem
Jobst Heitzig
It is shown that each continuous transformation from Euclidean -space () into Euclidean -space that preserves the equality of distances (that is, fulfils the implica…
Qualitative Visualization of Distance Information
Jobst Heitzig
Different types of two- and three-dimensional representations of a finite metric space are studied that focus on the accurate representation of the linear order among the distances…
Social Choice Under Incomplete, Cyclic Preferences
Jobst Heitzig
Actual individual preferences are neither complete (=total) nor antisymmetric in general, so that at least every quasi-order must be an admissible input to a satisfactory choice ru…