מינאטי דה (מדעי המחשב, טכניון)
יום ראשון, 6.7.2014, 13:00
חדר 337, בניין טאוב למדעי המחשב
The problem of finding the placement of certain number of facilities so that they can serve all the demands efficiently is a very important subject of research. In this talk, we present some fundamental facility location problems in memory-constrained environment. Here the input is considered to be given in a read-only memory and only constant amount of work-space is available for the computation. This model is well-motivated for handling big-data as well as for computing in smart portable devices with small amount of extra-space.
First, we propose a strategy to implement prune-and-search in this model. It will work
even if the input is given in a sequential access read-only memory. Using this we show how to compute (i) the center of the minimum enclosing circle for a set of points in , and (ii) the weighted 1-center and weighted 2-center of a tree network.
The running time of all these algorithms are . We also present optimal linear time algorithm for finding centroid and weighted median of a tree in this model. Our results improve product for all the stated problems.