Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
From MaRDI portal
Publication:3512428
DOI10.1145/375827.375845zbMath1138.90417OpenAlexW2139841919MaRDI QIDQ3512428
No author found.
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) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items
Approximation schemes for knapsack problems with shelf divisions, Combinatorial approximation algorithms for the robust facility location problem with penalties, Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems, Beyond Moulin mechanisms, Performance analysis of a greedy algorithm for inferring Boolean functions, A note on systems with max-min and max-product constraints, Integrality gaps for strengthened linear relaxations of capacitated 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, An alternative approach for proving the NP-hardness of optimization problems, Improved algorithms for joint optimization of facility locations and network connections, Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs, Deterministic versus randomized adaptive test cover, Finding a collective set of items: from proportional multirepresentation to group recommendation, Analysis of bounds for a capacitated single-item lot-sizing problem, Approximation of min-max and min-max regret versions of some combinatorial optimization problems, Approximation algorithms for facility location problems with a special class of subadditive cost functions, Partial multicuts in trees, Clustering through continuous facility location problems, Towards the price of leasing online, New primal-dual algorithms for Steiner tree problems, On a facility location problem with applications to tele-diagnostic, Approximately dominating representatives, Matching interdiction, Differential approximation of MIN SAT, MAX SAT and related problems, Grouping objects in multi-band images using an improved eigenvector-based algorithm, Incremental facility location problem and its competitive algorithms, An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties, An approximation algorithm for the \(k\)-level stochastic facility location problem, The \(l\)-diversity problem: tractability and approximability, An approximation algorithm for the \(k\)-level capacitated facility location problem, A probabilistic PTAS for shortest common superstring, Multi-pattern matching with bidirectional indexes, An approximation algorithm for the dynamic facility location problem with submodular penalties, A polylogarithmic approximation for computing non-metric terminal Steiner trees, Catastrophic cascading failures in power networks, Centrality of trees for capacitated \(k\)-center, Combinatorial model and bounds for target set selection, Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Pricing commodities, A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs, Repairing XML functional dependency violations, Information-theoretic approaches to branching in search, On the linear relaxation of the \(p\)-median problem, A unified approach to approximating partial covering problems, An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs, Contention-aware data caching in wireless multi-hop ad hoc networks, Improved approximation algorithms for the robust fault-tolerant facility location problem, A primal-dual approximation algorithm for stochastic facility location problem with service installation costs, Graph clustering, A survey on the structure of approximation classes, A primal-dual approximation algorithm for the vertex cover \(P^3\) problem, A primal-dual algorithm for online non-uniform facility location, Approximation algorithm for facility location with service installation costs, Selfish splittable flows and NP-completeness, Approximation schemes for deal splitting and covering integer programs with multiplicity constraints, Finding the closest ultrametric, Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach, Simultaneous matchings: Hardness and approximation, Comments on the hierarchically structured bin packing problem, LP-based approximation algorithms for capacitated facility location, Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms, Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length, A cost-sharing method for an uncapacitated facility location game with penalties, Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees, LP-rounding algorithms for the fault-tolerant facility placement problem, Correcting gene tree by removal and modification: tractability and approximability, Inapproximability results for graph convexity parameters, The capacitated orienteering problem, Improved and simplified inapproximability for \(k\)-means, Robust ordinal regression for dominance-based rough set approach to multiple criteria sorting, George Dantzig's impact on the theory of computation, On the \(p\)-median polytope of \(Y\)-free graphs, \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems, On optimal approximability results for computing the strong metric dimension, Approximation algorithms for the robust/soft-capacitated 2-level facility location problems, Continuous speed scaling with variability: a simple and direct approach, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, A distributed O(1)-approximation algorithm for the uniform facility location problem, Local search algorithms for the red-blue median problem, Capacitated domination problem, A new approximation algorithm for the multilevel facility location problem, Approximation algorithms for art gallery problems in polygons, Kinetic facility location, Multi-facility ordered median problems in directed networks, Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Cross-monotonic cost sharing methods for connected facility location games, A simple and deterministic competitive algorithm for online facility location, Video distribution under multiple constraints, Randomized priority algorithms, An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme, Efficient approximation algorithms for clustering point-sets, An approximation algorithm for the stochastic fault-tolerant facility location problem, Approximation algorithms for the partition vertex cover problem, Improved approximation algorithms for the facility location problems with linear/submodular penalties, A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems, On the complexity of isoperimetric problems on trees, There is no EPTAS for two-dimensional knapsack, The generalized assignment problem with minimum quantities, A genetic algorithm approach for regrouping service sites, A primitive-based 3D segmentation algorithm for mechanical CAD models, An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties, Smoothed analysis of binary search trees, Approximation algorithms for hard capacitated \(k\)-facility location problems, Adding cardinality constraints to integer programs with applications to maximum satisfiability, A new approximation algorithm for the \(k\)-facility location problem, On some optimization problems in molecular biology, Efficient approximation of convex recolorings, The maximum integer multiterminal flow problem in directed graphs, A list heuristic for vertex cover, A primal-dual approximation algorithm for partial vertex cover: Making educated guesses, Approximation algorithm for uniform bounded facility location problem, A cross-monotonic cost-sharing scheme for the concave facility location game, Approximation and online algorithms for multidimensional bin packing: a survey, Semantics-aware influence maximization in social networks, On Lagrangian relaxation for constrained maximization and reoptimization problems, Approximating set multi-covers, Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability, The pairwise flowtime network construction problem, On clustering with discounts, On the computational complexities of three problems related to a privacy measure for large networks under active attack, Local search approximation algorithms for the \(k\)-means problem with penalties, An approximation algorithm for the dynamic facility location problem with outliers, A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem, Approximation algorithms for the fault-tolerant facility location problem with penalties, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Approximation algorithm for squared metric facility location problem with nonuniform capacities, Approximation algorithm for squared metric two-stage stochastic facility location problem, \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space, Euclidean prize-collecting Steiner forest, A primal-dual approximation algorithm for the facility location problem with submodular penalties, An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem, Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization, Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results, Simple FPTAS for the subset-sums ratio problem, Hardness and inapproximability of convex recoloring problems, Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem, Multi-way sparsest cut problem on trees with a control on the number of parts and outliers, On the \(k\)-edge-incident subgraph problem and its variants, Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem, Computing the differential of a graph: hardness, approximability and exact algorithms, Descriptive complexity of \#P functions: a new perspective, Approximation algorithms for the dynamic \(k\)-level facility location problems, Approximation algorithms for spherical \(k\)-means problem using local search scheme, Approximation algorithms for maximum cut with limited unbalance, Approximability of the capacitated \(b\)-edge dominating set problem, Cut problems in graphs with a budget constraint, How to allocate hard candies fairly, Cache placement in sensor networks under an update cost constraint, The \(k\)-level facility location game, A note on scenario reduction for two-stage stochastic programs, An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem, Parallel approximation for partial set cover, On the competitive ratio for online facility location, A rounding algorithm for approximating minimum Manhattan networks, A 4.31-approximation for the geometric unique coverage problem on unit disks, Mobile facility location: combinatorial filtering via weighted occupancy, Approximating soft-capacitated facility location problem with uncertainty, A fast asymptotic approximation scheme for bin packing with rejection, A one-dimensional bin packing problem with shelf divisions, Approximation algorithms for constructing some required structures in digraphs, Minimum vertex cover problem for coupled interdependent networks with cascading failures, Incremental medians via online bidding, Erratum to: ``Internet shopping with price-sensitive discounts, A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems, Subset-conjunctive rules for breast cancer diagnosis, On the probabilistic minimum coloring and minimum \(k\)-coloring, On certain connectivity properties of the internet topology, Soft-capacitated facility location game, An approximation algorithm for a facility location problem with stochastic demands and inventories, A polynomial case of the parsimony haplotyping problem, \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem, Efficient scheduling of periodic information monitoring requests, Clustering with \(r\)-regular graphs, The communication requirements of efficient allocations and supporting prices, Local search approximation algorithms for the sum of squares facility location problems, Correlation clustering in general weighted graphs, Asymmetry in \(k\)-center variants, Incremental algorithms for facility location and \(k\)-median, Deformable spanners and applications, New LP relaxations for minimum cycle/path/tree cover problems, Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth, A simple algorithm for the multiway cut problem, LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem, Cache me if you can: capacitated selfish replication games in networks, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting, The ordered \(k\)-median problem: surrogate models and approximation algorithms, Cooperative games with overlapping coalitions: charting the tractability frontier, On a bidirected relaxation for the MULTIWAY CUT problem, Efficient algorithms for online decision problems, Approximation algorithms for covering/packing integer programs, Approximating minimum-cost connected \(T\)-joins, Approximability of the upper chromatic number of hypergraphs, Improved approximation algorithms for constrained fault-tolerant resource allocation, Approximating the optimal sequence of acquisitions and sales with a capped budget, On full Steiner trees in unit disk graphs, Approximate spanning cactus, A complexity and approximation framework for the maximization scaffolding problem, Improved approximation algorithms for a bilevel knapsack problem, Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems, An improved primal-dual approximation algorithm for the k-means problem with penalties, Design of Dynamic Algorithms via Primal-Dual Method, Approximation Algorithms for the Multilevel Facility Location Problem with Linear/Submodular Penalties, The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem, Analysis of a local search algorithm for the k-facility location problem, Resource allocation problem under single resource assignment, Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties, Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems, On the Integrality Gap of the Prize-Collecting Steiner Forest LP, A Region Growing Algorithm for Detecting Critical Nodes, Approximation Algorithms for the Robust Facility Location Problem with Penalties, Solving Facility Location Problem Based on Duality Approach, Better guarantees for \(k\)-median with service installation costs, Discrete facility location in machine learning, Effective Heuristic Techniques for Combined Robust Clustering Problem, Matheuristics: survey and synthesis, Approximation algorithms for Steiner forest: An experimental study, Agile optimization for a real‐time facility location problem in Internet of Vehicles networks, Universal Algorithms for Clustering Problems, Offline and Online Facility Leasing, The provably good parallel seeding algorithms for the k‐means problem with penalties, Simple and efficient bi-objective search algorithms via fast dominance checks, Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center, Multi-robot motion planning for unit discs with revolving areas, Scalable timing-aware network design via Lagrangian decomposition, Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Approximation algorithms for the fault-tolerant facility location problem with submodular penalties, The facility location problem with maximum distance constraint, An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions, Unnamed Item, On the Minimum Hitting Set of Bundles Problem, Unnamed Item, An approximation algorithm for \(P\)-prize-collecting set cover problem, Unnamed Item, Approximation schemes for \(k\)-facility location, Unnamed Item, Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs, A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties, A semi brute-force search approach for (balanced) clustering, Mathematical Programming Formulations and Algorithms for Discrete k-Median Clustering of Time-Series Data, Finding Points in General Position, Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms, LP-Based Algorithms for Capacitated Facility Location, Unnamed Item, Approximate the lower-bounded connected facility location problem, New algorithms for a simple measure of network partitioning, Unnamed Item, Unnamed Item, Unnamed Item, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, When polynomial approximation meets exact computation, A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem, Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP, Capacitated Domination Problem, A Streaming Algorithm for k-Means with Approximate Coreset, On percolation and ‐hardness, Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics, Batching-Based Approaches for Optimized Packing of Jobs in the Spatial Scheduling Problem, The Parallel Seeding Algorithm for k-Means Problem with Penalties, Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties, When polynomial approximation meets exact computation, A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem, A unified framework of FPT approximation algorithms for clustering problems, Unnamed Item, Lossy kernelization of same-size clustering, Approximating Independent Set and Coloring in Random Uniform Hypergraphs, Unnamed Item, On Lagrangian Relaxation and Subset Selection Problems, A local search approximation algorithm for a squared metric \(k\)-facility location problem, Online facility assignment, Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems, Approximating \(k\)-forest with resource augmentation: a primal-dual approach, Approximate proof-labeling schemes, New algorithms for a simple measure of network partitioning, Finding large degree-anonymous subgraphs is hard, Comparing and Aggregating Partially Resolved Trees, Approximating $k$-Median via Pseudo-Approximation, The Priority k-Median Problem, Simpler and Better Algorithms for Minimum-Norm Load Balancing, Covering and packing of rectilinear subdivision, Tracking routes in communication networks, An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties, Approximation Algorithms for Distributed Multi-robot Coverage in Non-convex Environments, Synchronization problems in automata without non-trivial cycles, Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem, Locating Depots for Capacitated Vehicle Routing, Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm, Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem, Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks, Facility Location with Matroid or Knapsack Constraints, Unnamed Item, Minimum Cell Connection in Line Segment Arrangements, Selecting hierarchical facilities in a service-operations environment, A refined approximation for Euclidean \(k\)-means, 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, Clustering to minimize the sum of cluster diameters, A cost-sharing scheme for the \(k\)-level facility location game with penalties, 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, Best-response dynamics in combinatorial auctions with item bidding, Relaxation heuristics for the set multicover problem with generalized upper bound constraints, 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, A Lagrangian search method for the \(P\)-median problem, Algorithms for synthesizing mechanical systems with maximal natural frequencies, Why did the shape of your network change? (On detecting network anomalies via non-local curvatures), The distance-constrained matroid median problem, FPT approximation schemes for maximizing submodular functions, The knapsack problem with neighbour constraints, Parameterized approximation via fidelity preserving transformations, An improved approximation algorithm for the \(k\)-level facility location problem with soft capacities, 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?, Approximating covering integer programs with multiplicity constraints, A factor \(2\) approximation algorithm for the vertex cover \(P_3\) 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, 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, Connected facility location via random facility sampling and core detouring, Approximability results for stable marriage problems with ties., 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, 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, Covering problems in edge- and node-weighted graphs, 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, Faster balanced clusterings in high dimension, Designing small keyboards is hard, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, 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, On approximation of the vertex cover problem in hypergraphs, Exponential-time approximation of weighted set cover, Approximation algorithms for the Bipartite Multicut problem, Eisenberg-Gale markets: algorithms and game-theoretic properties, Student-project allocation with preferences over projects, Approximation algorithms for the lower-bounded knapsack median problem, Local search algorithm for the spherical \(k\)-means problem with outliers, The complexity of a minimum reload cost diameter problem, The power of verification for one-parameter agents, Offline and online facility leasing, 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, 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, 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, Near-optimal large-scale k-medoids clustering, Red-blue covering problems and the consecutive ones property, Algorithms for compact letter displays: comparison and evaluation, On approximating four covering and packing problems, An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem, Approximation algorithms for soft-capacitated facility location in capacitated network design, Near-optimal clustering in the \(k\)-machine model, 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, The general graph matching game: approximate core, 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, The traveling \(k\)-median problem: approximating optimal network coverage, A cross-monotonic cost sharing method for the facility location game with service installation costs, Lossy kernelization of same-size clustering, Improved approximation algorithms for solving the squared metric \(k\)-facility location problem, Improved approximation algorithms for multilevel facility location problems, Concave connection cost facility location and the star inventory routing problem
