-
Some efficient algorithms for the k-vertex cover problem
Speaker: Yijia Chen(Shanghai Jiao Tong University) Time: 11:00-12:00 (Time in Beijing) 15:00-16:00 (Time in Auckland) May 20, 2021 (Thursday) Venue: B1-501, Main Building Abstract: Let be a fixed constant. The -vertex cover problem asks, for an input graph , whether contains vertices which intersect every edge in . The problem has been studied extensively both […]
-
Kernels for Planar Vertex-Disjoint Triangle Packing
Speaker: Zimo Sheng (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) May 14, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/oLdo3h9nEQlW ID: 655 461 488 Venue: Main Building Abstract: Triangle Packing is an important class of NP-hard problem. In this paper, we study Parameterized Planar Vertex-Disjoint Triangle Packing problem, […]
-
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 […]