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)

• Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
• Tracking routes in communication networks
• Synchronization problems in automata without non-trivial cycles
• Capacitated domination problem
• Performance analysis of a greedy algorithm for inferring Boolean functions
• Facility Location with Matroid or Knapsack Constraints
• Approximation Algorithms for the k-Median Problem
• A lower bound for the hitting set size for combinatorial rectangles and an application
• The Priority k-Median Problem
• A simple and deterministic competitive algorithm for online facility location
• On a bidirected relaxation for the MULTIWAY CUT problem
• A note on systems with max-min and max-product constraints
• Video distribution under multiple constraints
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• Approximation algorithms for the Bipartite Multicut problem
• An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme
• A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
• Approximability results for stable marriage problems with ties.
• Lagrangian relaxation for the \(k\)-median problem: new insights and continuity properties
• Smoothed analysis of binary search trees
• Approximation algorithm for resource allocation problems with time dependent penalties
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Improved approximation algorithms for multilevel facility location problems
• Approximation and online algorithms for multidimensional bin packing: a survey
• Grouping objects in multi-band images using an improved eigenvector-based algorithm
• Incremental facility location problem and its competitive algorithms
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• Approximation algorithms for the partition vertex cover problem
• A cost-sharing scheme for the \(k\)-level facility location game with penalties
• Eisenberg-Gale markets: algorithms and game-theoretic properties
• An approximation algorithm for the stochastic fault-tolerant facility location problem
• Local search algorithms for \(k\)-median and \(k\)-facility location problems with linear penalties
• A rounding algorithm for approximating minimum Manhattan networks
• Approximation schemes for \(k\)-facility location
• Pricing commodities
• On the complexity of isoperimetric problems on trees
• Approximation algorithms for maximum cut with limited unbalance
• Contention-aware data caching in wireless multi-hop ad hoc networks
• Approximating set multi-covers
• An improved approximation algorithm for the \(k\)-level facility location problem with soft capacities
• A primal-dual approximation algorithm for stochastic facility location problem with service installation costs
• The maximum integer multiterminal flow problem in directed graphs
• Comparing and Aggregating Partially Resolved Trees
• On the integrality gap of the prize-collecting Steiner forest LP
• On the probabilistic minimum coloring and minimum \(k\)-coloring
• Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
• A list heuristic for vertex cover
• A polynomial-time approximation to a minimum dominating set in a graph
• Quick k-Median, k-Center, and Facility Location for Sparse Graphs
• Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
• Covering problems in edge- and node-weighted graphs
• New primal-dual algorithms for Steiner tree problems
• Approximation algorithms for the dynamic \(k\)-level facility location problems
• Improved and simplified inapproximability for \(k\)-means
• The relationship between attribute reducts in rough sets and minimal vertex covers of graphs
• Privacy preserving clustering with constraints
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Approximation algorithms for connected facility location problems
• A genetic algorithm approach for regrouping service sites
• Randomized priority algorithms
• A distributed O(1)-approximation algorithm for the uniform facility location problem
• 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

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)