Abstract
In the matroid center problem, which generalizes the kcenter problem, we need to pick a set of centers that is an independent set of a matroid with rank r. We study this problem in streaming, where elements of the ground set arrive in the stream. We first show that any randomized onepass streaming algorithm that computes a better than Deltaapproximation for partitionmatroid center must use Omega(r^2) bits of space, where Delta is the aspect ratio of the metric and can be arbitrarily large. This shows a quadratic separation between matroid center and kcenter, for which the Doubling algorithm [Charikar et al., 1997] gives an 8approximation using O(k)space and one pass. To complement this, we give a onepass algorithm for matroid center that stores at most O(r^2 log(1/epsilon)/epsilon) points (viz., stream summary) among which a (7+epsilon)approximate solution exists, which can be found by brute force, or a (17+epsilon)approximation can be found with an efficient algorithm. If we are allowed a second pass, we can compute a (3+epsilon)approximation efficiently.
We also consider the problem of matroid center with z outliers and give a onepass algorithm that outputs a set of O((r^2+rz)log(1/epsilon)/epsilon) points that contains a (15+epsilon)approximate solution. Our techniques extend to knapsack center and knapsack center with z outliers in a straightforward way, and we get algorithms that use space linear in the size of a largest feasible set (as opposed to quadratic space for matroid center).
BibTeX  Entry
@InProceedings{kale:LIPIcs:2019:11235,
author = {Sagar Kale},
title = {{Small Space Stream Summary for Matroid Center}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {20:120:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11235},
URN = {urn:nbn:de:0030drops112359},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.20},
annote = {Keywords: Streaming Algorithms, Matroids, Clustering}
}
Keywords: 

Streaming Algorithms, Matroids, Clustering 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) 
Issue Date: 

2019 
Date of publication: 

17.09.2019 