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)- Approximate proof-labeling schemes
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- A streaming algorithm for \(k\)-means with approximate coreset
- Subset-conjunctive rules for breast cancer diagnosis
- Faster balanced clusterings in high dimension
- Semantics-aware influence maximization in social networks
- Approximation algorithms for the lower-bounded knapsack median problem
- Local search algorithm for the spherical \(k\)-means problem with outliers
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- Algorithms for synthesizing mechanical systems with maximal natural frequencies
- Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
- Protecting elections by recounting ballots
- An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
- Improved approximation algorithms for (budgeted) node-weighted Steiner problems
- Improved approximation algorithms for a bilevel knapsack problem
- Approximation algorithm for squared metric facility location problem with nonuniform capacities
- A local search approximation algorithm for a squared metric \(k\)-facility location problem
- Parameterized approximation via fidelity preserving transformations
- Local search approximation algorithms for the \(k\)-means problem with penalties
- An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties
- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
- Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
- The Steiner traveling salesman problem with online advanced edge blockages
- Relaxation heuristics for the set multicover problem with generalized upper bound constraints
- An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
- Approximation algorithm for uniform bounded facility location problem
- Approximating minimum-cost connected \(T\)-joins
- Approximation algorithms for fuzzy \(C\)-means problem based on seeding method
- Approximating soft-capacitated facility location problem with uncertainty
- Approximation algorithm for squared metric two-stage stochastic facility location problem
- Approximation algorithms for spherical \(k\)-means problem using local search scheme
- A region growing algorithm for detecting critical nodes
- On full Steiner trees in unit disk graphs
- The generalized vertex cover problem and some variations
- Approximation algorithms for the robust facility leasing problem
- A logarithmic approximation for polymatroid congestion games
- An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties
- The distance-constrained matroid median problem
- Mathematical programming formulations and algorithms for discrete \(k\)-median clustering of time-series data
- A complexity and approximation framework for the maximization scaffolding problem
- Approximability of the upper chromatic number of hypergraphs
- Local search approximation algorithms for the sum of squares facility location problems
- Dynamic algorithms via the primal-dual method
- Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
- Approximate the lower-bounded connected facility location problem
- An improved approximation algorithm for knapsack median using sparsification
- Towards flexible demands in online leasing problems
- Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem
- A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem
- An approximation algorithm for soft capacitated \(k\)-facility location problem
- Maximum gradient embeddings and monotone clustering
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space
- Computing and Combinatorics
- 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
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)
