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)
- The \(l\)-diversity problem: tractability and approximability
- A probabilistic PTAS for shortest common superstring
- 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
- On certain connectivity properties of the internet topology
- Soft-capacitated facility location game
- A survey on the structure of approximation classes
- The communication requirements of efficient allocations and supporting prices
- Incremental algorithms for facility location and \(k\)-median
- Student-project allocation with preferences over projects
- Title not available (Why is that?)
- Finding the closest ultrametric
- Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach
- Comments on the hierarchically structured bin packing problem
- An approximation algorithm for the \(k\)-level stochastic facility location problem
- A one-dimensional bin packing problem with shelf divisions
- Near-optimal large-scale k-medoids clustering
- A cost-sharing method for an uncapacitated facility location game with penalties
- Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
- Approximating Independent Set and Coloring in Random Uniform Hypergraphs
- Correcting gene tree by removal and modification: tractability and approximability
- LP-rounding algorithms for the fault-tolerant facility placement problem
- Inapproximability results for graph convexity parameters
- The capacitated orienteering problem
- On a facility location problem with applications to tele-diagnostic
- A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
- Clustering to minimize the sum of cluster diameters
- Partial multicuts in trees
- Algorithms for compact letter displays: comparison and evaluation
- Improved and simplified inapproximability for \(k\)-means
- Approximately dominating representatives
- An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties
- Priority algorithms for graph optimization problems
- Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
- Tracking routes in communication networks
- 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
- 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
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)
