Is submodularity testable?

DOI10.1007/s00453-012-9719-2zbMath1307.68097arXiv1008.0831OpenAlexW1801423597MaRDI QIDQ472463

Jan Vondrák, C. Seshadhri

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

property testingsublinear algorithmssubmodular functions

Mathematics Subject Classification ID

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

Related Items

Testing Lipschitz functions on hypergrid domains, Recognizing Coverage Functions, On additive approximate submodularity, Characterizing and recognizing generalized polymatroids, A note on the implications of approximate submodularity in discrete optimization, Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems, Unnamed Item, Testing convexity of figures under the uniform distribution, Approximate F_2-Sketching of Valuation Functions, The Complexity of Partial Function Extension for Coverage Functions, A non-extendibility certificate for submodularity and applications, Unnamed Item, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monotonicity testing and shortest-path routing on the cube
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• On the strength of comparisons in property testing
• Testing Coverage Functions
• Approximating the distance to monotonicity in high dimensions
• Property testing and its connection to learning and approximation
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Monotonicity testing over general poset domains
• An analysis of approximations for maximizing submodular set functions—I
• On Testing Convexity and Submodularity
• Robust Characterizations of Polynomials with Applications to Program Testing
• Learning submodular functions
• Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
• The Complexity of Approximating the Entropy
• Testing monotonicity