Is submodularity testable?

DOI10.1007/S00453-012-9719-2zbMATH Open1307.68097arXiv1008.0831OpenAlexW1801423597MaRDI QIDQ472463FDOQ472463

Authors: C. Seshadhri, Jan Vondrák 

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

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 $f$ 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.

Full work available at URL: https://arxiv.org/abs/1008.0831

Recommendations

• Testing submodularity and other properties of valuation functions
• On Testing Convexity and Submodularity
• Maximizing Non-monotone Submodular Functions
• Testing coverage functions
• scientific article; zbMATH DE number 2019621

zbMATH Keywords

property testingsublinear algorithmssubmodular functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Property testing and its connection to learning and approximation
• Title not available (Why is that?)
• Monotonicity testing over general poset domains
• Robust Characterizations of Polynomials with Applications to Program Testing
• Title not available (Why is that?)
• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
• Title not available (Why is that?)
• Testing monotonicity
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• An analysis of approximations for maximizing submodular set functions—I
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Approximating the Entropy
• On the strength of comparisons in property testing
• Monotonicity testing and shortest-path routing on the cube
• Testing coverage functions
• Approximating the distance to monotonicity in high dimensions
• Title not available (Why is that?)
• On Testing Convexity and Submodularity
• Title not available (Why is that?)
• Learning submodular functions
• Submodular functions are noise stable

Cited In (19)

• Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems
• Title not available (Why is that?)
• Characterizing and recognizing generalized polymatroids
• Optimal unateness testers for real-valued functions: adaptivity helps
• Testing Lipschitz functions on hypergrid domains
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Testing submodularity and other properties of valuation functions
• Positivity and convexity in incomplete cooperative games
• Testing convexity of figures under the uniform distribution
• 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)