## Invited Session Tue.3.H 3021

#### Tuesday, 15:15 - 16:45 h, Room: H 3021

**Cluster 2: Combinatorial optimization** [...]

### New insights for old problems

**Chair: Andreas S. Schulz**

**Tuesday, 15:15 - 15:40 h, Room: H 3021, Talk 1**

**Gautier Stauffer**

A simple and fast 2-approximation algorithm for the one-warehouse multi-retailer problem

**Coauthors: Jean-Philippe Gayon, Guillaume Massonnet, Christophe Rapine**

**Abstract:**

In the One-Warehouse Multi-Retailer (OWMR) problem, we want to optimize the distribution of a single item over a network composed of one warehouse and *N* different retailers over a discrete finite planning horizon of *T* periods. Each retailer is facing deterministic demands that have to be fulfilled on time by ordering those units from the warehouse, which in turn have to be ordered from an external supplier of infinite capacity. The objective of the OWMR problem is to find a planning for the orders at each location (i.e., period and quantity) that minimizes the sum of the fixed ordering costs and holding costs in the system. The cost of ordering is fixed, independent of the number of products, while a per-unit holding cost is paid at each location to keep an item in stock. This problem is NP-hard but efficient *1.8*- and *2*-approximation algorithms have been proposed in the literature. The corresponding algorithms are based on sophisticated LP techniques (randomized rounding and primal dual). In this talk we present a simple *2*-approximation algorithm that is purely combinatorial and that can be implemented to run in linear time.

**Tuesday, 15:45 - 16:10 h, Room: H 3021, Talk 2**

**Danny Segev**

An approximate dynamic-programming approach to the joint replenishment problem

**Abstract:**

In this talk, I will present a high-level view of a very recent approach for *ε*-approximating the joint replenishment problem, with stationary demands and holding costs. Based on synthesizing ideas such as commodity aggregation, approximate dynamic programming, and a few guessing tricks, it turns out that one can attain any required degree of accuracy in time *O((nT)*^{O(log log T)}), where *n* denotes the number of given commodities, and *T* stands for the number of time periods.

**Tuesday, 16:15 - 16:40 h, Room: H 3021, Talk 3**

**Andreas S. Schulz**

The joint replenishment problem and the problem of clustering frequency-constrained maintenance jobs are integer-factorization hard

**Coauthor: Claudio Telha Cornejo**

**Abstract:**

We present a new connection between certain sequencing problems

involving the coordination of activities and the problem of integer factorization. We use this connection to derive hardness results for three well-known problems in operations management whose computational complexity has been open for more than two decades:

\begin{compactitem}[-]

The joint replenishment problem with general integer policies.

The joint replenishment problem with correction factor.

The problem of finding an optimal clustering of frequency-constrained maintenance jobs.

\end{compactitem}

Our hardness results imply that no polynomial-time algorithm exists for either problem, unless integer factorization is solvable in polynomial time.