-
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…
-
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…
-
Qimu Xiao: Joint cross-cell offloading and resource allocation in the multi-cell MEC network via online learning
Speaker: Qimu Xiao (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) March 24, 2023 (Friday) Venue: 518, Research Building 4 Abstract: A widely studied typical mobile edge computing (MEC) system network consists of a cloud server, some edge servers, and some user equipment, which promises a satisfactory user experience by…