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

时间:2019-03-27浏览:13设置

 报   告  人: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.




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