Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation

DOI10.1145/375827.375845zbMATH Open1138.90417OpenAlexW2139841919MaRDI QIDQ3512428

Author name not available (Why is that?)

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

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
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
Analysis of bounds for a capacitated single-item lot-sizing problem
Approximation algorithms for the Bipartite Multicut problem
Approximation algorithms for facility location problems with a special class of subadditive cost functions
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.
On the Integrality Gap of the Prize-Collecting Steiner Forest LP
Fast primal and dual heuristics for the \(p\)-median location problem
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
Selecting hierarchical facilities in a service-operations environment
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 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
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
The relationship between attribute reducts in rough sets and minimal vertex covers of graphs
Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties
Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties
Approximation algorithms for connected facility location problems
A genetic algorithm approach for regrouping service sites
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
Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks
An approximation algorithm for the \(k\)-level capacitated facility location problem
A polylogarithmic approximation for computing non-metric terminal Steiner trees
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
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
Approximation algorithms for covering/packing integer programs
Smoothed analysis of binary search trees
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

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)