On Testing Convexity and Submodularity

DOI10.1137/S0097539702414026MaRDI QIDQ4429680zbMATHFDO

Authors Michal Parnas, Dana Ron, Ronitt Rubinfeld

Publication date 28 September 2003

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

zbMATH Keywords

randomized algorithmsapproximation algorithmsconvex functionsproperty testingMonge matrices

Mathematics Subject Classification ID

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

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)

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

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)