-
Zihui Liang: Connectivity in the presence of an opponent
Speaker: Zihui Liang (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) October 20, 2023 (Friday) Venue: 518, Research Building 4 Abstract: The paper introduces two player connectivity games played on finite bipartite graphs. Algorithms that solve these connectivity games can be used as subroutines for solving M\”uller games. M\”uller games […]
-
Kangyi Tian: Parameterized Algorithms for Cluster Vertex Deletion on Degree-4 Graphs and General Graphs
Speaker: Kangyi Tian (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) October 13, 2023 (Friday) Venue: 518, Research Building 4 Abstract: In the Cluster Vertex Deletion problem, we are given a graph G and an integer k, and the goal is to determine whether we can delete at most k […]
-
Haidong Yang: Topological network-control games
Speaker: Haidong Yang (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) September 22, 2023 (Friday) Venue: 518, Research Building 4 Abstract: The paper introduces new combinatorial games, called topological network-control games, played on graphs. These games model the influence of competing two parties aiming to control a given network. In […]
-
Pengpeng Wang: 基于树割映射的网络健壮性增强算法
Speaker: Pengpeng Wang（Henan University of Technology) Time: 16:20-17:20 (Time in Beijing) September 15, 2023 (Friday) Venue: 518, Research Building 4 Abstract: 在大型稀疏网络中，少数几条边的随机故障可能导致网络断开，为了提高网络健壮性，可以选择性的保护特定边从而使整个网络的连通性保持到一定水平，然而资源总是有限的，不可能保护所有的边。我们设计了一种快速的算法，即通过深度遍历树快速定位到较小的割，并对这些割的边进行有选择性的保护，从而提高网络健壮性，传统算法利用线性规划，时间较慢，并且不能适用于大型网络，实验表明我们的算法能够抵御 99.99%的随机故障，有较好的加速效果。 Speaker Bio: 汪鹏鹏现就读于河南工业大学信息科学与工程学院，研究方向为最小割，网络健壮性，稀疏割算法等。
-
Yan Gu:Recent Advances in Parallel Algorithm Design
Speaker: Yan Gu（University of California, Riverside) Time: 16:20-17:20 (Time in Beijing) September 8, 2023 (Friday) Venue: 518, Research Building 4 Abstract: This talk will cover some new advances in recent parallel algorithm research. We will introduce a few new parallel algorithms on classic graph problems such as single-source shortest paths (the rho-stepping and the delta*-stepping […]
-
Chao Xu: Matroid Base with Congruency Constraint
Speaker: Chao Xu (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) June 9, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Let $k$ be an integer and $M$ a matroid on groundset $E$.There is a label function $\ell:E\to [k]$ that assigns a label to all elements. We aim to identify […]
-
Yuhang Guo: Characterization of Monotonic Allocation in Multi-unit Diffusion Auction
Speaker: Yuhang Guo (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) June 2, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Designing strategyproof mechanisms in multi-unit diffusion auctions has posed a significant challenge, as each agent’s allocation and price can be easily influenced by their invitees and siblings. In our […]
-
Yuyang Zhuge, Xiaoyang Gong: Automatic Structures
Speaker: Yuyang Zhuge, Xiaoyang Gong(University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) May 26, 2023 (Friday) Venue: 518, Research Building 4 Abstract: We introduce automatic structures. We provide examples and discuss several research directions. One direction of research is the isomorphism problem. The problem asks to design an algorithm that […]
-
Yu Cong: Trade-off Curve Computation for Incentive Allocation
Speaker: Yu Cong (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) May 19, 2023 (Friday) Venue: 518, Research Building 4 Abstract: We consider a large-scale incentive allocation problem where the entire trade-off curve between budget and profit has to be maintained approximately at all time. The application originally comes from […]
-
Zibo Zhou: Two-dimensional irregular bin packing problem
Speaker: Zibo Zhou (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) April 21, 2023 (Friday) Venue: 518, Research Building 4 Abstract: We proposes a local search combined with DJD heuristic approach for the two-dimensional irregular bin packing problem (2DIBPP) with limited rotations. The objective of 2DIBPP is to pack a […]