The Library
Approximation algorithms for the joint replenishment problem with deadlines
Tools
Bienkowski, M., Byrka, J., Chrobak, M., Dobbs, N., Nowicki, T., Sviridenko, Maxim , Świrszcz, G. and Young, N. E. (2013) Approximation algorithms for the joint replenishment problem with deadlines. In: Freivalds, Rūsiņš and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , David, (eds.) Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I. Lecture Notes in Computer Science, Volume 7965 . Berlin ; London: Springer Berlin Heidelberg, pp. 135-147. ISBN 9783642392054
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-39206-1_12
Abstract
The Joint Replenishment Problem (JRP) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods over time from a supplier to retailers. Over time, in response to demands at the retailers, the supplier sends shipments, via a warehouse, to the retailers. The objective is to schedule shipments to minimize the sum of shipping costs and retailers' waiting costs. We study the approximability of JRP with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of 1.207, and an upper bound and approximation ratio of 1.574. The best previous upper bound and approximation ratio was 1.667; no lower bound was previously published. For the special case when all demand periods are of equal length we give an upper bound of 1.5, a lower bound of 1.2, and show APX-hardness.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
Place of Publication: | Berlin ; London | ||||
ISBN: | 9783642392054 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I | ||||
Editor: | Freivalds, Rūsiņš and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , David | ||||
Official Date: | 2013 | ||||
Dates: |
|
||||
Volume: | Volume 7965 | ||||
Page Range: | pp. 135-147 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Description: | |||||
Title of Event: | 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 | ||||
Type of Event: | Other | ||||
Location of Event: | Riga, Latvia | ||||
Date(s) of Event: | 8-12 July 2013 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |