IDEAS home Printed from https://ideas.repec.org/a/wut/journl/v1y2014p37-49id1059.html
   My bibliography  Save this article

Perturbation algorithm for a minimax regret minimum spanning tree problem

Author

Listed:
  • Mariusz Makuchowski

Abstract

The problem of finding a robust spanning tree has been analysed. The problem consists of determining a minimum spanning tree of a graph with uncertain edge costs. We should determine a spanning tree that minimizes the difference in costs between the tree selected and the optimal tree. While doing this, all possible realizations of the edge costs should be taken into account. This issue belongs to the class of NP-hard problems. In this paper, an algorithm based on the cost perturbation method and adapted to the analysed problem has been proposed. The paper also contains the results of numerical experiments testing the effectiveness of the proposed algorithm and compares it with algorithms known in the literature. The research is based on a large number of various test examples taken from the literature.

Suggested Citation

  • Mariusz Makuchowski, 2014. "Perturbation algorithm for a minimax regret minimum spanning tree problem," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 24(1), pages 37-49.
    • Handle: RePEc:wut:journl:v:1:y:2014:p:37-49:id:1059
    DOI: 10.5277/ord140103
    as

    Download full text from publisher

    File URL: https://ord.pwr.edu.pl/assets/papers_archive/1059%20-%20published.pdf
    Download Restriction: no
    File URL: https://libkey.io/10.5277/ord140103?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. Montemanni, R. & Gambardella, L. M., 2005. "A branch and bound algorithm for the robust spanning tree problem with interval data," European Journal of Operational Research, Elsevier, vol. 161(3), pages 771-779, March.
    2. N/A, 1996. "Note:," Foreign Trade Review, , vol. 31(1-2), pages 1-1, January.
    3. Celso C. Ribeiro & Eduardo Uchoa & Renato F. Werneck, 2002. "A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs," INFORMS Journal on Computing, INFORMS, vol. 14(3), pages 228-246, August.
    4. Conde, Eduardo & Candia, Alfredo, 2007. "Minimax regret spanning arborescences under uncertain costs," European Journal of Operational Research, Elsevier, vol. 182(2), pages 561-577, October.
    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. Wei Wu & Manuel Iori & Silvano Martello & Mutsunori Yagiura, 2022. "An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2523-2539, September.

    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. Hiroshi Fujiki & Edward J. Green & Akira Yamazaki, 1999. "Sharing the risk of settlement failure," Working Papers 594, Federal Reserve Bank of Minneapolis.
    2. Kris James Mitchener & Matthew Jaremski, 2014. "The Evolution of Bank Supervision: Evidence from U.S. States," NBER Working Papers 20603, National Bureau of Economic Research, Inc.
    3. , G. & , & ,, 2008. "Non-Bayesian updating: A theoretical framework," Theoretical Economics, Econometric Society, vol. 3(2), June.
    4. Andrei Kapaev, 2013. "Remark on repo and options," Papers 1311.5211, arXiv.org.
    5. Daniel Sanches, 2016. "On the Inherent Instability of Private Money," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 20, pages 198-214, April.
    6. Ricardo de O. Cavalcanti & Andres Erosa & Ted Temzelides, 1999. "Private Money and Reserve Management in a Random-Matching Model," Journal of Political Economy, University of Chicago Press, vol. 107(5), pages 929-945, October.
    7. James J. McAndrews & William Roberds, 1999. "Payment intermediation and the origins of banking," Staff Reports 85, Federal Reserve Bank of New York.
    8. Allen Head & Junfeng Qiu, 2007. "Elastic Money, Inflation, And Interest Rate Policy," Working Paper 1152, Economics Department, Queen's University.
    9. Hentati-Kaffel, R. & Prigent, J.-L., 2016. "Optimal positioning in financial derivatives under mixture distributions," Economic Modelling, Elsevier, vol. 52(PA), pages 115-124.
    10. Fong, Wai Mun, 1997. "Robust beta estimation: Some empirical evidence," Review of Financial Economics, Elsevier, vol. 6(2), pages 167-186.
    11. Freixas, Xavier & Parigi, Bruno M & Rochet, Jean-Charles, 2000. "Systemic Risk, Interbank Relations, and Liquidity Provision by the Central Bank," Journal of Money, Credit and Banking, Blackwell Publishing, vol. 32(3), pages 611-638, August.
    12. Marti, Rafael, 2006. "Scatter Search--Wellsprings and Challenges," European Journal of Operational Research, Elsevier, vol. 169(2), pages 351-358, March.
    13. repec:ulb:ulbcvp:p0025 is not listed on IDEAS
    14. Santiago Moreno-Bromberg & Luca Taschini, 2011. "Pollution permits, Strategic Trading and Dynamic Technology Adoption," Papers 1103.2914, arXiv.org.
    15. Steven Brams & D. Kilgour, 1998. "Backward Induction Is Not Robust: The Parity Problem and the Uncertainty Problem," Theory and Decision, Springer, vol. 45(3), pages 263-289, December.
    16. Christian Volpe Martincus & Andrés Gallo, 2009. "Institutions and Export Specialization: Just Direct Effects?," Kyklos, Wiley Blackwell, vol. 62(1), pages 129-149, February.
    17. Zelenyuk, Valentin, 2015. "Aggregation of scale efficiency," European Journal of Operational Research, Elsevier, vol. 240(1), pages 269-277.
    18. Junfeng Qiu, 2011. "Bank money, aggregate liquidity, and asset prices," Annals of Economics and Finance, Society for AEF, vol. 12(2), pages 295-346, November.
    19. Antunes, Antonio & Peeters, Dominique, 2001. "On solving complex multi-period location models using simulated annealing," European Journal of Operational Research, Elsevier, vol. 130(1), pages 190-201, April.
    20. Postlewaite, Andrew, 1998. "The social basis of interdependent preferences," European Economic Review, Elsevier, vol. 42(3-5), pages 779-800, May.
    21. Giacomo Bonanno, 2008. "Non-cooperative game theory," Working Papers 86, University of California, Davis, Department of Economics.

    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:wut:journl:v:1:y:2014:p:37-49:id:1059. 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: Adam Kasperski (email available below). General contact details of provider: https://edirc.repec.org/data/iopwrpl.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.