Is Submodularity Testable?
Open Access
- 21 November 2012
- journal article
- Published by Springer Nature in Algorithmica
- Vol. 69 (1) , 1-25
Abstract
No abstract availableKeywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Monotonicity testing and shortest-path routing on the cubeCombinatorica, 2012
- Approximating the distance to monotonicity in high dimensionsACM Transactions on Algorithms, 2010
- THE ART OF UNINFORMED DECISIONS: A PRIMER TO PROPERTY TESTING2004
- On the strength of comparisons in property testingInformation and Computation, 2004
- A combinatorial strongly polynomial algorithm for minimizing submodular functionsJournal of the ACM, 2001
- A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial TimeJournal of Combinatorial Theory, Series B, 2000
- Testing MonotonicityCombinatorica, 2000
- Property testing and its connection to learning and approximationJournal of the ACM, 1998
- Submodular functions and convexity1983
- An analysis of approximations for maximizing submodular set functions—II1978