Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
From MaRDI portal
Publication:3512428
Recommendations
Cited in
(only showing first 100 items - show all)- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- A one-dimensional bin packing problem with shelf divisions
- Correcting gene tree by removal and modification: tractability and approximability
- LP-rounding algorithms for the fault-tolerant facility placement problem
- Approximately dominating representatives
- Near-optimal large-scale k-medoids clustering
- Approximation schemes for knapsack problems with shelf divisions
- Inapproximability results for graph convexity parameters
- The capacitated orienteering problem
- The \(l\)-diversity problem: tractability and approximability
- A probabilistic PTAS for shortest common superstring
- Approximation algorithm for facility location with service installation costs
- The communication requirements of efficient allocations and supporting prices
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- Repairing XML functional dependency violations
- Information-theoretic approaches to branching in search
- On the linear relaxation of the \(p\)-median problem
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Partial multicuts in trees
- A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
- On optimal approximability results for computing the strong metric dimension
- Fast payment schemes for truthful mechanisms with verification
- Fast bounding procedures for large instances of the simple plant location problem
- Clustering to minimize the sum of cluster diameters
- A new approximation algorithm for the multilevel facility location problem
- Exponential-time approximation of weighted set cover
- A polylogarithmic approximation for computing non-metric terminal Steiner trees
- Soft-capacitated facility location game
- Multi-pattern matching with bidirectional indexes
- The complexity of a minimum reload cost diameter problem
- Priority algorithms for graph optimization problems
- An approximation algorithm for the dynamic facility location problem with submodular penalties
- A Lagrangian search method for the \(P\)-median problem
- On approximating four covering and packing problems
- Incremental algorithms for facility location and \(k\)-median
- On a facility location problem with applications to tele-diagnostic
- An improved primal-dual approximation algorithm for the \(k\)-means problem with penalties
- Red-blue covering problems and the consecutive ones property
- Approximation algorithms for covering/packing integer programs
- Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
- Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
- A cost-sharing method for an economic lot-sizing game
- An approximation algorithm for the \(k\)-median warehouse-retailer network design problem
- An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties
- Approximating Independent Set and Coloring in Random Uniform Hypergraphs
- Student-project allocation with preferences over projects
- A unified framework of FPT approximation algorithms for clustering problems
- A Lagrangian-based algorithm for a combinatorial motion planning problem
- On certain connectivity properties of the internet topology
- Algorithms for compact letter displays: comparison and evaluation
- Selfish splittable flows and NP-completeness
- Approximation algorithms for the fault-tolerant facility placement problem
- Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
- scientific article; zbMATH DE number 1445291 (Why is no real title available?)
- A refined approximation for Euclidean \(k\)-means
- On approximation of the vertex cover problem in hypergraphs
- Improved and simplified inapproximability for \(k\)-means
- A cost-sharing method for an uncapacitated facility location game with penalties
- Approximating covering integer programs with multiplicity constraints
- An approximation algorithm for the \(k\)-level stochastic facility location problem
- A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
- A 4.31-approximation for the geometric unique coverage problem on unit disks
- Approximation algorithms for the weighted independent set problem in sparse graphs
- An approximation algorithm for the \(k\)-level capacitated facility location problem
- How to allocate hard candies fairly
- On the \(p\)-median polytope of \(Y\)-free graphs
- 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
- A survey on the structure of approximation classes
- On the \(k\)-edge-incident subgraph problem and its variants
- Local search algorithms for \(k\)-median and \(k\)-facility location problems with linear penalties
- A primal-dual approximation algorithm for stochastic facility location problem with service installation costs
- A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
- Pricing commodities
- Approximation algorithms for connected facility location problems
- Approximation Algorithms for the k-Median Problem
- Randomized priority algorithms
- Approximation algorithms for maximum cut with limited unbalance
- A list heuristic for vertex cover
- A polynomial-time approximation to a minimum dominating set in a graph
- Approximability results for stable marriage problems with ties.
- Performance analysis of a greedy algorithm for inferring Boolean functions
- Approximation schemes for \(k\)-facility location
- Video distribution under multiple constraints
- The maximum integer multiterminal flow problem in directed graphs
- Approximation algorithms for the Bipartite Multicut problem
- On the complexity of isoperimetric problems on trees
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- On the integrality gap of the prize-collecting Steiner forest LP
- On the probabilistic minimum coloring and minimum \(k\)-coloring
- A lower bound for the hitting set size for combinatorial rectangles and an application
- Quick k-Median, k-Center, and Facility Location for Sparse Graphs
- An improved approximation algorithm for the \(k\)-level facility location problem with soft capacities
- Approximation and online algorithms for multidimensional bin packing: a survey
- Eisenberg-Gale markets: algorithms and game-theoretic properties
- An approximation algorithm for the stochastic fault-tolerant facility location problem
- New primal-dual algorithms for Steiner tree problems
- A genetic algorithm approach for regrouping service sites
- Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
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)
