2011/11/07 by Cristina G. Fernandes, Fernandes, Cristina G., Luís A. A. Meira +5 · 1 citation
Business, Management and Accounting · Computer Science · Engineering · #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Optimization and Packing Problems #Optimization and Search Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1111.1672
openalex publication_date 2011/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A systematic technique to bound factor-revealing linear programs is\npresented. We show how to derive a family of upper bound factor-revealing\nprograms (UPFRP), and show that each such program can be solved by a computer\nto bound the approximation factor of an associated algorithm. Obtaining an\nUPFRP is straightforward, and can be used as an alternative to analytical\nproofs, that are usually very long and tedious. We apply this technique to the\nMetric Facility Location Problem (MFLP) and to a generalization where the\ndistance function is a squared metric. We call this generalization the Squared\nMetric Facility Location Problem (SMFLP) and prove that there is no\napproximation factor better than 2.04, assuming P \≠ NP. Then, we analyze\nthe best known algorithms for the MFLP based on primal-dual and LP-rounding\ntechniques when they are applied to the SMFLP. We prove very tight bounds for\nthese algorithms, and show that the LP-rounding algorithm achieves a ratio of\n2.04, and therefore has the best factor for the SMFLP. We use UPFRPs in the\ndual-fitting analysis of the primal-dual algorithms for both the SMFLP and the\nMFLP, improving some of the previous analysis for the MFLP.\n