On Testing Convexity and Submodularity

DOI10.1137/S0097539702414026zbMath1026.68166MaRDI QIDQ4429680

Michal Parnas, Dana Ron, Ronitt Rubinfeld

Publication date: 28 September 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

convex functionsapproximation algorithmsrandomized algorithmsproperty testingMonge matrices

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Functional inequalities, including subadditivity, convexity, etc. (39B62) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (11)

Parameterized property testing of functions ⋮ On additive approximate submodularity ⋮ Erasure-Resilient Property Testing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Testing convexity of figures under the uniform distribution ⋮ Is submodularity testable? ⋮ Property testing lower bounds via communication complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Subclasses of solvable problems from classes of combinatorial optimization problems

This page was built for publication: On Testing Convexity and Submodularity