Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk |
| |
Authors: | Ashish Goel Deborah Estrin |
| |
Affiliation: | (1) Department of Management Science and Engineering and (by courtesy) Computer Science, Stanford University, Terman 311, Stanford CA 94305, USA;(2) Department of Computer Science and Laboratory for Embedded Collaborative Systems (LECS), University of California, Los Angeles, CA 90095-1596, USA |
| |
Abstract: | We consider the problem of finding efficient trees to send
information from k sources to a single sink in a network where
information can be aggregated at intermediate nodes in the tree.
Specifically, we assume that if information from j sources is
traveling over a link, the total information that needs to be
transmitted is f(j). One natural and important (though not
necessarily comprehensive) class of functions is those which are
concave, non-decreasing, and satisfy f(0) = 0. Our goal is to find a
tree which is a good approximation simultaneously to the
optimum trees for all such functions. This problem is
motivated by aggregation in sensor networks, as well as by
buy-at-bulk network design. We present a randomized tree construction algorithm that guarantees
Emaxf Cf/C*(f)] ≤ 1 + log k, where Cf is a random
variable denoting the cost of the tree for function f and C*(f)
is the cost of the optimum tree for function f. To the best of our
knowledge, this is the first result regarding simultaneous
optimization for concave costs. We also show how to derandomize this
result to obtain a deterministic algorithm that guarantees max_f
Cf/C*(f) = O(log k). Both these results are much stronger than
merely obtaining a guarantee on max_f ECf/C*(f)]. A guarantee
on maxf ECf/C*(f)] can be obtained using existing techniques,
but this does not capture simultaneous optimization since no one
tree is guaranteed to be a good approximation for all f
simultaneously. While our analysis is quite involved, the algorithm itself is very
simple and may well find practical use. We also hope that our
techniques will prove useful for other problems where one needs
simultaneous optimization for concave costs. |
| |
Keywords: | Optimization Buy-at-bulk |
本文献已被 SpringerLink 等数据库收录! |
|