Inverse anti-k-centrum problem on networks with variable edge lengths. Pham, V. H. & Nguyen, K. T. Taiwanese Journal of Mathematics, 24(2):501–522, 2020. doi abstract bibtex This paper concerns the problem of modifying edge lengths of a network at minimum total costs so as to make a prespecified vertex become an optimal location in the modified environment. Here, we focus on the ordered median objective function with respect to the vector of multipliers λ = (1, …, 1, 0, …, 0) with k 1’s. This problem is called the inverse anti-k-centrum problem. We first show that the inverse anti-k-centrum problem is NP-hard even on tree networks. However, for the inverse anti-k-centrum problem on cycles, we formulate it as one or two linear programs, depending on odd or even integer k. Concerning the special cases with k = 2, 3, M, we develop combinatorial algorithms that efficiently solve the problem, where M is the number of vertices of the cycle.
@article{Pham2020,
title = {Inverse anti-k-centrum problem on networks with variable edge lengths},
volume = {24},
issn = {10275487},
doi = {10.11650/tjm/190602},
abstract = {This paper concerns the problem of modifying edge lengths of a network at minimum total costs so as to make a prespecified vertex become an optimal location in the modified environment. Here, we focus on the ordered median objective function with respect to the vector of multipliers λ = (1, …, 1, 0, …, 0) with k 1’s. This problem is called the inverse anti-k-centrum problem. We first show that the inverse anti-k-centrum problem is NP-hard even on tree networks. However, for the inverse anti-k-centrum problem on cycles, we formulate it as one or two linear programs, depending on odd or even integer k. Concerning the special cases with k = 2, 3, M, we develop combinatorial algorithms that efficiently solve the problem, where M is the number of vertices of the cycle.},
number = {2},
journal = {Taiwanese Journal of Mathematics},
author = {Pham, Van Huy and Nguyen, Kien Trung},
year = {2020},
keywords = {Anti-k-centrum, Cycle, Inverse optimization problems, Location problems, Ordered median function, Tree},
pages = {501--522},
}
Downloads: 0
{"_id":"uF82bYgDCurWqCYcK","bibbaseid":"pham-nguyen-inverseantikcentrumproblemonnetworkswithvariableedgelengths-2020","author_short":["Pham, V. H.","Nguyen, K. T."],"bibdata":{"bibtype":"article","type":"article","title":"Inverse anti-k-centrum problem on networks with variable edge lengths","volume":"24","issn":"10275487","doi":"10.11650/tjm/190602","abstract":"This paper concerns the problem of modifying edge lengths of a network at minimum total costs so as to make a prespecified vertex become an optimal location in the modified environment. Here, we focus on the ordered median objective function with respect to the vector of multipliers λ = (1, …, 1, 0, …, 0) with k 1’s. This problem is called the inverse anti-k-centrum problem. We first show that the inverse anti-k-centrum problem is NP-hard even on tree networks. However, for the inverse anti-k-centrum problem on cycles, we formulate it as one or two linear programs, depending on odd or even integer k. Concerning the special cases with k = 2, 3, M, we develop combinatorial algorithms that efficiently solve the problem, where M is the number of vertices of the cycle.","number":"2","journal":"Taiwanese Journal of Mathematics","author":[{"propositions":[],"lastnames":["Pham"],"firstnames":["Van","Huy"],"suffixes":[]},{"propositions":[],"lastnames":["Nguyen"],"firstnames":["Kien","Trung"],"suffixes":[]}],"year":"2020","keywords":"Anti-k-centrum, Cycle, Inverse optimization problems, Location problems, Ordered median function, Tree","pages":"501–522","bibtex":"@article{Pham2020,\n\ttitle = {Inverse anti-k-centrum problem on networks with variable edge lengths},\n\tvolume = {24},\n\tissn = {10275487},\n\tdoi = {10.11650/tjm/190602},\n\tabstract = {This paper concerns the problem of modifying edge lengths of a network at minimum total costs so as to make a prespecified vertex become an optimal location in the modified environment. Here, we focus on the ordered median objective function with respect to the vector of multipliers λ = (1, …, 1, 0, …, 0) with k 1’s. This problem is called the inverse anti-k-centrum problem. We first show that the inverse anti-k-centrum problem is NP-hard even on tree networks. However, for the inverse anti-k-centrum problem on cycles, we formulate it as one or two linear programs, depending on odd or even integer k. Concerning the special cases with k = 2, 3, M, we develop combinatorial algorithms that efficiently solve the problem, where M is the number of vertices of the cycle.},\n\tnumber = {2},\n\tjournal = {Taiwanese Journal of Mathematics},\n\tauthor = {Pham, Van Huy and Nguyen, Kien Trung},\n\tyear = {2020},\n\tkeywords = {Anti-k-centrum, Cycle, Inverse optimization problems, Location problems, Ordered median function, Tree},\n\tpages = {501--522},\n}\n\n","author_short":["Pham, V. H.","Nguyen, K. T."],"key":"Pham2020-1-1-1-1-1-1-1-1","id":"Pham2020-1-1-1-1-1-1-1-1","bibbaseid":"pham-nguyen-inverseantikcentrumproblemonnetworkswithvariableedgelengths-2020","role":"author","urls":{},"keyword":["Anti-k-centrum","Cycle","Inverse optimization problems","Location problems","Ordered median function","Tree"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://api.zotero.org/groups/2168152/items?key=VCdsaROd5deDY3prqqG8kI0c&format=bibtex&limit=100","dataSources":["syJjwTDDM32TsM2iF","QwrFbRJvXF69SEShv","HbngRCZLbLed2q9QT","LtEFvT85hYpNg4Esp","iHfnnAr7wKJJxkNMt","PrvBTxn4Zgeep29e5","78Yd9ZHcx783Wkffe","SKRhTA7ok4L4waPkZ","GfrMfnKTkYdcYTRsy","RqqCdXGEyWH4dZ76k","cbiwaQPQJSZeJDDY9","2Jak7xK39ytqcgqQ4","CDfDBPD6CDScj6Ty4","WgiCycoQjRx6KArBy","KBdipwowTNXWiKqYd","yjd6eECyb3TYZpZ3R","D9jmZ7aoHfJnYQ4ES","R8dLFAvyQ2oFRijDJ","dc6SzEK4S9LfC3XpA","kGWABmrDfhF29uibh","YE9GesxGLCsBc3vvC","v3qfuosZ66nvD85FK","BSxBG5ms26R2teZn9"],"keywords":["anti-k-centrum","cycle","inverse optimization problems","location problems","ordered median function","tree"],"search_terms":["inverse","anti","centrum","problem","networks","variable","edge","lengths","pham","nguyen"],"title":"Inverse anti-k-centrum problem on networks with variable edge lengths","year":2020}