Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications

DOI10.1145/2963170zbMath1446.68199OpenAlexW1524471135MaRDI QIDQ4962627

Chaitanya Swamy

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4712/

zbMATH Keywords

linear programmingfacility locationapproximation algorithmsknapsack constraints\(k\)-medianLP roundingmatroid mediansubmodular polyhedramatroid polyhedra

Mathematics Subject Classification ID

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

Related Items (11)

Constant approximation for fault-tolerant median problems via iterative rounding ⋮ Approximation algorithms for clustering with dynamic points ⋮ On some variants of Euclidean \(k\)-supplier ⋮ The distance-constrained matroid median problem ⋮ On clustering with discounts ⋮ Approximation Algorithms for Matroid and Knapsack Means Problems ⋮ Approximation algorithms for diversity-bounded center problems ⋮ The Euclidean k-Supplier Problem ⋮ Unnamed Item ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ Improved approximation for prize-collecting red-blue median

This page was built for publication: Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications