Local search algorithms for the red-blue median problem

DOI10.1007/s00453-011-9547-9zbMath1262.90146MaRDI QIDQ692631

Rohit Khandekar, Guy Kortsarz, Mohammad Taghi Hajiaghayi

Publication date: 6 December 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9547-9

zbMATH Keywords

facility location; local search algorithms; \(k\)-median; prize-collecting

Mathematics Subject Classification ID

90C27: Combinatorial optimization

Related Items

Facility Location with Matroid or Knapsack Constraints, Approximation Algorithms for Matroid and Knapsack Means Problems, Capacitated facility location with outliers/penalties, Local search heuristics for the mobile facility location problem, An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme, An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution, Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties, Improved approximation for prize-collecting red-blue median, Improved approximation algorithms for solving the squared metric \(k\)-facility location problem, An improved approximation algorithm for squared metric \(k\)-facility location, The distance-constrained matroid median problem, An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• Approximation algorithms for geometric median problems
• Improved approximation algorithms for capacitated facility location problems
• A constant-factor approximation algorithm for the \(k\)-median problem
• Assignment problem in content distribution networks
• On the Complexity of Some Common Geometric Location Problems
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• Tight approximation algorithms for maximum general assignment problems
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• The prize collecting traveling salesman problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Local Search Heuristics for k-Median and Facility Location Problems
• A General Approximation Technique for Constrained Forest Problems
• Improved Combinatorial Algorithms for Facility Location Problems
• Integer Programming and Combinatorial Optimization
• Algorithms - ESA 2003
• Algorithms - ESA 2003
• A tight bound on approximating arbitrary metrics by tree metrics