[日時] 2023年10月20日(金) 12:20--14:20
[場所] 東京大学 本郷キャンパス 工14号館 534室
[講演者] 隈部 壮 (東京大学)
[題目(title)] Lipschitz Continuous Optimization Algorithms
[概要(Abstract)] Combinatorial algorithms are widely used for decision-making and knowledge discovery, and it is important to ensure that their output remains stable even when subjected to small perturbations in the input. Failure to do so can lead to several problems, including costly decisions, reduced user trust, potential security concerns, and lack of replicability. Unfortunately, many fundamental combinatorial algorithms are vulnerable to small input perturbations.In this study, we consider the Lipschitz continuity of algorithms as a stability measure and initiate a systematic study of the Lipschitz continuity of algorithms for (weighted) optimization problems. Specifically, we provide Lipschitz continuous algorithms for the minimum spanning tree problem, the shortest path problem, the maximum weight matching problem, the minimum weight vertex cover problem, the minimum weight set cover problem, and the minimum weight feedback vertex set problem.