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

Efficient Algorithms for the Inverse Spanning-Tree Problem

Author

Listed:
  • Dorit S. Hochbaum

    (Department of Industrial Engineering and Operations Research, Walter A. Haas School of Business, University of California, Berkeley, California 94720)

Abstract

The inverse spanning-tree problem is to modify edge weights in a graph so that a given tree T is a minimum spanning tree. The objective is to minimize the cost of the deviation. The cost of deviation is typically a convex function. We propose algorithms here that are faster than all known algorithms for the problem. Our algorithm's run time for any convex inverse spanning-tree problem is O ( nm log 2 n ) for a graph on n nodes and m edges plus the time required to find the minima of the n convex deviation functions. This not only improves on the complexity of previously known algorithms for the general problem, but also for algorithms devised for special cases. For the case when the objective is weighted absolute deviation, Sokkalingam et al. (1999) devised an algorithm with run time O ( n 2 m log( nC )) for C the maximum edge weight. For the sum of absolute deviations our algorithm runs in time O ( n 2 log n ), matching the run time of a recent (Ahuja and Orlin 2000) improvement for this case. A new algorithm for bipartite matching in path graphs is reported here with complexity of O ( n 1.5 log n ). This leads to a second algorithm for the sum of absolute deviations running in O ( n 1.5 log n log C ) steps.

