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
• Approximation algorithms for the robust facility leasing problem
• An improved approximation algorithm for knapsack median using sparsification
• Towards flexible demands in online leasing problems
• 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
• 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
• 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
• A streaming algorithm for \(k\)-means with approximate coreset
• 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
• Protecting elections by recounting ballots
• 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
• 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
• On the competitive ratio for online facility location
• Incremental medians via online bidding
• Clustering with \(r\)-regular graphs
• The generalized assignment problem with minimum quantities
• Approximation Algorithms for Metric Facility Location Problems
• A polynomial case of the parsimony haplotyping problem
• Correlation clustering in general weighted graphs
• Combinatorial model and bounds for target set selection
• A fast asymptotic approximation scheme for bin packing with rejection
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• On some optimization problems in molecular biology
• Simultaneous matchings: Hardness and approximation
• Title not available (Why is that?)
• Continuous speed scaling with variability: a simple and direct approach
• Approximating \(k\)-median via pseudo-approximation
• Combinatorial approximation algorithms for the robust facility location problem with penalties
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• Approximation algorithms for art gallery problems in polygons
• Improved approximation algorithms for the robust fault-tolerant facility location problem
• Efficient approximation algorithms for clustering point-sets
• Differential approximation of MIN SAT, MAX SAT and related problems
• LP-based approximation algorithms for capacitated facility location
• Approximation algorithms for the robust/soft-capacitated 2-level facility location problems
• Beyond Moulin mechanisms
• Approximation algorithms for soft-capacitated facility location in capacitated network design
• Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
• A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
• Offline and Online Facility Leasing
• A cross-monotonic cost sharing method for the facility location game with service installation costs
• Integrality gaps for strengthened linear relaxations of capacitated facility location
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Finding large degree-anonymous subgraphs is hard
• Title not available (Why is that?)
• The power of verification for one-parameter agents
• A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
• Robust ordinal regression for dominance-based rough set approach to multiple criteria sorting
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• An alternative approach for proving the NP-hardness of optimization problems
• Improved algorithms for joint optimization of facility locations and network connections
• Matching interdiction
• Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs
• Centrality of trees for capacitated \(k\)-center
• A note on scenario reduction for two-stage stochastic programs
• Cross-monotonic cost sharing methods for connected facility location games
• Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover 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)