Tuesday, 15:15 - 15:40 h, Room: H 3021


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.


Talk 1 of the invited session Tue.3.H 3021
"New insights for old problems" [...]
Cluster 2
"Combinatorial optimization" [...]


  To apply for USA Payday Loans you don't have to seek the help of relatives or go to a bank. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Buy Levitra, but also as part of its analogs.