IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v73y2011i2p263-280.html
   My bibliography  Save this article

Inverse p-median problems with variable edge lengths

Author

Listed:
  • Fahimeh Baroughi Bonab
  • Rainer Burkard
  • Elisabeth Gassner

Abstract

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly $${\mathcal{NP}}$$ -hard on general graphs and weakly $${\mathcal{NP}}$$ -hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm. Copyright Springer-Verlag 2011

Suggested Citation

  • Fahimeh Baroughi Bonab & Rainer Burkard & Elisabeth Gassner, 2011. "Inverse p-median problems with variable edge lengths," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 73(2), pages 263-280, April.
    • Handle: RePEc:spr:mathme:v:73:y:2011:i:2:p:263-280
    DOI: 10.1007/s00186-011-0346-5
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00186-011-0346-5
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s00186-011-0346-5?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. Fahimeh Baroughi Bonab & Rainer Burkard & Behrooz Alizadeh, 2010. "Inverse median location problems with variable coordinates," 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. 18(3), pages 365-381, September.
    2. Burkard, Rainer E. & Galavii, Mohammadreza & Gassner, Elisabeth, 2010. "The inverse Fermat-Weber problem," European Journal of Operational Research, Elsevier, vol. 206(1), pages 11-17, October.
    3. S. L. Hakimi, 1964. "Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph," Operations Research, INFORMS, vol. 12(3), pages 450-459, June.
    4. A. J. Goldman, 1971. "Optimal Center Location in Simple Networks," Transportation Science, INFORMS, vol. 5(2), pages 212-221, May.
    5. Elisabeth Gassner, 2008. "The inverse 1-maxian problem with edge length modification," Journal of Combinatorial Optimization, Springer, vol. 16(1), pages 50-67, July.
    6. 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.
    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. Kien Nguyen & Lam Anh, 2015. "Inverse $$k$$ k -centrum problem on trees with variable vertex weights," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(1), pages 19-30, August.
    2. Nguyen, Kien Trung & Chassein, André, 2015. "The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance," European Journal of Operational Research, Elsevier, vol. 247(3), pages 774-781.
    3. Le Xuan Dai & Kien Trung Nguyen & Le Phuong Thao & Pham Thi Vui, 2024. "Some robust inverse median problems on trees with interval costs," Computational Management Science, Springer, vol. 21(2), pages 1-25, December.
    4. Kien Trung Nguyen, 2019. "The inverse 1-center problem on cycles with variable edge lengths," 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. 27(1), pages 263-274, March.
    5. Kien Trung Nguyen & Ali Reza Sepasian, 2016. "The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 872-884, October.
    6. Shahede Omidi & Jafar Fathali & Morteza Nazari, 2020. "Inverse and reverse balanced facility location problems with variable edge lengths on trees," OPSEARCH, Springer;Operational Research Society of India, vol. 57(2), pages 261-273, June.
    7. Alizadeh, Behrooz & Afrashteh, Esmaeil, 2020. "Budget-constrained inverse median facility location problem on tree networks," Applied Mathematics and Computation, Elsevier, vol. 375(C).
    8. Behrooz Alizadeh & Esmaeil Afrashteh & Fahimeh Baroughi, 2018. "Combinatorial Algorithms for Some Variants of Inverse Obnoxious Median Location Problem on Tree Networks," Journal of Optimization Theory and Applications, Springer, vol. 178(3), pages 914-934, September.
    9. S. Nobakhtian & A. Raeisi Dehkordi, 2018. "A fast algorithm for the rectilinear distance location problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 88(1), pages 81-98, August.
    10. Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi & Kien Trung Nguyen, 2018. "Linear Time Optimal Approaches for Max-Profit Inverse 1-Median Location Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(05), pages 1-22, October.
    11. Kien Trung Nguyen, 2016. "Inverse 1-Median Problem on Block Graphs with Variable Vertex Weights," Journal of Optimization Theory and Applications, Springer, vol. 168(3), pages 944-957, March.
    12. Behrooz Alizadeh & Somayeh Bakhteh, 2017. "A modified firefly algorithm for general inverse p-median location problems under different distance norms," OPSEARCH, Springer;Operational Research Society of India, vol. 54(3), pages 618-636, September.
    13. Behrooz Alizadeh & Rainer Burkard, 2013. "A linear time algorithm for inverse obnoxious center location problems 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. 21(3), pages 585-594, September.
    14. Baldomero-Naranjo, Marta & Kalcsics, Jörg & Marín, Alfredo & Rodríguez-Chía, Antonio M., 2022. "Upgrading edges in the maximal covering location problem," European Journal of Operational Research, Elsevier, vol. 303(1), pages 14-36.
    15. Kien Trung Nguyen & Huong Nguyen-Thu & Nguyen Thanh Hung, 2018. "On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 88(2), pages 147-159, October.

    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. Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi & Kien Trung Nguyen, 2018. "Linear Time Optimal Approaches for Max-Profit Inverse 1-Median Location Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(05), pages 1-22, October.
    2. Behrooz Alizadeh & Somayeh Bakhteh, 2017. "A modified firefly algorithm for general inverse p-median location problems under different distance norms," OPSEARCH, Springer;Operational Research Society of India, vol. 54(3), pages 618-636, September.
    3. Xiucui Guan & Binwu Zhang, 2012. "Inverse 1-median problem on trees under weighted Hamming distance," Journal of Global Optimization, Springer, vol. 54(1), pages 75-82, September.
    4. Alizadeh, Behrooz & Afrashteh, Esmaeil, 2020. "Budget-constrained inverse median facility location problem on tree networks," Applied Mathematics and Computation, Elsevier, vol. 375(C).
    5. Behrooz Alizadeh & Esmaeil Afrashteh & Fahimeh Baroughi, 2018. "Combinatorial Algorithms for Some Variants of Inverse Obnoxious Median Location Problem on Tree Networks," Journal of Optimization Theory and Applications, Springer, vol. 178(3), pages 914-934, September.
    6. Elisabeth Gassner, 2012. "An inverse approach to convex ordered median problems in trees," Journal of Combinatorial Optimization, Springer, vol. 23(2), pages 261-273, February.
    7. Kien Nguyen & Lam Anh, 2015. "Inverse $$k$$ k -centrum problem on trees with variable vertex weights," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(1), pages 19-30, August.
    8. Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi, 2020. "Optimal approaches for upgrading selective obnoxious p-median location problems on tree networks," Annals of Operations Research, Springer, vol. 289(2), pages 153-172, June.
    9. Burkard, Rainer E. & Galavii, Mohammadreza & Gassner, Elisabeth, 2010. "The inverse Fermat-Weber problem," European Journal of Operational Research, Elsevier, vol. 206(1), pages 11-17, October.
    10. Gassner, Elisabeth, 2009. "Up- and downgrading the 1-center in a network," European Journal of Operational Research, Elsevier, vol. 198(2), pages 370-377, October.
    11. Oded Berman & Dmitry Krass & Mozart B. C. Menezes, 2007. "Facility Reliability Issues in Network p -Median Problems: Strategic Centralization and Co-Location Effects," Operations Research, INFORMS, vol. 55(2), pages 332-350, April.
    12. Mulder, H.M. & Pelsmajer, M.J. & Reid, K.B., 2006. "Generalized centrality in trees," Econometric Institute Research Papers EI 2006-16, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    13. Behrooz Alizadeh & Rainer Burkard, 2013. "A linear time algorithm for inverse obnoxious center location problems 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. 21(3), pages 585-594, September.
    14. Hakimi, S.Louis, 1983. "Network location theory and contingency planning," Energy, Elsevier, vol. 8(8), pages 697-702.
    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. Igor Averbakh & Oded Berman, 2000. "Minmax Regret Median Location on a Network Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 104-110, May.
    17. Ting Zeng & James Ward, 2005. "The Stochastic Location-Assignment Problem on a Tree," Annals of Operations Research, Springer, vol. 136(1), pages 81-97, April.
    18. ReVelle, C. S. & Eiselt, H. A., 2005. "Location analysis: A synthesis and survey," European Journal of Operational Research, Elsevier, vol. 165(1), pages 1-19, August.
    19. Le Xuan Dai & Kien Trung Nguyen & Le Phuong Thao & Pham Thi Vui, 2024. "Some robust inverse median problems on trees with interval costs," Computational Management Science, Springer, vol. 21(2), pages 1-25, December.
    20. Vladimir Marianov & Daniel Serra, 2009. "Median problems in networks," Economics Working Papers 1151, Department of Economics and Business, Universitat Pompeu Fabra.

    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:mathme:v:73:y:2011:i:2:p:263-280. 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.