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


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


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


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:

  • 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.
    Our hardness results imply that no polynomial-time algorithm exists for either problem, unless integer factorization is solvable in polynomial time.


  •   Do you need Missouri Payday Loans as soon as possible? But at the same time, it acts only with sexual arousal. Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.