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
• Matroid and knapsack center problems

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

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

Cited In (3)

• On the DCJ 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)