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)- Student-project allocation with preferences over projects
- The complexity of a minimum reload cost diameter problem
- The power of verification for one-parameter agents
- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- Fast payment schemes for truthful mechanisms with verification
- Approximation algorithm for maximum edge coloring
- An approximation algorithm to the \(k\)-Steiner forest problem
- A lower bound for the hitting set size for combinatorial rectangles and an application
- Minimum partition of an independence system into independent sets
- A cost-sharing method for an economic lot-sizing game
- Approximation algorithms for connected facility location problems
- Red-blue covering problems and the consecutive ones property
- Algorithms for compact letter displays: comparison and evaluation
- On approximating four covering and packing problems
- Approximation algorithms for soft-capacitated facility location in capacitated network design
- A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
- Approximation algorithms for the weighted independent set problem in sparse graphs
- An improved approximation algorithm for uncapacitated facility location problem with penalties
- On the minimum hitting set of bundles problem
- Scheduling jobs with time-resource tradeoff via nonlinear programming
- Priority algorithms for graph optimization problems
- A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
- The reverse greedy algorithm for the metric k-median problem
- A cross-monotonic cost sharing method for the facility location game with service installation costs
- Fast primal and dual heuristics for the \(p\)-median location problem
- Approximating covering integer programs with multiplicity constraints
- Approximability results for stable marriage problems with ties.
- Single machine scheduling with job delivery to multiple customers
- Complexity of single-swap heuristics for metric facility location and related problems
- An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
- Dynamic algorithms via the primal-dual method
- Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
- The Steiner traveling salesman problem with online advanced edge blockages
- Relaxation heuristics for the set multicover problem with generalized upper bound constraints
- A Lagrangian search method for the \(P\)-median problem
- Parameterized approximation via fidelity preserving transformations
- An improved approximation algorithm for the k-level facility location problem with soft capacities
- A local search approximation algorithm for the uniform capacitated k-facility location problem
- An approximation algorithm for soft capacitated k-facility location problem
- On the complexity of clustering with relaxed size constraints in fixed dimension
- A logarithmic approximation for polymatroid congestion games
- Approximation algorithms for the robust facility leasing problem
- The relationship between attribute reducts in rough sets and minimal vertex covers of graphs
- Towards flexible demands in online leasing problems
- An improved approximation algorithm for knapsack median using sparsification
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- The generalized vertex cover problem and some variations
- An empirical analysis of heuristics for solving the two-machine flow shop problem with job release times
- On the approximability of Dodgson and Young elections
- Fast bounding procedures for large instances of the simple plant location problem
- Designing small keyboards is hard
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- On approximation of the vertex cover problem in hypergraphs
- Offline and online facility leasing
- Improved approximation algorithms for multilevel facility location problems
- Selecting hierarchical facilities in a service-operations environment
- Clustering to minimize the sum of cluster diameters
- Algorithms for synthesizing mechanical systems with maximal natural frequencies
- The knapsack problem with neighbour constraints
- A factor 2 approximation algorithm for the vertex cover P₃ problem
- An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
- Approximation algorithms for the fault-tolerant facility placement problem
- Maximum gradient embeddings and monotone clustering
- Connected facility location via random facility sampling and core detouring
- Approximation algorithms for fuzzy \(C\)-means problem based on seeding method
- Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
- Faster balanced clusterings in high dimension
- A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
- Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
- Approximation algorithms for the lower-bounded knapsack median problem
- Local search algorithm for the spherical \(k\)-means problem with outliers
- An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties
- Protecting elections by recounting ballots
- An approximation algorithm for the k-level facility location problem with outliers
- Near-optimal large-scale k-medoids clustering
- An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem
- Near-optimal clustering in the \(k\)-machine model
- The general graph matching game: approximate core
- The traveling \(k\)-median problem: approximating optimal network coverage
- Lossy kernelization of same-size clustering
- Improved approximation algorithms for solving the squared metric k-facility location problem
- Concave connection cost facility location and the star inventory routing problem
- A refined approximation for Euclidean \(k\)-means
- A cost-sharing scheme for the \(k\)-level facility location game with penalties
- Best-response dynamics in combinatorial auctions with item bidding
- Induced star partition of graphs
- An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee
- Approximation algorithm for prize-collecting sweep cover with base stations
- A polynomial-time approximation to a minimum dominating set in a graph
- Approximation algorithms for clustering with dynamic points
- LP-based approximation for uniform capacitated facility location problem
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- The distance-constrained matroid median problem
- Goal scoring, coherent loss and applications to machine learning
- On the complexity and approximation of the maximum expected value all-or-nothing subset
- Robust fitting in computer vision: easy or hard?
- \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space
- An approximation algorithm for the k-prize-collecting multicut on a tree problem
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem
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)
