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
- Approximate proof-labeling schemes
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- A streaming algorithm for \(k\)-means with approximate coreset
- Subset-conjunctive rules for breast cancer diagnosis
- Faster balanced clusterings in high dimension
- Semantics-aware influence maximization in social networks
- Approximation algorithms for the lower-bounded knapsack median problem
- Local search algorithm for the spherical \(k\)-means problem with outliers
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- Algorithms for synthesizing mechanical systems with maximal natural frequencies
- Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
- Protecting elections by recounting ballots
- An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
- Improved approximation algorithms for (budgeted) node-weighted Steiner problems
- Improved approximation algorithms for a bilevel knapsack problem
- Approximation algorithm for squared metric facility location problem with nonuniform capacities
- A local search approximation algorithm for a squared metric \(k\)-facility location problem
- Parameterized approximation via fidelity preserving transformations
- Local search approximation algorithms for the \(k\)-means problem with penalties
- An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties
- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
- Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
- The Steiner traveling salesman problem with online advanced edge blockages
- Relaxation heuristics for the set multicover problem with generalized upper bound constraints
- An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
- Approximation algorithm for uniform bounded facility location problem
- Approximating minimum-cost connected \(T\)-joins
- Approximation algorithms for fuzzy \(C\)-means problem based on seeding method
- Approximating soft-capacitated facility location problem with uncertainty
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)
