-
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 […]
-
Minming Li: Defending with Shared Resources on a Network
Speaker: 李閩溟 （香港城市大学) Time: 14:00-15:00 (Time in Beijing) May 15, 2023 (Thursday) Venue: 电子科技大学清水河校区四号科研楼A区518 Abstract: In this paper we consider a defending problem on a network. In the model, the defender holds a total defending resource of R, which can be distributed to the nodes of the network. The defending resource allocated to a node […]
-
Xiaohui Bei: Auction Design: from Theory to Practice
Speaker: 贝小辉 (新加坡南洋理工大学) Time: 16:20-17:20 (Time in Beijing) May 11, 2023 (Thursday) Venue: 电子科技大学清水河校区四号科研楼A区518 Abstract: As a means to facilitate efficient resource allocation, auctions are a fundamental tool in the modern economy and play a pivotal role in mechanism design theory. This talk will provide a brief introduction to auction design. We will discuss fundamental […]
-
Zhiguo Fu: 平面图上计数问题的计算复杂性分类
Speaker: 付治国 (东北师范大学) Time: 11:00-12:00 (Time in Beijing) May 8, 2023 (Monday) Venue: 电子科技大学清水河校区四号科研楼A区518 Abstract: 平面图上计数问题的计算复杂性分类探索特定框架下的计数问题是否分为如下的三类：（1）一般图上可解的问题；（2）一般图上#P-难，但在平面图上可解的问题；（3）在平面图上#P-难的问题。其中一个重要的问题是基于匹配门的全息算法对（2）中的问题是否具有通用性。本报告将介绍平面图上计数问题计算复杂性分类的进展，尤其将介绍基于匹配门的全息算法与（2）中问题的关系。 Speaker Bio: 付治国，东北师范大学信息科学与技术学院教授，博士生导师，副院长。博士毕业于吉林大学数学学院计算数学专业，美国威斯康星大学麦迪逊分校博士后。研究领域为计数问题的算法与计算复杂性，成果发表在STOC，FOCS， SODA，Information and Computation等理论计算机顶级会议和期刊。
-
Zeyu Zhang: RSGNN: A Model-agnostic Approach for Enhancing the Robustness of Signed Graph Neural Networks
Speaker: 张泽宇 (奥克兰大学) Time: 16:20-17:20 (Time in Beijing) April 28, 2023 (Friday) Venue: 电子科技大学清水河校区四号科研楼A区518 Abstract: Signed graphs model complex relations using both positive and negative edges. Signed graph neural networks (SGNN) are powerful tools to analyze signed graphs. We address the vulnerability of SGNN to potential edge noise in the input graph. Our goal is […]
-
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 […]
-
Multi-unit Auction over a Social Network
Speaker: Yuan Fang (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) April 14, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Diffusion auction is an emerging business model where a seller aims to incentivise buyers in a social network to diffuse the auction information thereby attracting potential buyers. We focus […]
-
A $(2+\epsilon)k$-vertex kernel for Edge Triangle Deletion Problem
Speaker: Yuxi Liu (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) April 7, 2023 (Friday) Venue: 518, Research Building 4 Abstract: The Edge Triangle Deletion problem asks whether we can delete at most edges from the input graph such that there is no triangle in the remaining graph. This problem […]
-
Zimo Sheng: Improved Kernels for Edge Triangle Covering Problem
Speaker: Zimo Sheng (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) March 31, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Kernelization is a concept of data preprocessing which is possible to derive upper and lower bounds on sizes of reduced instance. Edge Triangle Covering is an important NP-hard problem […]