[BK Seminar]
Discrete Analysis Seminar / 신용호 (University of Wrocław), 8월 11일, 오후2시
행사일
2025.08.11
작성일
2025.07.30
작성자
전산조교
게시글 내용
Discrete Analysis Seminar 안내드립니다. 많은 참여와 관심 부탁드립니다.
일정: Aug 11, 2025 2:00 PM -
장소: 과학관 262호
강연자: 신용호 (University of Wrocław)
강연제목: University of Wrocław
초록: A rounding scheme for set cover has served as an important component in design of approximation algorithms for the problem, and there exists an \(H_s\)-approximate rounding scheme, where \(s\) denotes the maximum subset size, directly implying an approximation algorithm with the same approximation guarantee. A rounding scheme has also been considered under some online models, and in particular, under the element arrival model used as a crucial subroutine in algorithms for online set cover, an \(O(\log s)\)-competitive rounding scheme is known [Buchbinder, Chen, and Naor, SODA 2014]. On the other hand, under a more general model, called the subset arrival model, only a simple \(O(\log n)\)-competitive rounding scheme is known, where \(n\) denotes the number of elements in the ground set. In this talk, we present an \(O(\log^2 s)\)-competitive rounding scheme under the subset arrival model, with one mild assumption that \(s\) is known upfront. Using our rounding scheme, we immediately obtain an \(O(\log^2 s)\)-approximation algorithm for multi-stage stochastic set cover, improving upon the existing algorithms [Swamy and Shmoys, SICOMP 2012; Byrka and Srinivasan, SIDMA 2018] when \(s\) is small enough compared to the number of stages and the number of elements. Joint work with Jarek Byrka (University of Wrocław).
