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

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

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

(40)

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

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)