Approximation algorithms for replenishment problems with fixed turnover times

Thomas Bosman*, Martijn van Ee, Yang Jiao, Alberto Marchetti-Spaccamela, R. Ravi, Leen Stougie

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

15 Downloads (Pure)


We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places; at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

Original languageEnglish
Title of host publicationLATIN 2018: Theoretical Informatics
Subtitle of host publication13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings
EditorsMichael A. Bender, Martin Farach-Colton, Miguel A. Mosteiro
Number of pages14
ISBN (Electronic)9783319774046
ISBN (Print)9783319774039
Publication statusPublished - 2018
Event13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 - Buenos Aires, Argentina
Duration: 16 Apr 201819 Apr 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10807 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference13th International Symposium on Latin American Theoretical Informatics, LATIN 2018
CityBuenos Aires


Acknowledgments. The research of YJ and RR is supported in part by the U. S. National Science Foundation under award numbers CCF-1527032 and CCF-1655442. The research of MvE was done while he was employed by Vrije Universiteit Amsterdam.

FundersFunder number
U. S. National Science Foundation
National Science FoundationCCF-1527032, CCF-1655442


    Dive into the research topics of 'Approximation algorithms for replenishment problems with fixed turnover times'. Together they form a unique fingerprint.

    Cite this