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)- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- A unified approach to approximating partial covering problems
- LP-based approximation algorithms for capacitated facility location
- An improved approximation algorithm for uncapacitated facility location problem with penalties
- An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
- Approximation algorithms for art gallery problems in polygons
- On the competitive ratio for online facility location
- A new approximation algorithm for the \(k\)-facility location problem
- Continuous speed scaling with variability: a simple and direct approach
- A primal-dual algorithm for online non-uniform facility location
- Graph clustering
- There is no EPTAS for two-dimensional knapsack
- On some optimization problems in molecular biology
- Incremental medians via online bidding
- A cross-monotonic cost-sharing scheme for the concave facility location game
- An empirical analysis of heuristics for solving the two-machine flow shop problem with job release times
- Robust ordinal regression for dominance-based rough set approach to multiple criteria sorting
- On the approximability of Dodgson and Young elections
- Approximating \(k\)-median via pseudo-approximation
- A fast asymptotic approximation scheme for bin packing with rejection
- Erratum to: ``Internet shopping with price-sensitive discounts
- Beyond Moulin mechanisms
- Approximation algorithms for the robust/soft-capacitated 2-level facility location problems
- Combinatorial approximation algorithms for the robust facility location problem with penalties
- A polynomial case of the parsimony haplotyping problem
- An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Cut problems in graphs with a budget constraint
- Approximation algorithms for soft-capacitated facility location in capacitated network design
- \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
- Clustering with \(r\)-regular graphs
- Deformable spanners and applications
- Correlation clustering in general weighted graphs
- Better guarantees for \(k\)-median with service installation costs
- Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
- Hardness and inapproximability of convex recoloring problems
- A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
- A note on scenario reduction for two-stage stochastic programs
- Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
- Simultaneous matchings: Hardness and approximation
- Clustering through continuous facility location problems
- Towards the price of leasing online
- Improved approximation algorithms for the robust fault-tolerant facility location problem
- A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
- 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
- Offline and Online Facility Leasing
- Local search algorithms for the red-blue median problem
- A cross-monotonic cost sharing method for the facility location game with service installation costs
- Efficient approximation algorithms for clustering point-sets
- Multi-facility ordered median problems in directed networks
- A primal-dual approximation algorithm for the facility location problem with submodular penalties
- Offline and online facility leasing
- Differential approximation of MIN SAT, MAX SAT and related problems
- Efficient algorithms for online decision problems
- Cross-monotonic cost sharing methods for connected facility location games
- 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
- The generalized assignment problem with minimum quantities
- Approximation Algorithms for Metric Facility Location Problems
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Finding large degree-anonymous subgraphs is hard
- Scheduling jobs with time-resource tradeoff via nonlinear programming
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Connected facility location via random facility sampling and core detouring
- scientific article; zbMATH DE number 1947060 (Why is no real title available?)
- Efficient approximation of convex recolorings
- Minimum Cell Connection in Line Segment Arrangements
- scientific article; zbMATH DE number 1670526 (Why is no real title available?)
- The power of verification for one-parameter agents
- An alternative approach for proving the NP-hardness of optimization problems
- Improved algorithms for joint optimization of facility locations and network connections
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- Primal-dual schema and Lagrangian relaxation for the \(k\)-location-routing problem
- Matching interdiction
- Efficient approximation schemes for uniform-cost clustering problems in planar graphs
- Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs
- An approximation algorithm for a facility location problem with stochastic demands and inventories
- Constant factor approximation algorithm for the knapsack median problem
- Deterministic versus randomized adaptive test cover
- The \(k\)-level facility location game
- Finding a collective set of items: from proportional multirepresentation to group recommendation
- Centrality of trees for capacitated \(k\)-center
- Approximation algorithm for maximum edge coloring
- A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
- Approximation Algorithms for the Robust Facility Location Problem with Penalties
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- Combinatorial model and bounds for target set selection
- LP-based algorithms for capacitated facility location
- Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
- Local search algorithms for \(k\)-median and \(k\)-facility location problems with linear penalties
- A primal-dual approximation algorithm for stochastic facility location problem with service installation costs
- A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
- Pricing commodities
- Approximation algorithms for connected facility location problems
- Approximation Algorithms for the k-Median Problem
- Randomized priority algorithms
- Approximation algorithms for maximum cut with limited unbalance
- A list heuristic for vertex cover
- A polynomial-time approximation to a minimum dominating set in a graph
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)
