Наредни састанак Семинара биће одржан у уторак, 2. априла 2024. у сали 301ф Математичког института САНУ са почетком у 14.15.
Предавач: Слободан Јелић, University of Belgrade, Faculty of Civil Engineering, Department of Geodesy and Geoinformatics
Наслов предавања: A log(n) APPROXIMATION ALGORITHM FOR NODE WEIGHTED PRIZE COLLECTING GROUP STEINER TREE PROBLEM WITH BOUNDED GROUP SIZE
Апстракт: In this paper, we present a randomized rounding algorithm for node weighted prize collecting group Steiner tree problem where the group size is upper bounded by a constant $\gamma$. First, we propose an $O(\log n)$-approximation algorithm for a node weighted group Steiner tree problem with the bounded group size. To solve prize collecting version of the problem, the subset of groups $\mathcal{G}’$ is selected by applying a randomized rounding technique to the solution of the natural cut-based solution of the problem. The expected cost of the group Steiner tree on $\mathcal{G}’$ is proved to be at most $1/(1-e^ {(-1/2\gamma)} )$ times optimal.
Напомена: Регистрациона форма за учешће на Семинару је доступна на линку:
https://miteam.mi.sanu.ac.rs/call/wnz6oyxsQsy29LfJA/MjQ__eH607WeAL9X7IFtUI98xdQQgVkp-ljiEKPPfXr
Уколико желите само да пратите предавање без могућности активног учешћа, пренос је доступан на линку:
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So