Is submodularity testable?
From MaRDI portal
Abstract: We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a vast range of algorithms, the existence of an oracle to a submodular function is assumed. But how does one check if this oracle indeed represents a submodular function? Consider a function f:{0,1}^n
ightarrow R. The distance to submodularity is the minimum fraction of values of that need to be modified to make f submodular. If this distance is more than epsilon > 0, then we say that f is epsilon-far from being submodular. The aim is to have an efficient procedure that, given input f that is epsilon-far from being submodular, certifies that f is not submodular. We analyze a very natural tester for this problem, and prove that it runs in subexponential time. This gives the first non-trivial tester for submodularity. On the other hand, we prove an interesting lower bound (that is, unfortunately, quite far from the upper bound) suggesting that this tester cannot be very efficient in terms of epsilon. This involves non-trivial examples of functions which are far from submodular and yet do not exhibit too many local violations. We also provide some constructions indicating the difficulty in designing a tester for submodularity. We construct a partial function defined on exponentially many points that cannot be extended to a submodular function, but any strict subset of these values can be extended to a submodular function.
Recommendations
Cites work
- scientific article; zbMATH DE number 1819631 (Why is no real title available?)
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- scientific article; zbMATH DE number 1175945 (Why is no real title available?)
- scientific article; zbMATH DE number 7051222 (Why is no real title available?)
- scientific article; zbMATH DE number 1857651 (Why is no real title available?)
- scientific article; zbMATH DE number 1418269 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- An analysis of approximations for maximizing submodular set functions—I
- Approximating the distance to monotonicity in high dimensions
- Learning submodular functions
- Monotonicity testing and shortest-path routing on the cube
- Monotonicity testing over general poset domains
- On Testing Convexity and Submodularity
- On the strength of comparisons in property testing
- Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
- Property testing and its connection to learning and approximation
- Robust Characterizations of Polynomials with Applications to Program Testing
- Submodular functions are noise stable
- Testing coverage functions
- Testing monotonicity
- The Complexity of Approximating the Entropy
Cited in
(19)- Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems
- Characterizing and recognizing generalized polymatroids
- scientific article; zbMATH DE number 7559054 (Why is no real title available?)
- Optimal unateness testers for real-valued functions: adaptivity helps
- Testing Lipschitz functions on hypergrid domains
- scientific article; zbMATH DE number 2019621 (Why is no real title available?)
- A non-extendibility certificate for submodularity and applications
- Approximate F_2-Sketching of Valuation Functions
- The Complexity of Partial Function Extension for Coverage Functions
- A note on the implications of approximate submodularity in discrete optimization
- On Testing Convexity and Submodularity
- Recognizing Coverage Functions
- scientific article; zbMATH DE number 7765404 (Why is no real title available?)
- Testing submodularity and other properties of valuation functions
- Testing convexity of figures under the uniform distribution
- Positivity and convexity in incomplete cooperative games
- On additive approximate submodularity
- Which Distribution Distances are Sublinearly Testable?
- Testing coverage functions
This page was built for publication: Is submodularity testable?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472463)
