IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v88y2018i2d10.1007_s00186-018-0632-6.html
   My bibliography  Save this article

On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks

Author

Listed:
  • Kien Trung Nguyen

    (Can Tho University)

  • Huong Nguyen-Thu

    (Can Tho University)

  • Nguyen Thanh Hung

    (Can Tho University)

Abstract

An ordered median function is used in location theory to generalize a class of problems, including median and center problems. In this paper we consider the complexity of inverse ordered 1-median problems on the plane and on trees, where the multipliers are sorted nondecreasingly. Based on the convexity of the objective function, we prove that the problems with variable weights or variable coordinates on the line are NP-hard. Then we can directly get the NP-hardness result for the corresponding problem on the plane. We finally develop a cubic time algorithm that solves the inverse convex ordered 1-median problem on trees with relaxation on modification bounds.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:mathme:v:88:y:2018:i:2:d:10.1007_s00186-018-0632-6
    DOI: 10.1007/s00186-018-0632-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00186-018-0632-6
    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/s00186-018-0632-6?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. 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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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 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.
    2. Nguyen, Kien Trung & Hung, Nguyen Thanh, 2021. "The minmax regret inverse maximum weight problem," Applied Mathematics and Computation, Elsevier, vol. 407(C).

    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. Alizadeh, Behrooz & Afrashteh, Esmaeil, 2020. "Budget-constrained inverse median facility location problem on tree networks," Applied Mathematics and Computation, Elsevier, vol. 375(C).
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Nguyen, Kien Trung & Hung, Nguyen Thanh, 2021. "The minmax regret inverse maximum weight problem," Applied Mathematics and Computation, Elsevier, vol. 407(C).
    14. 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.
    15. Ali Reza Sepasian, 2019. "Reverse 1-maxian problem with keeping existing 1-median," OPSEARCH, Springer;Operational Research Society of India, vol. 56(1), pages 1-13, March.
    16. 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.
    17. Zhi-Ming Chen & Cheng-Hsiung Lee & Hung-Lin Lai, 2022. "Speedup the optimization of maximal closure of a node-weighted directed acyclic graph," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1413-1437, December.
    18. Libura, Marek, 2007. "On the adjustment problem for linear programs," European Journal of Operational Research, Elsevier, vol. 183(1), pages 125-134, November.
    19. Qin Wang & Tianyu Yang & Longshu Wu, 0. "General restricted inverse assignment problems under $$l_1$$l1 and $$l_\infty $$l∞ norms," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-16.
    20. 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.

    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:88:y:2018:i:2:d:10.1007_s00186-018-0632-6. 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.