-
A Fast Algorithm for SAT in Terms of Formula Length
Speaker: Junqiang Peng (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) June 4, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/2p05iZpS1RvT ID: 973 577 922 Password: 1949 Venue: Main Building Abstract: The CNF satisfiability problem is defined as follows: given a CNF formula , decide if there exists a […]
-
Score aggregation in social choice
Speaker: Mingyu Xiao (University of Electronic and Science Technology of China) Time: 9:00-12:00 May 29, 2021 (Saturday) VooVmeeting: ZOOM Conference ID: 748 677 4340 Venue: Lotus Room, Orient Hotel Xi’an Abstract: In a score aggregation system, several agents give scores to a set of candidates independently, and we are going to combine the individual scores […]
-
Random Sampling of Important Separators: New Bounds and New Applications
Speaker: Huairui Chu (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) May 28, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/xtCxnutcKyYJ ID: 447 185 012 Password: 1949 Venue: Main Building Abstract: Important separator is a well-known concept for solving problems about graphs in parameterized algorithm sense. Marx and Razgon […]
-
Kernelization for Feedback Vertex Set based on linear programming
Speaker: Tian Bai (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) May 21, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/QfT7QuGrXPBQ ID: 582 848 199 Password: 1949 Venue: Main Building Abstract: Feedback Vertex Set (FVS) is a problem to determine whether a given undirected graph has a vertex set […]
-
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 […]