Title: Approximation Algorithms for the Joint Replenishment Problem

Speaker: Marek Chrobak, University of California, Riverside

Time/Date: Friday, Mar 28, 11-12
Location: Room 3501

Abstract:

The Joint Replenishment Problem (JRP) is a classical problem in the
area of supply management, that has been extensively studied in
operations research since 1950s. It was shown to be strongly NP-hard
in late 1980s, but since then very little progress has been made in
establishing approximation bounds for JRP.

In this talk I'll survey the past work on JRP and present our new
results on approximation algorithms for JRP. In the offline case, we
give an 1.791-approximation algorithm, breaking the existing barrier
of 1.8, and we show that for the variant with linear costs, the LP
integrality gap is at least 1.09.  In the online case, we show that
the competitive ratio for JRP is at least 2.754 and we prove the
optimal ratio of 2 for the version of JRP with deadlines.

This is joint work with M. Bienkowski, J. Byrka, L. Jez, D. Nogneng
and J. Sgall.