Greedy Strikes Back: Improved Facility Location Algorithms
From MaRDI portal
Publication:4240134
DOI10.1006/JAGM.1998.0993zbMATH Open0928.68137DBLPjournals/jal/GuhaK99OpenAlexW4243637616WikidataQ57568237 ScholiaQ57568237MaRDI QIDQ4240134FDOQ4240134
Authors: Sudipto Guha, Samir Khuller 
Publication date: 9 January 2000
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1998.0993
Recommendations
Cited In (only showing first 100 items - show all)
- Easy capacitated facility location problems, with connections to lot-sizing
- Greedy algorithms for the single-demand facility location problem
- Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
- Local search approximation algorithms for the sum of squares facility location problems
- A \(k\)-product uncapacitated facility location problem
- Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
- Iterative partial rounding for vertex cover with hard capacities
- Kinetic facility location
- An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties
- Approximation algorithm for squared metric facility location problem with nonuniform capacities
- On parameterized approximation algorithms for balanced clustering
- Approximation algorithms for stochastic clustering
- Concave connection cost facility location and the star inventory routing problem
- To close is easier than to open: dual parameterization to \(k\)-median
- Polynomial time approximation schemes for clustering in low highway dimension graphs
- Efficient black-box reductions for separable cost sharing
- Efficient black-box reductions for separable cost sharing
- On Hop-Constrained Steiner Trees in Tree-Like Metrics
- Complexity of single-swap heuristics for metric facility location and related problems
- Approximation algorithms for the robust facility leasing problem
- Improved approximation algorithms for constrained fault-tolerant resource allocation
- An approximation algorithm for the \(k\)-level facility location problem with outliers
- Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
- Approximating the \(\tau\)-relaxed soft capacitated facility location problem
- 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
- On the cost of essentially fair clusterings
- An approximation algorithm for the dynamic facility location problem with outliers
- An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties
- A primal-dual 3-approximation algorithm for the stochastic facility location problem with submodular penalties
- Dynamic sum-radii clustering
- An improved approximation algorithm for squared metric \(k\)-facility location
- Improved parameterized approximation for balanced \(k\)-median
- Title not available (Why is that?)
- Approximation algorithms for hierarchical location problems
- Recent developments in approximation algorithms for facility location and clustering problems
- Title not available (Why is that?)
- LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem
- Perturbation resilience for the facility location problem
- On the power of static assignment policies for robust facility location problems
- A local search approximation algorithm for a squared metric \(k\)-facility location problem
- The minimum \(k\)-storage problem on directed graphs
- A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem
- An approximation algorithm for soft capacitated \(k\)-facility location problem
- The traveling \(k\)-median problem: approximating optimal network coverage
- Approximation algorithms for the transportation problem with market choice and related models
- Solving facility location problem based on duality approach
- Bounding quality of pure Nash equilibria in dual-role facility location games
- On Min-Max r-Gatherings
- Improved approximation algorithm for fault-tolerant facility placement
- The facility location problem with general cost functions
- Title not available (Why is that?)
- An approximation algorithm for the dynamic facility location problem with submodular penalties
- Approximation algorithms for the fault-tolerant facility placement problem
- Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties)
- A General k-Level Uncapacitated Facility Location Problem
- An approximation algorithm for the \(k\)-level capacitated facility location problem
- The General Steiner Tree-Star problem.
- Fault-tolerant concave facility location problem with uniform requirements
- Approximating \(k\)-hop minimum-spanning trees
- Approximation algorithm for facility location with service installation costs
- Approximating \(k\)-median via pseudo-approximation
- A hybrid multistart heuristic for the uncapacitated facility location problem
- Combinatorial approximation algorithms for the robust facility location problem with penalties
- A constant-factor approximation algorithm for the \(k\)-median problem
- An improved approximation algorithm for uncapacitated facility location problem with penalties
- A new approximation algorithm for the multilevel facility location problem
- Improved approximation algorithms for the robust fault-tolerant facility location problem
- A unified framework of FPT approximation algorithms for clustering problems
- Approximation algorithms for facility location problems with a special class of subadditive cost functions
- Beyond Moulin mechanisms
- Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
- 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
- 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
- Approximation algorithm for resource allocation problems with time dependent penalties
- Title not available (Why is that?)
- Problem-driven scenario clustering in stochastic optimization
- Improved approximation algorithms for multilevel facility location problems
- Inapproximability of the multi-level uncapacitated facility location problem
- Incremental facility location problem and its competitive algorithms
- Soft-capacitated facility location game
- Data stability in clustering: a closer look
- Centrality of trees for capacitated \(k\)-center
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Improved approximation algorithms for capacitated facility location problems
- An approximation algorithm for a large-scale facility location problem
- An approximation algorithm for the stochastic fault-tolerant facility location problem
- Incremental algorithms for facility location and \(k\)-median
- Approximating the two-level facility location problem via a quasi-greedy approach
- An approximation algorithm for a facility location problem with stochastic demands and inventories
- Approximation schemes for \(k\)-facility location
- Non-cooperative facility location and covering games
- Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach
- On min-max \(r\)-gatherings
- Efficient approximation schemes for uniform-cost clustering problems in planar graphs
- An approximation algorithm for the \(k\)-level stochastic facility location problem
This page was built for publication: Greedy Strikes Back: Improved Facility Location Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4240134)
