Showing math.COShow all
3 papers · 1 filter
math.CO2002
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*…
math.CO2002
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…
math.CO2002
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…