Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
From MaRDI portal
Publication:3512428
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
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)
- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
- Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
- A Streaming Algorithm for k-Means with Approximate Coreset
- 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
- 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
- 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
- Protecting elections by recounting ballots
- Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
- Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
- A Region Growing Algorithm for Detecting Critical Nodes
- An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
- Maximum gradient embeddings and monotone clustering
- Mathematical Programming Formulations and Algorithms for Discrete k-Median Clustering of Time-Series Data
- 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
- Approximation algorithms for fuzzy \(C\)-means problem based on seeding method
- 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
- Real time scheduling with a budget: parametric-search is better than binary search
- Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
- 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
- On the Integrality Gap of the Prize-Collecting Steiner Forest LP
- 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
- Title not available (Why is that?)
- Eisenberg-Gale markets: algorithms and game-theoretic properties
- An approximation algorithm for the stochastic fault-tolerant facility location problem
- 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
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)
