IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v77y2020i2d10.1007_s10898-019-00852-4.html
   My bibliography  Save this article

Approximation algorithms for capacitated partial inverse maximum spanning tree problem

Author

Listed:
  • Xianyue Li

    (Lanzhou University)

  • Zhao Zhang

    (Zhejiang Normal University)

  • Ruowang Yang

    (Lanzhou University)

  • Heping Zhang

    (Lanzhou University)

  • Ding-Zhu Du

    (University of Texas at Dallas)

Abstract

Given an edge weighted graph, and an acyclic edge set, the goal of the partial inverse maximum spanning tree problem is to modify the weight function as little as possible such that there exists a maximum spanning tree with respect to the new weight function containing the given edge set. In this paper, we consider this problem with capacitated constraint under the $$l_{p}$$lp-norm, where p is an integer and $$p \in [1,+\,\infty )$$p∈[1,+∞). Firstly, we characterize the feasible solutions of this problem. Then, we present a $$\root p \of {k}$$kp-approximation algorithm for this problem when the weight function can only be decreased, where k is the number of edges in the given edge set. Finally, when the weight function can be either decreased and increased, we propose an approximation algorithm for the general case and analyse its approximation ratio. Moreover, we remark that these algorithms can be generalized under the weighted $$l_{p}$$lp-norm and the weighted sum Hamming distance.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jglopt:v:77:y:2020:i:2:d:10.1007_s10898-019-00852-4
    DOI: 10.1007/s10898-019-00852-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-019-00852-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-019-00852-4?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. Yong He & Binwu Zhang & Enyu Yao, 2005. "Weighted Inverse Minimum Spanning Tree Problems Under Hamming Distance," Journal of Combinatorial Optimization, Springer, vol. 9(1), pages 91-100, February.
    3. Xianyue Li & Zhao Zhang & Ding-Zhu Du, 2018. "Partial inverse maximum spanning tree in which weight can only be decreased under $$l_p$$ l p -norm," Journal of Global Optimization, Springer, vol. 70(3), pages 677-685, March.
    4. 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.
    5. Dorit S. Hochbaum, 2003. "Efficient Algorithms for the Inverse Spanning-Tree Problem," Operations Research, INFORMS, vol. 51(5), pages 785-797, October.
    6. 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.
    7. 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.
    8. Omar Ben-Ayed & Charles E. Blair, 1990. "Computational Difficulties of Bilevel Linear Programming," Operations Research, INFORMS, vol. 38(3), pages 556-560, June.
    9. Zhao Zhang & Shuangshuang Li & Hong-Jian Lai & Ding-Zhu Du, 2016. "Algorithms for the partial inverse matroid problem in which weights can only be increased," Journal of Global Optimization, Springer, vol. 65(4), pages 801-811, August.
    10. 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.
    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. 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.
    2. 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.
    3. 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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    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. 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.
    7. 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.
    8. Nguyen, Kien Trung & Hung, Nguyen Thanh, 2021. "The minmax regret inverse maximum weight problem," Applied Mathematics and Computation, Elsevier, vol. 407(C).
    9. Xianyue Li & Zhao Zhang & Ding-Zhu Du, 2018. "Partial inverse maximum spanning tree in which weight can only be decreased under $$l_p$$ l p -norm," Journal of Global Optimization, Springer, vol. 70(3), pages 677-685, March.
    10. 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.
    11. 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.
    12. Binwu Zhang & Xiucui Guan & Panos M. Pardalos & Chunyuan He, 2018. "An Algorithm for Solving the Shortest Path Improvement Problem on Rooted Trees Under Unit Hamming Distance," Journal of Optimization Theory and Applications, Springer, vol. 178(2), pages 538-559, August.
    13. 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.
    14. 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.
    15. Xinqiang Qian & Xiucui Guan & Junhua Jia & Qiao Zhang & Panos M. Pardalos, 2023. "Vertex quickest 1-center location problem on trees and its inverse problem under weighted $$l_\infty $$ l ∞ norm," Journal of Global Optimization, Springer, vol. 85(2), pages 461-485, February.
    16. 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.
    17. Sinha, Surabhi & Sinha, S. B., 2002. "KKT transformation approach for multi-objective multi-level linear programming problems," European Journal of Operational Research, Elsevier, vol. 143(1), pages 19-31, November.
    18. 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.
    19. Dorit S. Hochbaum, 2003. "Efficient Algorithms for the Inverse Spanning-Tree Problem," Operations Research, INFORMS, vol. 51(5), pages 785-797, October.
    20. Budnitzki, Alina, 2014. "Computation of the optimal tolls on the traffic network," European Journal of Operational Research, Elsevier, vol. 235(1), pages 247-251.

    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:spr:jglopt:v:77:y:2020:i:2:d:10.1007_s10898-019-00852-4. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.