The distance-constrained matroid median problem

DOI10.1007/S00453-020-00688-5MaRDI QIDQ2182102zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• 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
• A local search algorithm for radius-constrained \(k\)-median
• The ordered anti-median problem with distances derived from a strictly convex norm
• The matroid median problem

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)