Logowanie

Języki

  • Polski
  • English

Seminarium ZOK: Mateusz Lewandowski o node-weighted prize-collecting Steiner tree problem  

W dniu 20 października 2015 (wtorek, godz. 10:15-12:00, sala 310) na seminarium Zakładu Optymalizacji Kombinatorycznej Mateusz Lewandowski przedstawi wyniki na temat Approximation algorithms for the node-weighted prize-collecting Steiner tree problem (NWPCST) on planar graphs.

Streszczenie

In the talk I will present extended results from my Master Thesis. In particular we will see the new primal-dual 3-approximation algorithm for the node-weighted prize-collecting Steiner tree problem (NWPCST) on planar graphs. We will prove that it is also Lagrangian-preserving. Our algorithm combined with a randomized rounding technique gives us the (2.87 + e)-approximation algorithm which is the best result for this problem.

Adres:
Instytut Informatyki
Uniwersytetu Wroclawskiego
ul. Joliot-Curie 15
50-383 Wroclaw
Sekretariat
tel.: 71 375 7800
tel.: 71 325 1271
fax: 71 375 7801
sekretariat@ii.uni.wroc.pl
Dziekanat
tel.: 71 375 7892
dziekan@ii.uni.wroc.pl
sprawy studenckie:
dziekanat@ii.uni.wroc.pl
Portiernia
tel.: 71 375 7958
Redaktor strony WWW
redaktor@ii.uni.wroc.pl
Projekt
MAKOS