Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/242541
Type: Artigo de periódico
Title: A Systematic Approach To Bound Factor-revealing Lps And Its Application To The Metric And Squared Metric Facility Location Problems
Author: Fernandes
Cristina G.; Meira
Luis A. A.; Miyazawa
Flavio K.; Pedrosa
Lehilton L. C.
Abstract: A systematic technique to bound factor-revealing linear programs is presented. We show how to derive a family of upper bound factor-revealing programs (UPFRP), and show that each such program can be solved by a computer to bound the approximation factor of an associated algorithm. Obtaining an UPFRP is straightforward, and can be used as an alternative to analytical proofs, that are usually very long and tedious. We apply this technique to the metric facility location problem (MFLP) and to a generalization where the distance function is a squared metric. We call this generalization the squared metric facility location problem (SMFLP), and prove that there is no approximation factor better than 2.04, assuming P not equal NP. Then, we analyze the best known algorithms for the MFLP based on primal-dual and LP-rounding techniques when they are applied to the SMFLP. We prove very tight bounds for these algorithms, and show that the LP-rounding algorithm achieves a ratio of 2.04, and therefore has the best possible factor for the SMFLP. We use UPFRPs in the dualfitting analysis of the primal-dual algorithms for both the SMFLP and the MFLP, improving some of the previous analysis for the MFLP.
Subject: Approximation Algorithms
Country: HEIDELBERG
Editor: SPRINGER HEIDELBERG
Citation: A Systematic Approach To Bound Factor-revealing Lps And Its Application To The Metric And Squared Metric Facility Location Problems. Springer Heidelberg, v. 153, p. 655-685 NOV-2015.
Rights: fechado
Identifier DOI: 10.1007/s10107-014-0821-x
Address: http://link.springer.com/article/10.1007%2Fs10107-014-0821-x
Date Issue: 2015
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
wos_000364330300014.pdf701.61 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.