인터넷겜블 | Cases & Studies in Internet Gambling | 网上赌博
- date : 2015-05-20 01:10|hit : 2447
-
- Article] An online algorithm for the dynamic maximal dense tree problem
-
DocNo of ILP: 6267
Doc. Type: Article
Title: An online algorithm for the dynamic maximal dense tree problem
Authors: Awerbuch, B; Singh, T
Full Name of Authors: Awerbuch, B; Singh, T
Keywords by Author: online algorithms; dense tree; multicast; dynamic
Keywords Plus:
Abstract: The Online Maximal Dense Tree problem is as follows given a weighted directed graph and a source node, users issue online requests for connection to the source node. A request can either be accepted or rejected (the admission control decision). If the connection request is accepted. it must be connected to the source or to a node previously connected to the source (the routing decision). The objective is to maximize the total number of connections while keeping the connection density, i.e. the ratio of accepted requests to the weight of the spanning tree, sufficiently high. The primary motivation for the Maximal Dense Tree problem is the Online Capacitated Multicast admission control and routing problem. In the Online Capacitated Multicast problem, we are given a communication network with limited link capacities and a set of signal source nodes. Users generate online requests fur connection to the signal sources, and the network administrator has to make the admission control and routing decisions. The goal of the network administrator is to maximize the total number of users connected subject to the network capacity constraints, The Online Maximal Dense Tree problem is also faced by a cable TV operator who wishes to connect as many customers as possible while keeping down the amount of wiring per customer. Informally, the Online Maximal Dense Tree algorithm must "gamble" on certain geographic areas connecting nodes which are unprofitable to start with, in the hope that eventually enough requests will arrive in its vicinity to make the investment profitable, In this paper we present a randomized online algorithm for the Maximal Dense Tree problem that guarantee, acceptance of a (1 - epsilon) factor of the requests accepted by the optimum offline algorithm with the expectation of density being at most polylogarithmically lower than that of the offline algorithm, This yields an offline capacitated multicast algorithm whose throughput is only poly-logarithmically lower than that of the optimum offline algorithm. Previous work on multicast routing and maximal dense tree problems either made probabilistic assumptions or resulted in linear performance gaps with the offline algorithm. Attempts to solve the Online Maximal Dense Tree problem have also lead to the development of the first polylogarithmic approximation algorithms for the k-MST and the Prize Collecting Salesman problems [AABV].
Cate of OECD: Computer and information sciences
Year of Publication: 2002
Business Area: gamble
Detail Business: gamble
Country: USA
Study Area:
Name of Journal: ALGORITHMICA
Language: English
Country of Authors: Johns Hopkins Univ, Dept Comp Sci, Baltimore, MD 21218 USA
Press Adress: Awerbuch, B (reprint author), Johns Hopkins Univ, Dept Comp Sci, Baltimore, MD 21218 USA.
Email Address:
Citaion:
Funding:
Lists of Citation: Awerbuch B., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), DOI 10.1109/SFCS.1993.366884; AWERBUCH B, 1996, P ACM S THEOR COMP; AWERBUCH B, 1995, P ACM S THEOR CO MAY; AWERBUCH B, 1993, UNPUB DENSE TREES CO; BALAS E, 1989, NETWORKS, V19, P621, DOI 10.1002/net.3230190602; Deering S. E., 1994, P SIGCOMM; Floyd S., 1995, P SIGCOMM; Garg N., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, DOI 10.1145/195058.195218; GOLDEN BL, 1987, NAV RES LOG, V34, P307, DOI 10.1002/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D; MCCANNE S, 1996, P SIGCOMM, V26; RAVI R, 1994, P 5 ANN ACM SIAM S D; SINGH T, 1999, THESIS J HOPKING U
Number of Citaion: 12
Publication: SPRINGER-VERLAG
City of Publication: NEW YORK
Address of Publication: 175 FIFTH AVE, NEW YORK, NY 10010 USA
ISSN: 0178-4617
29-Character Source Abbreviation: ALGORITHMICA
ISO Source Abbreviation: Algorithmica
Volume: 32
Version: 4
Start of File: 540
End of File: 553
DOI: 10.1007/s00453-001-0086-7
Number of Pages: 14
Web of Science Category: Computer Science, Software Engineering; Mathematics, Applied
Subject Category: Computer Science; Mathematics
Document Delivery Number: 514QF
Unique Article Identifier: WOS:000173452000002
[이 게시물은 HyeJung Mo…님에 의해 2015-05-20 14:44:04 GAMBLING에서 이동 됨]
- reply : 0
-
- list
-
- prev
- next