Improved algorithms for the minmax-regret 1-center and 1-median problems

✍ Scribed by Yu, Hung-I.; Lin, Tzu-Chin; Wang, Biing-Feng

• Book ID: 125524857
• Publisher: Association for Computing Machinery
• Year: 2008
• Tongue: English
• Weight: 258 KB
• Volume: 4
• Category: Article
• ISSN: 1549-6325
• DOI: 10.1145/1367064.1367076

✦ Synopsis

In this article, efficient algorithms are presented for the minmax-regret 1-center and 1-median problems on a general graph and a tree with uncertain vertex weights. For the minmax-regret 1-center problem on a general graph, we improve the previous upper bound from
O
(
mn
^2^
log
n
) to
O
(
mn
log
n
). For the problem on a tree, we improve the upper bound from
O
(
n
^2^
) to
O
(
n
log
^2^
n
). For the minmax-regret 1-median problem on a general graph, we improve the upper bound from
O
(
mn
^2^
log
n
) to
O
(
mn
^2^
+
n
^3^
log
n
). For the problem on a tree, we improve the upper bound from
O
(
n
log
^2^
n
) to
O
(
n
log
n
).