Matroid and knapsack center problems

DOI10.1007/s00453-015-0010-1zbMath1344.68282arXiv1301.0745OpenAlexW2522382150MaRDI QIDQ300451

Danny Z. Chen, Haitao Wang, Jian Li, Hongyu Liang

Publication date: 28 June 2016

Published in: Algorithmica, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.0745

zbMATH Keywords

fault-tolerance\(k\)-center\(k\)-median

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (24)

A Technique for Obtaining True Approximations for k-Center with Covering Constraints ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ 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 ⋮ Fully dynamic clustering and diversity maximization in doubling metrics ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Small Space Stream Summary for Matroid Center ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ A Lottery Model for Center-Type Problems with Outliers ⋮ Unnamed Item ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ A Lottery Model for Center-Type Problems With Outliers ⋮ Generalized Center Problems with Outliers ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The fault-tolerant capacitated \(K\)-center problem
• Clustering to minimize the maximum intercluster distance
• A minimal algorithm for the multiple-choice knapsack problem
• Fault tolerant \(K\)-center problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A Dependent LP-Rounding Approach for the k-Median Problem
• Achieving anonymity via clustering
• Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
• Efficient Algorithms for the Weighted k-Center Problem on a Real Line
• All-Norms and All-L_p-Norms Approximation Algorithms
• New Approximation Results for Resource Replication Problems
• Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
• Asymmetric k -center is log ^* n -hard to approximate
• Budgeted Red-Blue Median and Its Generalizations
• Approximation Schemes for Multi-Budgeted Independence Systems
• Clustering with Diversity
• A Best Possible Heuristic for the k-Center Problem
• Slowing down sorting networks to obtain faster sorting algorithms
• Non-monotone submodular maximization under matroid and knapsack constraints
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Bottleneck extrema

This page was built for publication: Matroid and knapsack center problems