﻿ 韩国高等科学院Jeong Han Kim教授学术报告

# 韩国高等科学院Jeong Han Kim教授学术报告

报   告  人：Jeong Han Kim 教授, Korea Institute for Advanced Study (KIAS)

时         间：2019329日下午330—430

地         点：数计学院第一会议室（20-404

题         目：Entropy and Sorting

摘         要：We reconsider the old problem of sorting under partial information, and give polynomial time algorithms for the following tasks: (1) Given a partial order P, find (adaptively) a sequence of comparisons (questions of the form, "is x < y?") which sorts ( i.e., finds an unknown linear extension of) P using O(log(e(P))) comparisons in worst case (where e(P) is the number of linear extensions of P). (2) Compute (on line) answers to any comparison algorithm for sorting a partial order P which force the algorithm to use Ω(log(e(P))) comparisons. (3) Given a partial order P of size n, estimate e(P) to within a factor exponential in n. (We give upper and lower bounds which differ by the factor n^n /n!.) Our approach, based on entropy of the comparability graph of P and convex minimization via the ellipsoid method, is completely different from earlier attempts to deal with these questions. 