On Testing Convexity and Submodularity

DOI10.1137/S0097539702414026MaRDI QIDQ4429680zbMATH OpenFDO

Authors Michal Parnas, Dana Ron, Ronitt Rubinfeld

Publication date 28 September 2003

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

Full work available at URL https://doi.org/10.1137/S0097539702414026

zbMATH Keywords

approximation algorithmsconvex functionsMonge matricesproperty testingrandomized algorithms

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2019621
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Testing submodularity and other properties of valuation functions
• Is submodularity testable?
• scientific article; zbMATH DE number 1418269

Cited in

(14)

• Subclasses of solvable problems from classes of combinatorial optimization problems
• On additive approximate submodularity
• scientific article; zbMATH DE number 2019621 (Why is no real title available?)
• scientific article; zbMATH DE number 2073529 (Why is no real title available?)
• Erasure-Resilient Property Testing
• Parameterized property testing of functions
• Testing submodularity and other properties of valuation functions
• Is submodularity testable?
• Testing local properties of arrays
• Optimal unateness testers for real-valued functions: adaptivity helps
• Testing convexity of figures under the uniform distribution
• scientific article; zbMATH DE number 7758320 (Why is no real title available?)
• scientific article; zbMATH DE number 7765404 (Why is no real title available?)
• Property testing lower bounds via communication complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429680)