-
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 […]
-
Yan Gu:Introduction to Parallel Algorithms
Speaker: Yan Gu（University of California, Riverside) Time: 10:20-11:20 (Time in Beijing) September 8, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Parallel processors are ubiquitous nowadays and it is almost impossible to find a single-core processor, probably other than a toaster. However, very few courses and online materials cover the basic knowledge for designing parallel […]
-
Yiding Feng: Mobility Data in Operations: The Facility Location Problem
Speaker: Yiding Feng（University of Chicago) Time: 11:00-12:00 (Time in Beijing) August 4, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Yiding Feng is a postdoctoral principal researcher at the University of Chicago Booth School of Business. Previously, he worked as a postdoctoral researcher at Microsoft Research New England from 2021 to 2023. He […]
-
Louxin Zhang: A Scalable Algorithm for Inferring Phylogenetic Networks from Trees
Speaker: Louxin Zhang （新加坡国立大学） Time: July 3, 2023 (Monday) 10:30-11:30am Venue: 电子科技大学清水河校区主楼B1-501 Abstract: Phylogenetic networks are rooted, acyclic directed graph in which leaves are labelled with genes, genomes or species. They are used to model evolution with reticulate events. The reconstruction of phylogenetic networks is an important but challenging problem in phylogenetics and genome evolution, […]
-
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 […]
-
Yixin Cao: Enumerating Maximal Induced Subgraphs
Speaker: 操宜新 （香港城市大学) Time: 15:00-16:00 (Time in Beijing) May 15, 2023 (Thursday) Venue: 电子科技大学清水河校区四号科研楼A区518 Abstract: Given a graph $G$, the maximal induced subgraphs problem asks to enumerate all maximal induced subgraphs of $G$ that belong to a certain hereditary graph class. While its optimization version, known as the minimum vertex deletion problem in literature, has […]