Семинар за рачунарство и примењену математику, 2. април 2024.

• 01. Април, 2024
• Коментари (0)

Наредни састанак Семинара биће одржан у уторак, 2. априла 2024. у сали 301ф Математичког института САНУ са почетком у 14.15.
 
Предавач: Slobodan Jelić, 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/2gamma)} )$ times optimal.

 
Напомена: Регистрациона форма за учешће на Семинару је доступна на линку:
https://miteam.mi.sanu.ac.rs/call/wnz6oyxsQsy29LfJA/MjQ__eH607WeAL9X7IFtUI98xdQQgVkp-ljiEKPPfXr

Уколико желите само да пратите предавање без могућности активног учешћа, пренос је доступан на линку:
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So