The matroid median problem

MaRDI QIDQ5365103zbMATH OpenFDO

Authors Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, Barna Saha

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133120

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• 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
• A dependent LP-rounding approach for the k-median problem
• The distance-constrained matroid median problem

Cited in

(39)

• Clustering what matters in constrained settings: improved outlier to outlier-free reductions
• Improved approximation algorithms for matroid and knapsack means problems
• Uniform capacitated facility location with outliers/penalties
• Facility Location with Matroid or Knapsack Constraints
• New approximation results for resource replication problems
• The Priority k-Median Problem
• Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
• Clustering with a knapsack constraint: parameterized approximation algorithms for the knapsack median problem
• Approximation algorithms for diversity-bounded center problems
• Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
• An improved approximation algorithm for knapsack median using sparsification
• Small Space Stream Summary for Matroid Center
• scientific article; zbMATH DE number 1138199 (Why is no real title available?)
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Approximation algorithms for clustering with dynamic points
• On the DCJ Median Problem
• Improved approximation for prize-collecting red-blue median
• Constant approximation for fault-tolerant median problems via iterative rounding
• Local search heuristics for the mobile facility location problem
• A lottery model for center-type problems with outliers
• On clustering with discounts
• The Lazy Matroid Problem
• The Hamiltonian p-median problem
• A dependent LP-rounding approach for the k-median problem
• Local search algorithms for the red-blue median problem
• LP-based approximation for uniform capacitated facility location problem
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Respecting lower bounds in uniform lower and upper bounded facility location problem
• Constant factor approximation algorithm for the knapsack median problem
• LP-based algorithms for capacitated facility location
• A Lottery Model for Center-Type Problems With Outliers
• Towards a theoretical understanding of why local search works for clustering with fair-center representation
• An improved approximation algorithm for knapsack median using sparsification
• The distance-constrained matroid median problem
• Approximation Algorithms for Matroid and Knapsack Means Problems
• Exploring the median of permutations problem
• Clustering under a knapsack constraint: parameterized approximation for the knapsack median problem
• Facility location with red-blue demands
• Clustering what matters in constrained settings (improved outlier to outlier-free reductions)

This page was built for publication: The matroid median problem

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