{"_id":"CyvtkkqyTQK8cx63G","bibbaseid":"nguyen-hieu-pham-inversegroup1medianproblemontrees-2021","author_short":["Nguyen, K. T.","Hieu, V. N. M.","Pham, V. H."],"bibdata":{"bibtype":"article","type":"article","title":"Inverse Group 1-Median Problem On Trees","volume":"17","issn":"1553166X","doi":"10.3934/jimo.2019108","abstract":"In location theory, group median generalizes the concepts of both median and center. We address in this paper the problem of modifying vertex weights of a tree at minimum total cost so that a prespecified vertex becomes a group 1-median with respect to the new weights. We call this problem the inverse group 1-median on trees. To solve the problem, we first reformulate the optimality criterion for a vertex being a group 1-median of the tree. Based on this result, we prove that the problem is NP-hard. Particularly, the corresponding problem with exactly two groups is however solvable in O(n2 log n) time, where n is the number of vertices in the tree","number":"1","journal":"Journal of Industrial and Management Optimization","author":[{"propositions":[],"lastnames":["Nguyen"],"firstnames":["Kien","Trung"],"suffixes":[]},{"propositions":[],"lastnames":["Hieu"],"firstnames":["Vo","Nguyen","Minh"],"suffixes":[]},{"propositions":[],"lastnames":["Pham"],"firstnames":["Van","Huy"],"suffixes":[]}],"year":"2021","keywords":"Group median, complexity, inverse optimization, parameterization, tree","pages":"221–232","bibtex":"@article{Pham2021,\n\ttitle = {Inverse {Group} 1-{Median} {Problem} {On} {Trees}},\n\tvolume = {17},\n\tissn = {1553166X},\n\tdoi = {10.3934/jimo.2019108},\n\tabstract = {In location theory, group median generalizes the concepts of both median and center. We address in this paper the problem of modifying vertex weights of a tree at minimum total cost so that a prespecified vertex becomes a group 1-median with respect to the new weights. We call this problem the inverse group 1-median on trees. To solve the problem, we first reformulate the optimality criterion for a vertex being a group 1-median of the tree. Based on this result, we prove that the problem is NP-hard. Particularly, the corresponding problem with exactly two groups is however solvable in O(n2 log n) time, where n is the number of vertices in the tree},\n\tnumber = {1},\n\tjournal = {Journal of Industrial and Management Optimization},\n\tauthor = {Nguyen, Kien Trung and Hieu, Vo Nguyen Minh and Pham, Van Huy},\n\tyear = {2021},\n\tkeywords = {Group median, complexity, inverse optimization, parameterization, tree},\n\tpages = {221--232},\n}\n\n","author_short":["Nguyen, K. T.","Hieu, V. N. M.","Pham, V. H."],"key":"Pham2021-1-1-1-1-1-1-1-1","id":"Pham2021-1-1-1-1-1-1-1-1","bibbaseid":"nguyen-hieu-pham-inversegroup1medianproblemontrees-2021","role":"author","urls":{},"keyword":["Group median","complexity","inverse optimization","parameterization","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":["group median","complexity","inverse optimization","parameterization","tree"],"search_terms":["inverse","group","median","problem","trees","nguyen","hieu","pham"],"title":"Inverse Group 1-Median Problem On Trees","year":2021}