A Randomized O(log N) -competitive Algorithm For The Online Connected Facility Location Problem

dc.creatorSan Felice
dc.creatorMario Cesar; Williamson
dc.creatorDavid P.; Lee
dc.creatorOrlando
dc.date2016
dc.datedez
dc.date2017-11-13T13:55:08Z
dc.date2017-11-13T13:55:08Z
dc.date.accessioned2018-03-29T06:08:37Z
dc.date.available2018-03-29T06:08:37Z
dc.identifierAlgorithmica. Springer, v. 76, p. 1139 - 1157, 2016.
dc.identifier0178-4617
dc.identifier1432-0541
dc.identifierWOS:000387338900013
dc.identifier10.1007/s00453-016-0115-1
dc.identifierhttps://link.springer.com/article/10.1007/s00453-016-0115-1
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/329586
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1366611
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionThe Connected Facility Location (CFL) is a network design problem that arises from a combination of the Uncapacitated Facility Location (FL) and the Steiner Tree (ST) problems. The Online Connected Facility Location problem (OCFL) is an online version of the CFL. San Felice et al. (2014) presented a randomized algorithm for the OCFL and proved that it is -competitive, where n is the number of clients. That algorithm combines the sample-and-augment framework of Gupta, Kumar, Pal, and Roughgarden with previous algorithms for the Online Facility Location (OFL) and the Online Steiner Tree (OST) problems. In this paper we use a more precise analysis to show that the same algorithm is -competitive. Since there is a lower bound of for this problem, our result achieves the best possible competitive ratio, asymptotically.
dc.description76
dc.description4
dc.description1139
dc.description1157
dc.descriptionSao Paulo Research Foundation (FAPESP) [2009/15535-1]
dc.descriptionNSF [CCF-1115256]
dc.descriptionBolsa de Produtividade do CNPq [303947/2008-0]
dc.descriptionEdital Universal CNPq [477692/2012-5]
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.languageEnglish
dc.publisherSpringer
dc.publisherNew York
dc.relationAlgorithmica
dc.rightsfechado
dc.sourceWOS
dc.subjectOnline Algorithms
dc.subjectCompetitive Analysis
dc.subjectConnected Facility Location
dc.subjectSteiner Tree
dc.subjectApproximation Algorithms
dc.subjectRandomized Algorithms
dc.titleA Randomized O(log N) -competitive Algorithm For The Online Connected Facility Location Problem
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución