Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks

详细信息    查看全文

• 作者：Binay Bhattacharya^a ; ^{binay@sfu.ca" class="auth_mail" title="E-mail the corresponding author} ; Tsunehiko Kameda^a ; ^{tiko@sfu.ca" class="auth_mail" title="E-mail the corresponding author} ; Zhao Song^b ; ^{zhaos@utexas.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Facility location ; 1-center problem ; Minmax regret optimization ; Robust solution ; Uncertain weight
• 刊名：Discrete Applied Mathematics
• 出版年：2015
• 出版时间：20 November 2015
• 年：2015
• 卷：195
• 期：Complete
• 页码：18-30
• 全文大小：600 K

文摘

In a model of facility location problem, uncertain vertex weights are represented by intervals of possible weights, and one looks for a “robust” solution that minimizes the maximum “regret” (Kouvelis et al., 1993). We first give an O(n)$O\left(n\right)$ time algorithm for the path networks, and then present an O(nlogn)$O(nlogn)$ time algorithm for the tree networks, which improves upon the previously best algorithm for this problem (Yu et al., 2008) with time complexity O(nlog²n)$O\left(n{log}^{2}n\right)$. We also present an O(nlogn)$O(nlogn)$ time algorithm for the unicycle networks, which contain just one cycle. Our cactus algorithm runs in O(nlog²n)$O\left(n{log}^{2}n\right)$ time. There is no previously published result tailored specifically for cactus networks. In solving these problems, we introduce a number of data structures, which we believe are useful for other applications.