Home // ADVCOMP 2012, The Sixth International Conference on Advanced Engineering Computing and Applications in Sciences // View article

Minmax Regret 1-Center on a Path/Cycle/Tree

Authors:
Binay Bhattacharya
Tsunehiko Kameda
Zhao Song

Keywords: facility location, 1-center, minmax regret, cycle, tree

Abstract:
In a facility location problem in computational geometry, if the vertex weights are uncertain one may look for a ``robust'' solution that minimizes ``regret." The best previously known algorithm for finding the minmax regret 1-center in a tree with positive vertex weights is due to Yu et al., and runs in sub-quadratic asymptotic time in the number of vertices. Assuming that the minimum weight of at least one vertex is non-negative, we present a new, conceptually simpler algorithm for a tree with the same time complexity, as well as an algorithm that runs in linear (respectively sub-quadratic) time for a path (respectively cycle).

Pages: 108 to 113

Copyright: Copyright (c) IARIA, 2012

Publication date: September 23, 2012

Published in: conference

ISSN: 2308-4499

ISBN: 978-1-61208-237-0

Location: Barcelona, Spain

Dates: from September 23, 2012 to September 28, 2012