Suggested Citation

  • Dorit S. Hochbaum, 2003. "Efficient Algorithms for the Inverse Spanning-Tree Problem," Operations Research, INFORMS, vol. 51(5), pages 785-797, October.
    • Handle: RePEc:inm:oropre:v:51:y:2003:i:5:p:785-797
    DOI: 10.1287/opre.51.5.785.16756
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.51.5.785.16756
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.51.5.785.16756?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. P. T. Sokkalingam & Ravindra K. Ahuja & James B. Orlin, 1999. "Solving Inverse Spanning Tree Problems Through Network Flow Techniques," Operations Research, INFORMS, vol. 47(2), pages 291-298, April.
    2. Jean-Claude Picard, 1976. "Maximal Closure of a Graph and Applications to Combinatorial Problems," Management Science, INFORMS, vol. 22(11), pages 1268-1272, July.
    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. Madziwa, Lawrence & Pillalamarry, Mallikarjun & Chatterjee, Snehamoy, 2023. "Integrating stochastic mine planning model with ARDL commodity price forecasting," Resources Policy, Elsevier, vol. 85(PB).
    2. Xiucui Guan & Xinyan He & Panos M. Pardalos & Binwu Zhang, 2017. "Inverse max $$+$$ + sum spanning tree problem under Hamming distance by modifying the sum-cost vector," Journal of Global Optimization, Springer, vol. 69(4), pages 911-925, December.
    3. Timothy C. Y. Chan & Tim Craig & Taewoo Lee & Michael B. Sharpe, 2014. "Generalized Inverse Multiobjective Optimization with Application to Cancer Therapy," Operations Research, INFORMS, vol. 62(3), pages 680-695, June.
    4. Kien Trung Nguyen & Nguyen Thanh Hung, 2020. "The inverse connected p-median problem on block graphs under various cost functions," Annals of Operations Research, Springer, vol. 292(1), pages 97-112, September.
    5. Binwu Zhang & Xiucui Guan & Panos M. Pardalos & Hui Wang & Qiao Zhang & Yan Liu & Shuyi Chen, 2021. "The lower bounded inverse optimal value problem on minimum spanning tree under unit $$l_{\infty }$$ l ∞ norm," Journal of Global Optimization, Springer, vol. 79(3), pages 757-777, March.
    6. Dorit Hochbaum, 2007. "Complexity and algorithms for nonlinear optimization problems," Annals of Operations Research, Springer, vol. 153(1), pages 257-296, September.
    7. Clemens Heuberger, 2004. "Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 329-361, September.
    8. Xianyue Li & Xichao Shu & Huijing Huang & Jingjing Bai, 2019. "Capacitated partial inverse maximum spanning tree under the weighted Hamming distance," Journal of Combinatorial Optimization, Springer, vol. 38(4), pages 1005-1018, November.
    9. Xianyue Li & Ruowang Yang & Heping Zhang & Zhao Zhang, 2022. "Partial inverse maximum spanning tree problem under the Chebyshev norm," Journal of Combinatorial Optimization, Springer, vol. 44(5), pages 3331-3350, December.
    10. Kien Nguyen & André Chassein, 2015. "Inverse eccentric vertex problem on networks," 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. 23(3), pages 687-698, September.
    11. Nguyen, Kien Trung & Hung, Nguyen Thanh, 2021. "The minmax regret inverse maximum weight problem," Applied Mathematics and Computation, Elsevier, vol. 407(C).
    12. Xiaoguang Yang & Jianzhong Zhang, 2007. "Some inverse min-max network problems under weighted l 1 and l ∞ norms with bound constraints on changes," Journal of Combinatorial Optimization, Springer, vol. 13(2), pages 123-135, February.
    13. Dorit S. Hochbaum, 2004. "50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today," Management Science, INFORMS, vol. 50(6), pages 709-723, June.
    14. Cai, Mao-Cheng & Duin, C.W. & Yang, Xiaoguang & Zhang, Jianzhong, 2008. "The partial inverse minimum spanning tree problem when weight increase is forbidden," European Journal of Operational Research, Elsevier, vol. 188(2), pages 348-353, July.
    15. Dorit S. Hochbaum, 2008. "The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem," Operations Research, INFORMS, vol. 56(4), pages 992-1009, August.
    16. Xiucui Guan & Panos Pardalos & Xia Zuo, 2015. "Inverse Max + Sum spanning tree problem by modifying the sum-cost vector under weighted $$l_\infty $$ l ∞ Norm," Journal of Global Optimization, Springer, vol. 61(1), pages 165-182, January.
    17. Junhua Jia & Xiucui Guan & Qiao Zhang & Xinqiang Qian & Panos M. Pardalos, 2022. "Inverse max+sum spanning tree problem under weighted $$l_{\infty }$$ l ∞ norm by modifying max-weight vector," Journal of Global Optimization, Springer, vol. 84(3), pages 715-738, November.
    18. Madziwa, Lawrence & Pillalamarry, Mallikarjun & Chatterjee, Snehamoy, 2023. "Integrating flexibility in open pit mine planning to survive commodity price decline," Resources Policy, Elsevier, vol. 81(C).
    19. Hui Wang & Xiucui Guan & Qiao Zhang & Binwu Zhang, 2021. "Capacitated inverse optimal value problem on minimum spanning tree under bottleneck Hamming distance," Journal of Combinatorial Optimization, Springer, vol. 41(4), pages 861-887, May.
    20. Xianyue Li & Zhao Zhang & Ruowang Yang & Heping Zhang & Ding-Zhu Du, 2020. "Approximation algorithms for capacitated partial inverse maximum spanning tree problem," Journal of Global Optimization, Springer, vol. 77(2), pages 319-340, June.
    21. Jonathan Yu-Meng Li, 2021. "Inverse Optimization of Convex Risk Functions," Management Science, INFORMS, vol. 67(11), pages 7113-7141, November.
    22. Javad Tayyebi & Ali Reza Sepasian, 2020. "Partial inverse min–max spanning tree problem," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1075-1091, November.

    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. Rafael Epstein & Marcel Goic & Andrés Weintraub & Jaime Catalán & Pablo Santibáñez & Rodolfo Urrutia & Raúl Cancino & Sergio Gaete & Augusto Aguayo & Felipe Caro, 2012. "Optimizing Long-Term Production Plans in Underground and Open-Pit Copper Mines," Operations Research, INFORMS, vol. 60(1), pages 4-17, February.
    2. Xianyue Li & Ruowang Yang & Heping Zhang & Zhao Zhang, 2022. "Partial inverse maximum spanning tree problem under the Chebyshev norm," Journal of Combinatorial Optimization, Springer, vol. 44(5), pages 3331-3350, December.
    3. Zhang, Jianzhong & Xu, Chengxian, 2010. "Inverse optimization for linearly constrained convex separable programming problems," European Journal of Operational Research, Elsevier, vol. 200(3), pages 671-679, February.
    4. Chatterjee, Snehamoy & Sethi, Manas Ranjan & Asad, Mohammad Waqar Ali, 2016. "Production phase and ultimate pit limit design under commodity price uncertainty," European Journal of Operational Research, Elsevier, vol. 248(2), pages 658-667.
    5. Biswas, Pritam & Sinha, Rabindra Kumar & Sen, Phalguni, 2023. "A review of state-of-the-art techniques for the determination of the optimum cut-off grade of a metalliferous deposit with a bibliometric mapping in a surface mine planning context," Resources Policy, Elsevier, vol. 83(C).
    6. Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    7. Clemens Heuberger, 2004. "Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 329-361, September.
    8. Csapó, Gergely & Müller, Rudolf, 2013. "Optimal mechanism design for the private supply of a public good," Games and Economic Behavior, Elsevier, vol. 80(C), pages 229-242.
    9. Domenico Moramarco & Umutcan Salman, 2023. "Equal opportunities in many-to-one matching markets," Working Papers 649, ECINEQ, Society for the Study of Economic Inequality.
    10. Esmaeili, Ahmadreza & Hamidi, Jafar Khademi & Mousavi, Amin, 2023. "Determination of sublevel stoping layout using a network flow algorithm and the MRMR classification system," Resources Policy, Elsevier, vol. 80(C).
    11. Nancel-Penard, Pierre & Morales, Nelson & Cornillier, Fabien, 2022. "A recursive time aggregation-disaggregation heuristic for the multidimensional and multiperiod precedence-constrained knapsack problem: An application to the open-pit mine block sequencing problem," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1088-1099.
    12. Jélvez, Enrique & Morales, Nelson & Nancel-Penard, Pierre & Peypouquet, Juan & Reyes, Patricio, 2016. "Aggregation heuristic for the open-pit block scheduling problem," European Journal of Operational Research, Elsevier, vol. 249(3), pages 1169-1177.
    13. Pavlos Eirinakis & Dimitrios Magos & Ioannis Mourtos & Panayiotis Miliotis, 2012. "Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 245-259, May.
    14. M. Vanhoucke, 2006. "An efficient hybrid search algorithm for various optimization problems," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 06/365, Ghent University, Faculty of Economics and Business Administration.
    15. Bradley Sturt, 2021. "A nonparametric algorithm for optimal stopping based on robust optimization," Papers 2103.03300, arXiv.org, revised Mar 2023.
    16. Jélvez, Enrique & Morales, Nelson & Nancel-Penard, Pierre & Cornillier, Fabien, 2020. "A new hybrid heuristic algorithm for the Precedence Constrained Production Scheduling Problem: A mining application," Omega, Elsevier, vol. 94(C).
    17. José R. Correa & Andreas S. Schulz, 2005. "Single-Machine Scheduling with Precedence Constraints," Mathematics of Operations Research, INFORMS, vol. 30(4), pages 1005-1021, November.
    18. Whittle, D. & Brazil, M. & Grossman, P.A. & Rubinstein, J.H. & Thomas, D.A., 2018. "Combined optimisation of an open-pit mine outline and the transition depth to underground mining," European Journal of Operational Research, Elsevier, vol. 268(2), pages 624-634.
    19. Gonczarowski, Yannai A. & Nisan, Noam & Ostrovsky, Rafail & Rosenbaum, Will, 2019. "A stable marriage requires communication," Games and Economic Behavior, Elsevier, vol. 118(C), pages 626-647.
    20. Madziwa, Lawrence & Pillalamarry, Mallikarjun & Chatterjee, Snehamoy, 2023. "Integrating stochastic mine planning model with ARDL commodity price forecasting," Resources Policy, Elsevier, vol. 85(PB).

    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:51:y:2003:i:5:p:785-797. 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.