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)
- 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
- 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
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)
