2020/10/02 by Shadravan, Mohammad · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2010.01901
First, for the for the submodular k-secretary problem with shortlists [1], we provide a near optimal 1-1/e-ε approximation using shortlist of size O(k poly(1/ε)). In particular, we improve the size of shortlist used in \citeus from O(k 2poly(1/ε)) to O(k poly(1/ε)). As a result, we provide a near optimal approximation algorithm for random-order streaming of monotone submodular functions under cardinality constraints, using memory O(k poly(1/ε)). It exponentially improves the running time and memory of \citeus in terms of 1/ε. Next we generalize the problem to matroid constraints, which we refer to as submodular matroid secretary problem with shortlists. It is a variant of the matroid secretary problem \citefeldman2014simple, in which the algorithm is allowed to have a shortlist. We design an algorithm that achieves a (1)/(2)(1-1/e2 -ε) competitive ratio for any constant ε>0, using a shortlist of size O(k poly(\frac1ε)). Moreover, we generalize our results to the case of p-matchoid constraints and give a (1)/(p+1)(1-1/ep+1-ε) approximation using shortlist of size O(k poly(\frac1ε)). It asymptotically approaches the best known offline guarantee (1)/(p+1) [22]. Furthermore, we show that our algorithms can be implemented in the streaming setting using O(k poly(\frac1ε)) memory.