The distance-constrained matroid median problem

DOI10.1007/S00453-020-00688-5zbMATH Open1442.90166OpenAlexW3006244605MaRDI QIDQ2182102FDOQ2182102

Authors: Naoyuki Kamiyama 

Publication date: 21 May 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2324/4479688

Recommendations

• The matroid median problem
• Facility Location with Matroid or Knapsack Constraints
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Improved approximation algorithms for matroid and knapsack median problems and applications

zbMATH Keywords

matroid\(k\)-center problem\(k\)-median problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Combinatorial aspects of matroids and geometric lattices (05B35) Discrete location and assignment (90B80)

Cites Work

• Title not available (Why is that?)
• A Best Possible Heuristic for the k-Center Problem
• A bicriteria approximation algorithm for the \(k\)-center and \(k\)-median problems
• A constant-factor approximation algorithm for the \(k\)-median problem
• A dependent LP-rounding approach for the \(k\)-median problem
• A new greedy approach for facility location problems
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Approximating \(k\)-median via pseudo-approximation
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Clustering to minimize the maximum intercluster distance
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Facility Location with Matroid or Knapsack Constraints
• Improved Combinatorial Algorithms for Facility Location Problems
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Local Search Heuristics for k-Median and Facility Location Problems
• Local search algorithms for the red-blue median problem

Cited In (4)

• On the DCJ Median Problem
• The matroid median problem
• A local search algorithm for radius-constrained \(k\)-median
• The ordered anti-median problem with distances derived from a strictly convex norm

This page was built for publication: The distance-constrained matroid median problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182102)