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. 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.
    2. 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.
    3. 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.
    4. N/A, 1996. "Note:," Foreign Trade Review, , vol. 31(1-2), pages 1-1, January.
    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. 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.
    2. , G. & , & ,, 2008. "Non-Bayesian updating: A theoretical framework," Theoretical Economics, Econometric Society, vol. 3(2), June.
    3. Andrei Kapaev, 2013. "Remark on repo and options," Papers 1311.5211, arXiv.org.
    4. 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.
    5. James J. McAndrews & William Roberds, 1999. "Payment intermediation and the origins of banking," Staff Reports 85, Federal Reserve Bank of New York.
    6. Allen Head & Junfeng Qiu, 2007. "Elastic Money, Inflation, And Interest Rate Policy," Working Paper 1152, Economics Department, Queen's University.
    7. Fong, Wai Mun, 1997. "Robust beta estimation: Some empirical evidence," Review of Financial Economics, Elsevier, vol. 6(2), pages 167-186.
    8. 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.
    9. Santiago Moreno-Bromberg & Luca Taschini, 2011. "Pollution permits, Strategic Trading and Dynamic Technology Adoption," Papers 1103.2914, arXiv.org.
    10. 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.
    11. 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.
    12. Zibo Xu, 2013. "The instability of backward induction in evolutionary dynamics," Discussion Paper Series dp633, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    13. James S. Costain, 1998. "On the quantitative importance of wage bargaining models," Economics Working Papers 262, Department of Economics and Business, Universitat Pompeu Fabra.
    14. Kahn, Charles M & Roberds, William, 1998. "Payment System Settlement and Bank Incentives," The Review of Financial Studies, Society for Financial Studies, vol. 11(4), pages 845-870.
    15. Jim Dolmas & Gregory W. Huffman, 2004. "On The Political Economy Of Immigration And Income Redistribution," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 45(4), pages 1129-1168, November.
    16. Zarepisheh, M. & Soleimani-damaneh, M., 2009. "A dual simplex-based method for determination of the right and left returns to scale in DEA," European Journal of Operational Research, Elsevier, vol. 194(2), pages 585-591, April.
    17. Banker, Rajiv D. & Chang, Hsihui & Cooper, William W., 1996. "Equivalence and implementation of alternative methods for determining returns to scale in data envelopment analysis," European Journal of Operational Research, Elsevier, vol. 89(3), pages 473-481, March.
    18. Kenney, Martin & Patton, Donald, 2003. "Innovation and Social Capital in Silicon Valley," UCAIS Berkeley Roundtable on the International Economy, Working Paper Series qt25w6w54t, UCAIS Berkeley Roundtable on the International Economy, UC Berkeley.
    19. Howard Bodenhorn & Eugene N. White, 2014. "The Evolution of Bank Boards of Directors in New York, 1840–1950," NBER Chapters, in: Enterprising America: Businesses, Banks, and Credit Markets in Historical Perspective, pages 107-145, National Bureau of Economic Research, Inc.
    20. Srinivas, P.S. & Whitehouse, Edward & Yermo, Juan, 2000. "Regulating private pension funds’ structure, performance and investments: cross-country evidence," MPRA Paper 14753, University Library of Munich, Germany.

    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.