A talk of prof. Jeong Han Kim from Korea Institute for Advanced Study


SpeakerProf. Jeong Han Kim, (Korea Institute for Advanced Study (KIAS))

Time3 : 30 – 4 : 30 p.m., 29th(Fri.) March, 2019

PlaceRoom 404, Building 20

TitleEntropy and Sorting

Abstract: 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.

浙江师范大学离散数学研究中心版权所有 © 2018-2028
地址:浙江省金华市迎宾大道688号21幢 邮政编码:321004
联系电话:0579-82282629   电子邮箱:jcsx@zjnu.cn    管理登陆