{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:28Z","timestamp":1759638628113},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p> The objective of the classical Joint Replenishment Problem (JRP) is to minimize ordering costs by combining orders in two stages, first at some retailers, and then at a warehouse. These orders are needed to satisfy demands that appear over time at the retailers. We investigate the natural special case that each demand has a deadline until when it needs to be satisfied. For this case, we present a randomized 5\/3-approximation algorithm. We moreover prove that JRP with deadlines is APX-hard. Finally, we extend the known hardness results by showing that JRP with linear delay cost functions is NP-hard, even if each retailer has to satisfy only three demands. <\/jats:p>","DOI":"10.1142\/s1793830909000130","type":"journal-article","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T11:53:30Z","timestamp":1246535610000},"page":"153-173","source":"Crossref","is-referenced-by-count":11,"title":["APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES"],"prefix":"10.1142","volume":"01","author":[{"given":"TIM","family":"NONNER","sequence":"first","affiliation":[{"name":"Department of Computer Science, Albert Ludwigs University of Freiburg, Georges-K\u00f6hler-Allee 79, 79110 Freiburg im Breisgau, Germany"}]},{"given":"ALEXANDER","family":"SOUZA","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Albert Ludwigs University of Freiburg, Georges-K\u00f6hler-Allee 79, 79110 Freiburg im Breisgau, Germany"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1108\/eb054814"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90001-1"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367074"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2002.1221"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1051\/ro:2007024"},{"key":"rf10","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","volume":"57","author":"Golumbic M. C.","year":"2004"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.2.279"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.03.007"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90011-K"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.2.262"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.3.486"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830909000130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:57:52Z","timestamp":1565193472000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830909000130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":12,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1142\/S1793830909000130"],"URL":"https:\/\/doi.org\/10.1142\/s1793830909000130","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}