Seminar za računarstvo i primenjenu matematiku, 2. april 2024.

Naredni sastanak Seminara biće održan u utorak, 2. aprila 2024. u sali 301f Matematičkog instituta SANU sa početkom u 14.15.
 
Predavač: Slobodan Jelić, University of Belgrade, Faculty of Civil Engineering, Department of Geodesy and Geoinformatics
 
Naslov predavanja: A $(log n)$ APPROXIMATION ALGORITHM FOR NODE WEIGHTED PRIZE COLLECTING GROUP STEINER TREE PROBLEM WITH BOUNDED GROUP SIZE
 
Apstrakt: 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.

 
Napomena: Registraciona forma za učešće na Seminaru je dostupna na linku:
https://miteam.mi.sanu.ac.rs/call/wnz6oyxsQsy29LfJA/MjQ__eH607WeAL9X7IFtUI98xdQQgVkp-ljiEKPPfXr

Ukoliko želite samo da pratite predavanje bez mogućnosti aktivnog učešća, prenos je dostupan na linku:
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So


 Ostavite vaš komentar 

Komentari(0)

Nažalost nije moguće ostaviti komentar.