  Subset selection, which aims to select a subset from a ground set to maximize
some objective function, arises in various applications such as influence
maximization and sensor placement. In real-world scenarios, however, one often
needs to find a subset which is robust against (i.e., is good over) a number of
possible objective functions due to uncertainty, resulting in the problem of
robust subset selection. This paper considers robust subset selection with
monotone objective functions, relaxing the submodular property required by
previous studies. We first show that the greedy algorithm can obtain an
approximation ratio of $1-e^{-\beta\gamma}$, where $\beta$ and $\gamma$ are the
correlation and submodularity ratios of the objective functions, respectively;
and then propose EPORSS, an evolutionary Pareto optimization algorithm that can
utilize more time to find better subsets. We prove that EPORSS can also be
theoretically grounded, achieving a similar approximation guarantee to the
greedy algorithm. In addition, we derive the lower bound of $\beta$ for the
application of robust influence maximization, and further conduct experiments
to validate the performance of the greedy algorithm and EPORSS.
