On Testing Convexity and Submodularity

DOI10.1137/S0097539702414026zbMATH Open1026.68166MaRDI QIDQ4429680FDOQ4429680

Authors: Michal Parnas, Dana Ron, Ronitt Rubinfeld 

Publication date: 28 September 2003

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

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

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)

Cited In (14)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Erasure-Resilient Property Testing
• Optimal unateness testers for real-valued functions: adaptivity helps
• Is submodularity testable?
• Title not available (Why is that?)
• Title not available (Why is that?)
• Property testing lower bounds via communication complexity
• Testing submodularity and other properties of valuation functions
• Testing convexity of figures under the uniform distribution
• On additive approximate submodularity
• Parameterized property testing of functions
• Title not available (Why is that?)
• Subclasses of solvable problems from classes of combinatorial optimization problems

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)