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)- Approximation algorithms for Steiner forest: An experimental study
- The l-diversity problem: tractability and approximability
- A probabilistic PTAS for shortest common superstring
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- On the competitive ratio for online facility location
- The generalized assignment problem with minimum quantities
- Fast bounding procedures for large instances of the simple plant location problem
- Incremental medians via online bidding
- Lossy kernelization of same-size clustering
- Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
- Clustering with \(r\)-regular graphs
- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
- Approximation algorithms for the weighted independent set problem in sparse graphs
- Improved approximation algorithms for (budgeted) node-weighted Steiner problems
- Multi-pattern matching with bidirectional indexes
- An approximation algorithm for the dynamic facility location problem with submodular penalties
- Algorithms for synthesizing mechanical systems with maximal natural frequencies
- Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
- Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
- Capacitated domination problem
- Approximation algorithms for the fault-tolerant facility placement problem
- Approximating covering integer programs with multiplicity constraints
- Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
- Approximation Algorithms for Metric Facility Location Problems
- Multi-way sparsest cut problem on trees with a control on the number of parts and outliers
- Performance analysis of a greedy algorithm for inferring Boolean functions
- scientific article; zbMATH DE number 7651196 (Why is no real title available?)
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- A polynomial case of the parsimony haplotyping problem
- Tracking routes in communication networks
- Correlation clustering in general weighted graphs
- Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm
- An approximation algorithm for the \(k\)-level capacitated facility location problem
- Combinatorial model and bounds for target set selection
- Approximate proof-labeling schemes
- The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem
- Local search approximation algorithms for the sum of squares facility location problems
- A polylogarithmic approximation for computing non-metric terminal Steiner trees
- Facility Location with Matroid or Knapsack Constraints
- A lower bound for the hitting set size for combinatorial rectangles and an application
- Simpler and Better Algorithms for Minimum-Norm Load Balancing
- Adding cardinality constraints to integer programs with applications to maximum satisfiability
- Kinetic facility location
- Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
- Descriptive complexity of \#P functions: a new perspective
- Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties
- The ordered \(k\)-median problem: surrogate models and approximation algorithms
- Approximation Algorithms for the k-Median Problem
- An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties
- A Lagrangian-based algorithm for a combinatorial motion planning problem
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- How to allocate hard candies fairly
- Fast payment schemes for truthful mechanisms with verification
- Exponential-time approximation of weighted set cover
- Discrete facility location in machine learning
- Subset-conjunctive rules for breast cancer diagnosis
- On approximating four covering and packing problems
- Approximation algorithm for squared metric facility location problem with nonuniform capacities
- A fast asymptotic approximation scheme for bin packing with rejection
- The Priority k-Median Problem
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- A simple and deterministic competitive algorithm for online facility location
- On full Steiner trees in unit disk graphs
- Simple FPTAS for the subset-sums ratio problem
- A simple algorithm for the multiway cut problem
- Approximation algorithm for facility location with service installation costs
- A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
- Approximability of the capacitated \(b\)-edge dominating set problem
- Simultaneous matchings: Hardness and approximation
- Concave connection cost facility location and the star inventory routing problem
- Semantics-aware influence maximization in social networks
- On some optimization problems in molecular biology
- A cost-sharing method for an economic lot-sizing game
- 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
- A note on systems with max-min and max-product constraints
- Continuous speed scaling with variability: a simple and direct approach
- Combinatorial approximation algorithms for the robust facility location problem with penalties
- Video distribution under multiple constraints
- On a bidirected relaxation for the MULTIWAY CUT problem
- An improved primal-dual approximation algorithm for the \(k\)-means problem with penalties
- scientific article; zbMATH DE number 1947060 (Why is no real title available?)
- On the \(k\)-edge-incident subgraph problem and its variants
- scientific article; zbMATH DE number 7650098 (Why is no real title available?)
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- Approximating \(k\)-median via pseudo-approximation
- A refined approximation for Euclidean \(k\)-means
- Approximation algorithms for art gallery problems in polygons
- An improved approximation algorithm for uncapacitated facility location problem with penalties
- Repairing XML functional dependency violations
- Information-theoretic approaches to branching in search
- On the linear relaxation of the \(p\)-median problem
- Resource allocation problem under single resource assignment
- Improved approximation algorithms for the robust fault-tolerant facility location problem
- A new approximation algorithm for the multilevel facility location problem
- The complexity of a minimum reload cost diameter problem
- Efficient approximation algorithms for clustering point-sets
- Red-blue covering problems and the consecutive ones property
- Analysis of bounds for a capacitated single-item lot-sizing problem
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)
