Speaker: 李建平，云南大学

Inviter: 陈绍示，中国科学院数学机械化重点实验室

Title: Constrained bottleneck (1, 2)-assignments and related problems

Language: Chinese

Time & Venue: 2025.02.17 16:00-17:30 思源楼525

Abstract: In this talk, we address the constrained bottleneck (1, 2)-assignment (CBn2A) problem. We obtain the following four main results. (1) We can prove that it is NP-hard to find a feasible solution to solve the CBn2A problem; (2) Using algorithms to produce minimum-cost integer circulation flows on a series of auxiliary networks and to find minimum bottleneck perfect matchings on a series of auxiliary graphs, respectively, we can design two combinatorial algorithms to solve two special versions of the minmax-CBn2A problem; (3) Similar to (2), we present two combinatorial algorithms to solve two special versions of the maxmin-CBn2A problem; (4) Using shifting techniques and combinatorial algorithms in (1), we provide two combinatorial algorithms to solve two special versions of the CBBn2A problem.