Logowanie

Języki

  • Polski
  • English

Seminarium ZOK: Bartosz Rybicki o An approximation algorithm for Uniform Capacitated k-Median problem with 1+ε capacity violation.  

W dniu 1 grudnia 2015 (wtorek, godz. 10:15-12:00, sala 310) na seminarium Zakładu Optymalizacji Kombinatorycznej Bartosz Rybicki przedstawi wyniki na temat An approximation algorithm for Uniform Capacitated k-Median problem with 1+ε capacity violation.

Streszczenie

We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the standard LP-relaxation can only be used for algorithms violating one of the two by a factor of at least two, Shi Li [SODA’15, SODA’16] gave algorithms violating the number of facilities by a factor of 1 + ε exploring properties of extended relaxations. In this paper we develop a constant factor approximation algorithm for Uniform Capacitated k-Median violating only the capacities by a factor of 1 + ε. The algorithm is based on a configuration LP. Unlike in the algorithms violating the number of facilities, we cannot simply open extra few facilities at selected locations. Instead, our algorithm decides about the facility openings in a carefully designed dependent rounding process.

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