On Testing Convexity and Submodularity
Michal Parnas, Dana Ron, Ronitt Rubinfeld · SIAM Journal on Computing · 2003
Convex and submodular functions play an important role in many applications, and in particular in combinatorial optimization. Here we study two special cases: convexity in one dimension and submodularity in two dimensions. The latter type of functions are equivalent to the well-known Monge matrices. A matrix $V = \{v_{i,j}\}_{i,j=0}^{i=n_1,j=n_2}$ is called a Monge matrix if for every $0 \leq i < i' \leq n_1$ and $0 \leq j < j' \leq n_2$ we have $v_{i,j}+v_{i',j'} \le v_{i,j'}+v_{i',j}$. If inequality holds in the opposite direction, then V is an inverse Monge matrix (supermodular function). Many problems, such as the traveling salesperson problem and various transportation problems, can be solved more efficiently if the input is a Monge matrix. In this work we present testing algorithms for the above properties. A testing algorithm for a predetermined property $\cal P$ is given query access to an unknown function f and a distance parameter $\epsilon$. The algorithm should accept f with high probability if it has the property $\cal P$ and reject it with high probability if more than an $\epsilon$-fraction of the function values should be modified so that f obtains the property. Our algorithm for testing whether a 1-dimensional function $f:[n] \rightarrow \mathbb{R}$ is convex (concave) has query complexity and running time of $O\left((\log n) /\epsilon\right)$. Our algorithm for testing whether an n 1 × n 2 matrix V is a Monge (inverse Monge) matrix has query complexity and running time of $O\left((\log n_1\cdot\log n_2) /\epsilon\right)$.