Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
From MaRDI portal
Publication:3452509
DOI10.1145/950620.950621zbMath1325.90060arXivcs/0207028OpenAlexW2052494364MaRDI QIDQ3452509
No author found.
Publication date: 12 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0207028
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties, Combinatorial approximation algorithms for the robust facility location problem with penalties, Flexible Graph Connectivity, Beyond Moulin mechanisms, An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution, Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs, Approximation algorithms for hard capacitated \(k\)-facility location problems, Integrality gaps for strengthened linear relaxations of capacitated facility location, A DISTRIBUTED APPROXIMATION ALGORITHM FOR FAULT-TOLERANT METRIC FACILITY LOCATION, The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem, Clustering with or without the approximation, A new approximation algorithm for the \(k\)-facility location problem, An Improved Approximation Bound for Spanning Star Forest and Color Saving, An improved approximation algorithm for squared metric \(k\)-facility location, Improved parameterized approximation for balanced \(k\)-median, Analysis of a local search algorithm for the k-facility location problem, A hybrid multistart heuristic for the uncapacitated facility location problem, Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties, An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs, Approximation algorithms for facility location problems with a special class of subadditive cost functions, Tight approximation bounds for combinatorial frugal coverage algorithms, Approximation algorithms for inventory problems with submodular or routing costs, Bifactor approximation for location routing with vehicle and facility capacities, LP-based approximation for uniform capacitated facility location problem, Mechanisms for dual-role-facility location games: truthfulness and approximability, Incremental facility location problem and its competitive algorithms, Approximation Algorithms for the Robust Facility Location Problem with Penalties, Solving Facility Location Problem Based on Duality Approach, An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties, An approximation algorithm for the \(k\)-level stochastic facility location problem, An approximation algorithm for the \(k\)-level capacitated facility location problem, Perturbation resilience for the facility location problem, Discrete facility location in machine learning, An approximation algorithm for the dynamic facility location problem with submodular penalties, Offline and Online Facility Leasing, An improved approximation algorithm for the \(k\)-level facility location problem with soft capacities, Approximation algorithms for the fault-tolerant facility location problem with penalties, Approximation algorithm for squared metric facility location problem with nonuniform capacities, Recovery guarantees for exemplar-based clustering, An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions, Approximation algorithm for squared metric two-stage stochastic facility location problem, Approximation Algorithms for Stochastic and Risk-Averse Optimization, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Approximation algorithms for the fault-tolerant facility placement problem, Maximum gradient embeddings and monotone clustering, Near-optimal asymmetric binary matrix partitions, A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem, Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms, LP-Based Algorithms for Capacitated Facility Location, Unnamed Item, Approximate the lower-bounded connected facility location problem, Improved approximation algorithms for the robust fault-tolerant facility location problem, A primal-dual approximation algorithm for stochastic facility location problem with service installation costs, Connected facility location via random facility sampling and core detouring, Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach, LP-rounding algorithms for the fault-tolerant facility placement problem, Tight Approximation Bounds for Greedy Frugal Coverage Algorithms, Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties, A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem, Approximation algorithms for the robust facility leasing problem, Towards flexible demands in online leasing problems, Approximation algorithms for the robust/soft-capacitated 2-level facility location problems, An improved approximation algorithm for knapsack median using sparsification, Mobile facility location: combinatorial filtering via weighted occupancy, A distributed O(1)-approximation algorithm for the uniform facility location problem, Fault-tolerant concave facility location problem with uniform requirements, Incremental medians via online bidding, A new approximation algorithm for the multilevel facility location problem, Competitive cost sharing with economies of scale, Unnamed Item, A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties, An approximation algorithm for a facility location problem with stochastic demands and inventories, Approximation algorithms for the lower-bounded \(k\)-median and its generalizations, Approximating the \(\tau\)-relaxed soft capacitated facility location problem, Integrating facility location and production planning decisions, A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games, An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme, Offline and online facility leasing, Approximating $k$-Median via Pseudo-Approximation, Improved approximation for prize-collecting red-blue median, An approximation algorithm to the \(k\)-Steiner forest problem, LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem, An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties, An approximation algorithm for the \(k\)-level facility location problem with outliers, An approximation algorithm for the stochastic fault-tolerant facility location problem, An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties, Improved approximation algorithms for the facility location problems with linear/submodular penalties, A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems, An improved approximation algorithm for uncapacitated facility location problem with penalties, Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems, An effective linear approximation method for separable programming problems, An LP rounding algorithm for approximating uncapacitated facility location problem with penalties, An approximation algorithm for stochastic multi-level facility location problem with soft capacities, Oblivious algorithms for the maximum directed cut problem, Improved approximation algorithms for constrained fault-tolerant resource allocation, Improved approximation algorithms for solving the squared metric \(k\)-facility location problem, Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties), Concave connection cost facility location and the star inventory routing problem, Flexible graph connectivity, Parametric packing of selfish items and the subset sum algorithm, Approximability results for the $p$-centdian and the converse centdian problems, Approximation algorithms for the fault-tolerant facility location problem with submodular penalties, Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship, Approximation schemes for \(k\)-facility location, A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties, Integrated Supply Chain Management via Randomized Rounding, A unified framework of FPT approximation algorithms for clustering problems, A per-scenario bound for the two-stage stochastic facility location problem with linear penalty, On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem, A local search approximation algorithm for a squared metric \(k\)-facility location problem, Maximum stable matching with one-sided ties of bounded length, Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks, Unnamed Item
