Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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.


Letzte Aktualisierung: 21.01.2013