DocumentCode :
2736873
Title :
Building Steiner trees with incomplete global knowledge
Author :
Karget, D.R. ; Minkoff, Maria
Author_Institution :
Lab. for Comput. Sci., MIT, Cambridge, MA, USA
fYear :
2000
fDate :
2000
Firstpage :
613
Lastpage :
623
Abstract :
A networking problem of present-day interest is that of distributing a single data item to multiple clients while minimizing network usage. Steiner tree algorithms are a natural solution method, but only when the set of clients requesting the data is known. We study what can be done without this global knowledge, when a given vertex knows only the probability that any other client wishes to be connected, and must simply specify a fixed path to the data to be used in case it is requested. Our problem is an example of a class of network design problems with concave cost functions (which arise when the design problem exhibits economies of scale). In order to solve our problem, we introduce a new version of the facility location problem: one in which every open facility is required to have some minimum amount of demand assigned to it. We present a simple bicriterion approximation for this problem, one which is loose in both assignment cost and minimum demand, but within a constant factor of the optimum for both. This suffices for our application. We leave open the question of finding an algorithm that produces a truly feasible approximate solution
Keywords :
approximation theory; client-server systems; combinational switching; facility location; minimisation; network synthesis; trees (mathematics); uncertainty handling; Steiner trees; assignment cost; bicriterion approximation; concave cost functions; connection probability; data item distribution; data-requesting clients; economies of scale; facility location problem; fixed data path specification; incomplete global knowledge; minimum demand; network design problems; network usage minimization; open facilities; vertex; Algorithm design and analysis; Bandwidth; Computer science; Cost function; Degradation; Economies of scale; Joining processes; Laboratories;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on
Conference_Location :
Redondo Beach, CA
ISSN :
0272-5428
Print_ISBN :
0-7695-0850-2
Type :
conf
DOI :
10.1109/SFCS.2000.892329
Filename :
892329
Link To Document :
بازگشت