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)- 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
- Approximation algorithm for squared metric two-stage stochastic facility location problem
- Approximation algorithms for spherical \(k\)-means problem using local search scheme
- A region growing algorithm for detecting critical nodes
- On full Steiner trees in unit disk graphs
- The generalized vertex cover problem and some variations
- Approximation algorithms for the robust facility leasing problem
- A logarithmic approximation for polymatroid congestion games
- An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties
- The distance-constrained matroid median problem
- Mathematical programming formulations and algorithms for discrete \(k\)-median clustering of time-series data
- A complexity and approximation framework for the maximization scaffolding problem
- Approximability of the upper chromatic number of hypergraphs
- Local search approximation algorithms for the sum of squares facility location problems
- Dynamic algorithms via the primal-dual method
- Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
- Approximate the lower-bounded connected facility location problem
- An improved approximation algorithm for knapsack median using sparsification
- Towards flexible demands in online leasing problems
- Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem
- A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem
- An approximation algorithm for soft capacitated \(k\)-facility location problem
- Maximum gradient embeddings and monotone clustering
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space
- Computing and Combinatorics
- 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
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)
