Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation

DOI10.1145/375827.375845zbMATH Open1138.90417OpenAlexW2139841919MaRDI QIDQ3512428FDOQ3512428

Authors:

Publication date: 14 July 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/375827.375845

Recommendations

• scientific article; zbMATH DE number 1670526
• Approximation Algorithms for Metric Facility Location Problems
• scientific article; zbMATH DE number 1947060
• scientific article; zbMATH DE number 1559542
• scientific article; zbMATH DE number 1303535

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Cited In (only showing first 100 items - show all)

• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
• Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
• Algorithms for synthesizing mechanical systems with maximal natural frequencies
• Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
• Approximate proof-labeling schemes
• Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
• Local search approximation algorithms for the sum of squares facility location problems
• An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties
• Subset-conjunctive rules for breast cancer diagnosis
• Approximation algorithm for squared metric facility location problem with nonuniform capacities
• On full Steiner trees in unit disk graphs
• Semantics-aware influence maximization in social networks
• An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
• Approximation algorithms for the robust facility leasing problem
• An improved approximation algorithm for knapsack median using sparsification
• Towards flexible demands in online leasing problems
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• A region growing algorithm for detecting critical nodes
• Approximation algorithm for squared metric two-stage stochastic facility location problem
• Approximation algorithms for spherical \(k\)-means problem using local search scheme
• The generalized vertex cover problem and some variations
• Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
• Mathematical programming formulations and algorithms for discrete \(k\)-median clustering of time-series data
• Dynamic algorithms via the primal-dual method
• Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
• \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space
• Local search approximation algorithms for the \(k\)-means problem with penalties
• An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee
• Approximating soft-capacitated facility location problem with uncertainty
• Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem
• Faster balanced clusterings in high dimension
• Polynomial approximation algorithms with performance guarantees: an introduction-by-example
• An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties
• The Steiner traveling salesman problem with online advanced edge blockages
• Relaxation heuristics for the set multicover problem with generalized upper bound constraints
• Improved approximation algorithms for a bilevel knapsack problem
• A complexity and approximation framework for the maximization scaffolding problem
• Approximation algorithms for the lower-bounded knapsack median problem
• Local search algorithm for the spherical \(k\)-means problem with outliers
• An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
• Maximum gradient embeddings and monotone clustering
• Approximation algorithm for uniform bounded facility location problem
• FPT approximation schemes for maximizing submodular functions
• An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
• The distance-constrained matroid median problem
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• Parameterized approximation via fidelity preserving transformations
• Approximate the lower-bounded connected facility location problem
• Approximating minimum-cost connected \(T\)-joins
• Approximability of the upper chromatic number of hypergraphs
• A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem
• An approximation algorithm for soft capacitated \(k\)-facility location problem
• Computing and Combinatorics
• A logarithmic approximation for polymatroid congestion games
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Approximation algorithms for fuzzy \(C\)-means problem based on seeding method
• The \(l\)-diversity problem: tractability and approximability
• A probabilistic PTAS for shortest common superstring
• A systematic approach to bound factor revealing LPs and its application to the metric and squared metric facility location problems
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Fast bounding procedures for large instances of the simple plant location problem
• Approximation algorithms for the weighted independent set problem in sparse graphs
• Multi-pattern matching with bidirectional indexes
• An approximation algorithm for the dynamic facility location problem with submodular penalties
• Approximation algorithms for the fault-tolerant facility placement problem
• Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
• Approximating covering integer programs with multiplicity constraints
• An approximation algorithm for the \(k\)-level capacitated facility location problem
• A polylogarithmic approximation for computing non-metric terminal Steiner trees
• A Lagrangian-based algorithm for a combinatorial motion planning problem
• How to allocate hard candies fairly
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Fast payment schemes for truthful mechanisms with verification
• Exponential-time approximation of weighted set cover
• On approximating four covering and packing problems
• Approximation algorithm for facility location with service installation costs
• A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
• An improved primal-dual approximation algorithm for the \(k\)-means problem with penalties
• A cost-sharing method for an economic lot-sizing game
• On the \(k\)-edge-incident subgraph problem and its variants
• A refined approximation for Euclidean \(k\)-means
• Repairing XML functional dependency violations
• Information-theoretic approaches to branching in search
• On the linear relaxation of the \(p\)-median problem
• A new approximation algorithm for the multilevel facility location problem
• The complexity of a minimum reload cost diameter problem
• Red-blue covering problems and the consecutive ones property
• On approximation of the vertex cover problem in hypergraphs
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• Approximation schemes for knapsack problems with shelf divisions
• A unified framework of FPT approximation algorithms for clustering problems
• An approximation algorithm for the \(k\)-median warehouse-retailer network design problem
• Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
• Approximation algorithms for covering/packing integer programs
• On the \(p\)-median polytope of \(Y\)-free graphs
• Selfish splittable flows and NP-completeness
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• On optimal approximability results for computing the strong metric dimension
• A Lagrangian search method for the \(P\)-median problem

This page was built for publication: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation

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