#
Monday Lecture and Colloquium

**Monday, January 21, 2013**

Technische Universität Berlin

Institut für Mathematik

Str. des 17. Juni 136

10623 Berlin

** Lecture - 14:15**

### Andreas S. Schulz -
MIT (Cambridge, USA)

### Breaking public-key cryptosystems with inventory management

*Abstract:*

We consider the joint replenishment problem, a fundamental problem in inventory theory that is arguably the simplest extension of the famous economic order quantity model. The joint replenishment problem dates back to 1958, if not further, and it has received a great deal of attention from operations researchers, industrial engineers, and economists alike. However, its computational complexity has remained open. We show that an efficient algorithm for the joint replenishment problem would break the RSA encoding scheme, thereby providing the first mathematical evidence of the computational hardness of the joint replenishment problem.

This is joint work with Claudio Telha.

ROOM: MA 041

**Colloquium - 16:00**

###
Mohsen Rezapour - Technische Universität Berlin

### Approximation algorithms for connected facility location with buy-at-bulk
edge costs

*Abstract:*

In the connected facility location with buy-at-bulk edge costs problem we
are given a subset of clients with positive demands and a subset of
potential facilities with facility opening costs in an undirected graph
with edge lengths obeying the triangle inequality. Moreover, we are given
a set of access cable types, each with a cost per unit length and a
capacity. The cost per unit capacity decreases from small to large cables
by economies of scale. For interconnecting open facilities with each other
core cables of infinite capacity must be used. The task is to open some
facilities, connect these facilities by a core Steiner tree and construct
a network of access cables such that the capacities installed on the edges
suffice to simultaneously route the entire demand of each client to an
open facility via a single path. The objective is to minimize the total
cost of opening facilities, building the core Steiner tree among them, and
installing the access cables. In this talk, we present the first
constant-factor approximation algorithm for this problem.

This is joint work with Andreas Bley.

NEW ROOM: MA 212 (BMS)

Letzte Aktualisierung:
21.01.2013