IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v68y2020i1p214-232.html
   My bibliography  Save this article

Online Algorithms for Multilevel Aggregation

Author

Listed:
  • Marcin Bienkowski

    (Institute of Computer Science, University of Wrocław, 50-137 Wrocław, Poland)

  • Martin Böhm

    (CSLog, University of Bremen, 28359 Bremen, Germany, Computer Science Institute, Charles University, 118 00 Prague, Czech Republic)

  • Jaroslaw Byrka

    (Institute of Computer Science, University of Wrocław, 50-137 Wrocław, Poland)

  • Marek Chrobak

    (Department of Computer Science, University of California, Riverside, Riverside, California 92521)

  • Christoph Dürr

    (Laboratoire d’Informatique de Paris 6, Sorbonne Université, Centre National de la Recherche Scientifique, 75252 Paris, France)

  • Lukáš Folwarczný

    (Computer Science Institute, Charles University, 118 00 Prague, Czech Republic, Institute of Mathematics, Czech Academy of Sciences, 110 00 Prague, Czech Republic)

  • Łukasz Jeż

    (Institute of Computer Science, University of Wrocław, 50-137 Wrocław, Poland)

  • Jiří Sgall

    (Computer Science Institute, Charles University, 118 00 Prague, Czech Republic)

  • Nguyen Kim Thang

    (Laboratoire Informatique, Bio-informatique et Systèmes Complexes, Université d’Evry Val d’Essonne, 91034 Evry, France)

  • Pavel Veselý

    (Computer Science Institute, Charles University, 118 00 Prague, Czech Republic, Department of Computer Science, University of Warwick, CV4 7AL Coventry, United Kingdom)

Abstract

In the multilevel aggregation problem (MLAP), requests arrive at the nodes of an edge-weighted tree T and have to be served eventually. A service is defined as a subtree X of T that contains the root of T . This subtree X serves all requests that are pending in the nodes of X , and the cost of this service is equal to the total weight of X . Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the Transmission Control Protocol acknowledgment problem, whereas for trees of depth 2, it is equivalent to the joint replenishment problem. Aggregation problems for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and supply chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant-competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant-competitive online algorithm for trees of arbitrary (fixed) depth. The competitive ratio is O ( D 4 2 D ) , where D is the depth of T . The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.

Suggested Citation

  • Marcin Bienkowski & Martin Böhm & Jaroslaw Byrka & Marek Chrobak & Christoph Dürr & Lukáš Folwarczný & Łukasz Jeż & Jiří Sgall & Nguyen Kim Thang & Pavel Veselý, 2020. "Online Algorithms for Multilevel Aggregation," Operations Research, INFORMS, vol. 68(1), pages 214-232, January.
    • Handle: RePEc:inm:oropre:v:68:y:2020:i:1:p:214-232
    DOI: 10.1287/opre.2019.1847
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2019.1847
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2019.1847?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Retsef Levi & Robin Roundy & David Shmoys & Maxim Sviridenko, 2008. "A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem," Management Science, INFORMS, vol. 54(4), pages 763-776, April.
    2. Wallace B. Crowston & Michael H. Wagner, 1973. "Dynamic Lot Size Models for Multi-Stage Assembly Systems," Management Science, INFORMS, vol. 20(1), pages 14-21, September.
    3. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    4. Alok Aggarwal & James K. Park, 1993. "Improved Algorithms for Economic Lot Size Problems," Operations Research, INFORMS, vol. 41(3), pages 549-571, June.
    5. Retsef Levi & Robin O. Roundy & David B. Shmoys, 2006. "Primal-Dual Algorithms for Deterministic Inventory Problems," Mathematics of Operations Research, INFORMS, vol. 31(2), pages 267-284, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Josef Jablonský & Michal Černý & Juraj Pekár, 2022. "The last dozen of years of OR research in Czechia and Slovakia," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(2), pages 435-447, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    2. Jean-Philippe Gayon & Guillaume Massonnet & Christophe Rapine & Gautier Stauffer, 2017. "Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 854-875, August.
    3. Adam N. Elmachtoub & Retsef Levi, 2016. "Supply Chain Management with Online Customer Selection," Operations Research, INFORMS, vol. 64(2), pages 458-473, April.
    4. Danny Segev, 2014. "An Approximate Dynamic-Programming Approach to the Joint Replenishment Problem," Mathematics of Operations Research, INFORMS, vol. 39(2), pages 432-444, May.
    5. Kimms, Alf & Drexl, Andreas, 1996. "Multi-level lot sizing: A literature survey," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 405, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    6. Gayon, J.-P. & Massonnet, G. & Rapine, C. & Stauffer, G., 2016. "Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales," European Journal of Operational Research, Elsevier, vol. 250(1), pages 155-163.
    7. Siao-Leu Phouratsamay & Safia Kedad-Sidhoum & Fanny Pascual, 2021. "Coordination of a two-level supply chain with contracts," 4OR, Springer, vol. 19(2), pages 235-264, June.
    8. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    9. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    10. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2005. "Integrated Lot Sizing in Serial Supply Chains with Production Capacities," Management Science, INFORMS, vol. 51(11), pages 1706-1719, November.
    11. Hark‐Chin Hwang & Wilco van den Heuvel, 2012. "Improved algorithms for a lot‐sizing problem with inventory bounds and backlogging," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 244-253, April.
    12. Martel, Alain & Gascon, Andre, 1998. "Dynamic lot-sizing with price changes and price-dependent holding costs," European Journal of Operational Research, Elsevier, vol. 111(1), pages 114-128, November.
    13. Herbert Meyr & Mirko Kiel, 2022. "Minimizing setups and waste when printing labels of consumer goods," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 733-761, September.
    14. Nadjib Brahimi & Stéphane Dauzère-Pérès & Najib M. Najid, 2006. "Capacitated Multi-Item Lot-Sizing Problems with Time Windows," Operations Research, INFORMS, vol. 54(5), pages 951-967, October.
    15. Aarts, E. H. L. & Reijnhoudt, M. F. & Stehouwer, H. P. & Wessels, J., 2000. "A novel decomposition approach for on-line lot-sizing," European Journal of Operational Research, Elsevier, vol. 122(2), pages 339-353, April.
    16. Adam N. Elmachtoub & Paul Grigas, 2022. "Smart “Predict, then Optimize”," Management Science, INFORMS, vol. 68(1), pages 9-26, January.
    17. Yongpei Guan, 2011. "Stochastic lot-sizing with backlogging: computational complexity analysis," Journal of Global Optimization, Springer, vol. 49(4), pages 651-678, April.
    18. van den Heuvel, Wilco & Wagelmans, Albert P.M., 2006. "A polynomial time algorithm for a deterministic joint pricing and inventory model," European Journal of Operational Research, Elsevier, vol. 170(2), pages 463-480, April.
    19. Piñeyro, Pedro & Viera, Omar, 2010. "The economic lot-sizing problem with remanufacturing and one-way substitution," International Journal of Production Economics, Elsevier, vol. 124(2), pages 482-488, April.
    20. Romeijn, H.E. & van den Heuvel, W.J. & Geunes, J., 2012. "Mitigating the Cost of Anarchy in Supply Chain Systems," Econometric Institute Research Papers EI 2012-03, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:68:y:2020:i:1:p:214-232. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.