Matroid and knapsack center problems

DOI10.1007/978-3-642-36694-9_10zbMATH Open1344.68282arXiv1301.0745OpenAlexW2522382150MaRDI QIDQ300451FDOQ300451

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)

Abstract: In the classic $k$-center problem, we are given a metric graph, and the objective is to open $k$ nodes as centers such that the maximum distance from any vertex to its closest center is minimized. In this paper, we consider two important generalizations of $k$-center, the matroid center problem and the knapsack center problem. Both problems are motivated by recent content distribution network applications. Our contributions can be summarized as follows: 1. We consider the matroid center problem in which the centers are required to form an independent set of a given matroid. We show this problem is NP-hard even on a line. We present a 3-approximation algorithm for the problem on general metrics. We also consider the outlier version of the problem where a given number of vertices can be excluded as the outliers from the solution. We present a 7-approximation for the outlier version. 2. We consider the (multi-)knapsack center problem in which the centers are required to satisfy one (or more) knapsack constraint(s). It is known that the knapsack center problem with a single knapsack constraint admits a 3-approximation. However, when there are at least two knapsack constraints, we show this problem is not approximable at all. To complement the hardness result, we present a polynomial time algorithm that gives a 3-approximate solution such that one knapsack constraint is satisfied and the others may be violated by at most a factor of $1+epsilon$. We also obtain a 3-approximation for the outlier version that may violate the knapsack constraint by $1+epsilon$.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Algorithms for facility location problems with outliers. (Extended abstract)
• Clustering to minimize the maximum intercluster distance
• A Best Possible Heuristic for the k-Center Problem
• Bottleneck extrema
• Fault tolerant \(K\)-center problems
• Asymmetric k -center is log ^* n -hard to approximate
• Slowing down sorting networks to obtain faster sorting algorithms
• A minimal algorithm for the multiple-choice knapsack problem
• 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
• Budgeted Red-Blue Median and Its Generalizations
• Approximation Schemes for Multi-Budgeted Independence Systems
• Clustering with Diversity
• The fault-tolerant capacitated \(K\)-center problem
• Non-monotone submodular maximization under matroid and knapsack constraints
• Submodular function maximization via the multilinear relaxation and contention resolution schemes

Cited In (29)

• Fully dynamic clustering and diversity maximization in doubling metrics
• Parameterized complexity of categorical clustering with size constraints
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• A technique for obtaining true approximations for \(k\)-center with covering constraints
• A Lottery Model for Center-Type Problems with Outliers
• Title not available (Why is that?)
• Approximation algorithms for diversity-bounded center problems
• Title not available (Why is that?)
• Parameterized complexity of categorical clustering with size constraints
• Small Space Stream Summary for Matroid Center
• Approximation algorithms for clustering with dynamic points
• Representative families for matroid intersections, with applications to location, packing, and covering problems
• Title not available (Why is that?)
• Connected \(k\)-center and \(k\)-diameter clustering
• On some variants of Euclidean \(k\)-supplier
• Constant approximation for fault-tolerant median problems via iterative rounding
• On clustering with discounts
• 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
• Approximation Algorithms for Matroid and Knapsack Means Problems
• The distance-constrained matroid median problem
• Title not available (Why is that?)
• FPT approximation for capacitated clustering with outliers
• Title not available (Why is that?)
• The fair \(k\)-center with outliers problem: FPT and polynomial approximations
• The Euclidean k-Supplier Problem
• Title not available (Why is that?)
• New algorithms for fair \(k\)-center problem with outliers and capacity constraints

Uses Software

• Knapsack

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

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