-
Approximation Algorithms for the Traveling Tournament Problem with Maximum Tour Length Two
Speaker: Jingyang Zhao (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) May 07, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/smb8sodAC9nv ID: 559 715 185 Venue: Main Building Abstract: The Traveling Tournament Problem is a complex combinatorial optimization problem in tournament timetabling, which asks us to design a double […]
-
Efficient Reductions and a Fast Algorithm of Maximum Weighted Independent Set
Speaker: Sen Huang (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) April 23, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/XOBiQORlo9f9 ID: 860 317 588 Venue: B1-514, Main Building Abstract: The maximum independent set problem is one of the most fundamental problems in graph algorithms and has been widely […]
-
Constant Approximating k-Clique is W[1]-hard
Speaker: Bingkai Lin(Nanjing University) Time: 10:00-11:00 (Time in Beijing) April 20, 2021 (Tuesday) VooVmeeting: ZOOM ID: 467 156 1455 Password: 图灵机被提出的年份（4位） Bilibili Live: http://live.bilibili.com/22528138 Abstract: Deciding whether a graph contains a -Clique is a well-known NP-hard problem. One approach to dealing with NP-hard problem is approximation algorithm. However, assuming NP P , no polynomial time […]
-
Mathematical Principles of Information Sciences, II: Mathematical Theory of Intuitive Reasoning
Speaker: Angsheng Li(Beihang University) Time: 14:00-15:00 (Time in Beijing) 18:00-19:00 (Time in Auckland) April 9, 2021 (Friday) Venue: B1-501, Main Building Abstract: Started at Hilbert’s 1900 program of axiomatizing mathematics, in 1930s, mathematicians including Gödel proposed the definition of “proof” and established the subject of mathematical logic, and more importantly, Turing 1936 proposed a mathematical […]
-
An Experimental Study of the Feedback Arc Set Problem
Speaker: Ziliang Xiong(University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) April 9, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/4780kEVEoRgF ID: 381 139 951 Venue: B1-514, Main Building Abstract: Given a digraph, the minimum feedback arc set problem asks to find the smallest arc set whose removal makes the […]
-
Mathematical Principles of Information Sciences, I: The Laws of Information
Speaker: Angsheng Li(Beihang University) Time: 11:00-12:00(Time in Beijing) 15:00-16:00(Time in Auckland) April 8, 2021 (Thursday) Venue: Coffee Beanery (宾诺咖啡) Abstract: Shannon 1945 and 1948 started the mathematical studies of cryptography and of communication, respectively. In 1945,Shannon proposed an information theoretical protocol for data security, leading to the mathematical theory of data security. In 1948, Shannon […]
-
Random sampling in social network auction
Speaker: Yuchao Song(University of Electronic and Science Technology of China) Time: 10:00AM(Time in Beijing) 3:00PM(Time in Auckland) April 2, 2021 (Friday) Address: Online meeting VooVmeeting: ID: 425 826 163 Password: 1949 Link: https://meeting.tencent.com/s/OWsH2L3tXfss Abstract: We will introuduce the problem of auction design with budget and network structure, that is, auction information can be transmitted by […]
-
Random sampling in auction with budget
Speaker: Yuchao Song(University of Electronic and Science Technology of China) Time: 10:00AM(Time in Beijing) 3:00PM(Time in Auckland) March 26, 2021 (Friday) Address: Online meeting VooVmeeting: ID: 384 982 466 Password: 1949 Link: https://meeting.tencent.com/s/4UNWqmJBGY2s Abstract: In addition to reviewing the last classical random sampling auctions, we will introuduce the problem of auction with budget which buyers […]
-
How fast can we solve NP-complete problems?
Speaker: Mingyu Xiao(University of Electronic Science and Technology of China) Host Institute for Interdisciplinary Information Sciences, Tsinghua University Time: 2021-03-22 16:00-2021-03-22 17:00 Address: Tsinghua University FIT1-222 Abstract: Under the hypothesis P != NP, NP-complete problems cannot be solved in polynomial time. Under ETH, the SAT problem (the first NP-complete problem) cannot be solved in sub-exponential […]
-
Random sampling in auction
Speaker: Yuchao Song(University of Electronic and Science Technology of China) Time: 10:00AM(Time in Beijing) 3:00PM(Time in Auckland) March 19, 2021 (Friday) Address: Online meeting VooVmeeting: ID: 212 396 556 Password: 1949 Link: https://meeting.tencent.com/s/ZPP7b2ZIpUlL Abstract: Random sampling is a common technique in statistics. It is a common application to obtain the estimation of the overall distribution […]