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.375845zbMATH Open1138.90417OpenAlexW2139841919MaRDI QIDQ3512428FDOQ3512428
Authors:
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
Recommendations
Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Discrete location and assignment (90B80)
Cited In (only showing first 100 items - show all)
- On the competitive ratio for online facility location
- Incremental medians via online bidding
- Clustering with \(r\)-regular graphs
- The generalized assignment problem with minimum quantities
- Approximation Algorithms for Metric Facility Location Problems
- A polynomial case of the parsimony haplotyping problem
- Correlation clustering in general weighted graphs
- Combinatorial model and bounds for target set selection
- A fast asymptotic approximation scheme for bin packing with rejection
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- On some optimization problems in molecular biology
- Simultaneous matchings: Hardness and approximation
- Title not available (Why is that?)
- Continuous speed scaling with variability: a simple and direct approach
- Approximating \(k\)-median via pseudo-approximation
- Combinatorial approximation algorithms for the robust facility location problem with penalties
- An improved approximation algorithm for uncapacitated facility location problem with penalties
- Approximation algorithms for art gallery problems in polygons
- Improved approximation algorithms for the robust fault-tolerant facility location problem
- Efficient approximation algorithms for clustering point-sets
- Differential approximation of MIN SAT, MAX SAT and related problems
- LP-based approximation algorithms for capacitated facility location
- Approximation algorithms for the robust/soft-capacitated 2-level facility location problems
- Beyond Moulin mechanisms
- Approximation algorithms for soft-capacitated facility location in capacitated network design
- Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
- A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
- Offline and Online Facility Leasing
- A cross-monotonic cost sharing method for the facility location game with service installation costs
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- Finding large degree-anonymous subgraphs is hard
- Title not available (Why is that?)
- The power of verification for one-parameter agents
- A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
- Robust ordinal regression for dominance-based rough set approach to multiple criteria sorting
- A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
- An alternative approach for proving the NP-hardness of optimization problems
- Improved algorithms for joint optimization of facility locations and network connections
- Matching interdiction
- Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs
- Centrality of trees for capacitated \(k\)-center
- A note on scenario reduction for two-stage stochastic programs
- Cross-monotonic cost sharing methods for connected facility location games
- Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
- Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
- Hardness and inapproximability of convex recoloring problems
- Multi-facility ordered median problems in directed networks
- On the complexity of clustering with relaxed size constraints in fixed dimension
- Approximation of min-max and min-max regret versions of some combinatorial optimization problems
- An approximation algorithm for a facility location problem with stochastic demands and inventories
- Deterministic versus randomized adaptive test cover
- Finding a collective set of items: from proportional multirepresentation to group recommendation
- A unified approach to approximating partial covering problems
- Efficient approximation of convex recolorings
- Efficient approximation schemes for uniform-cost clustering problems in planar graphs
- Primal-dual schema and Lagrangian relaxation for the \(k\)-location-routing problem
- A primal-dual algorithm for online non-uniform facility location
- Local search algorithms for the red-blue median problem
- Scheduling jobs with time-resource tradeoff via nonlinear programming
- Constant factor approximation algorithm for the knapsack median problem
- A new approximation algorithm for the \(k\)-facility location problem
- A cross-monotonic cost-sharing scheme for the concave facility location game
- Approximation algorithms for the fault-tolerant facility location problem with penalties
- On the computational complexities of three problems related to a privacy measure for large networks under active attack
- Clustering through continuous facility location problems
- Towards the price of leasing online
- A primal-dual approximation algorithm for the facility location problem with submodular penalties
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Minimum Cell Connection in Line Segment Arrangements
- The \(k\)-level facility location game
- LP-based algorithms for capacitated facility location
- Efficient algorithms for online decision problems
- There is no EPTAS for two-dimensional knapsack
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Graph clustering
- An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
- Connected facility location via random facility sampling and core detouring
- Approximation Algorithms for the Robust Facility Location Problem with Penalties
- Cut problems in graphs with a budget constraint
- Offline and online facility leasing
- Approximation algorithm for maximum edge coloring
- 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
- \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
- Deformable spanners and applications
- An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
- Erratum to: ``Internet shopping with price-sensitive discounts
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- Better guarantees for \(k\)-median with service installation costs
- Improved approximation algorithms for (budgeted) node-weighted Steiner problems
- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
- Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
- Algorithms for synthesizing mechanical systems with maximal natural frequencies
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Approximate proof-labeling schemes
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- Local search approximation algorithms for the sum of squares facility location problems
- An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties
- Subset-conjunctive rules for breast cancer diagnosis
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)
