Abstract
We introduce the problem of maximizing approximately $k$-submodular functionssubject to size constraints. In this problem, one seeks to select $k$-disjointsubsets of a ground set with bounded total size or individual sizes, andmaximum utility, given by a function that is "close" to being $k$-submodular.The problem finds applications in tasks such as sensor placement, where onewishes to install $k$ types of sensors whose measurements are noisy, andinfluence maximization, where one seeks to advertise $k$ topics to users of asocial network whose level of influence is uncertain. To deal with the problem,we first provide two natural definitions for approximately $k$-submodularfunctions and establish a hierarchical relationship between them. Next, we showthat simple greedy algorithms offer approximation guarantees for differenttypes of size constraints. Last, we demonstrate experimentally that the greedyalgorithms are effective in sensor placement and influence maximizationproblems.