Summary
The paper studies bicriteria approximation algorithms for sub-modular cover problem (SCP). In the problem, we are given an oracle to some sub-modular function f, and a threshold tau. Our goal is to find the smallest set X such that f(x) >= tau.
The paper is not well-written at all. There are critical typos in the theorem statements, making it hard to understand what the main results are. Only after reading the rebuttal and the supplementary materials carefully, I was able to put all the pieces together. Two main results of the paper are
For the monotone SCP problem (MSCP), the result is an algorithm that achieves O(ln(1/eps))-approximation with 1-epsilon violation on the value, using O_eps(n log n) queries. This improves the previous query complexity of O(n^2). However, the algorithm is called threshold-greedy-c, described in Algorithm 5 in the supplementary material. But the theorem statement says the algorithm is threshold-bi, which is never defined.
The second result is for SCP. It says there is an algorithm that achieves 1/epsilon approximation with 1-epsilon violation on the value. The result uses theorem 2, which converts a randomized algorithm for the dual problem SMP into a randomized algorithm for SCP. The algorithm needs to guess a budget g, and repeat the algorithm for SMP multiple times in order to convert the expectation guarantee into high probability guarantee. However, in the theorem statement, gamma should be epsilon as pointed by the authors in the rebuttal, and alpha is never defined. From the supplementary material, I learnt that alpha is the parameter controlling the multiplicative step size of the guessed size budget g, and the term log |OPT| in the running time should really be log_{1 + alpha} |OPT|.
I am raising my score to borderline reject. There are so many typos in the theorem statements. Yes, they are just a few typos in the whole paper, but I think mistakes in the main theorems, which give the formal descriptions of main results, are intolerable. They are the first things that people will read, and they only take a few lines in the paper.
If I needed to judge the contribution of the results, without taking the typos into consideration, I would say the first result makes a fair improvement, but I do not see too much technical contribution from the second result. It is based on the dual relationship between SCP and SMP, and conversion from expectation to high probability comes from repeating the algorithm multiple times.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.