A systematic approach to bound factor revealing LPs and its application to the metric and squared metric facility location problems

DOI10.1007/978-3-642-32512-0_13zbMATH Open1369.90143arXiv1111.1672OpenAlexW2016301092MaRDI QIDQ747779FDOQ747779

Flávio K. Miyazawa, Lehilton L. C. Pedrosa, Luis A. A. Meira, Cristina G. Fernandes

Publication date: 19 October 2015

Published in: Mathematical Programming. Series A. Series B, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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 $eq$ 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 factor for the SMFLP. We use UPFRPs in the dual-fitting analysis of the primal-dual algorithms for both the SMFLP and the MFLP, improving some of the previous analysis for the MFLP.

Full work available at URL: https://arxiv.org/abs/1111.1672

Recommendations

• A systematic approach to bound factor revealing LPs and its application to the metric and squared metric facility location problems
• scientific article; zbMATH DE number 2086926
• Approximation algorithm for squared metric facility location problem with nonuniform capacities
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Approximation Algorithms for Metric Facility Location Problems

zbMATH Keywords

approximation algorithmfacility locationbound-factor revealing linear program

Mathematics Subject Classification ID

Quadratic programming (90C20) Linear programming (90C05) Combinatorial optimization (90C27) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Cites Work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Online bipartite matching with random arrivals
• A new greedy approach for facility location problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation Algorithms for Metric Facility Location Problems
• Heuristics for the fixed cost median problem

Cited In (12)

• Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
• Local search approximation algorithms for the sum of squares facility location problems
• Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
• An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties
• Approximation algorithm for squared metric facility location problem with nonuniform capacities
• Maximum stable matching with one-sided ties of bounded length
• Approximating the \(\tau\)-relaxed soft capacitated facility location problem
• Approximation algorithm for squared metric two-stage stochastic facility location problem
• \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space
• An improved approximation algorithm for squared metric \(k\)-facility location
• Clustering through continuous facility location problems
• A local search approximation algorithm for a squared metric \(k\)-facility location problem

This page was built for publication: A systematic approach to bound factor revealing LPs and its application to the metric and squared metric facility location problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q747779)