Approximate modularity revisited

DOI10.1137/18M1173873MaRDI QIDQ5211809zbMATH OpenOpenAlexWikidataFDO

Authors Michal Feldman, Inbal Talgam-Cohen, Uriel Feige

Publication date 28 January 2020

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

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

zbMATH Keywords

learninglinear functionsset functions

Mathematics Subject Classification ID

Computational learning theory (68Q32) Combinatorial optimization (90C27) Real- or complex-valued set functions (28A10)

Recommendations

• Approximate modularity revisited
• Optimal bounds on approximation of submodular and XOS functions by juntas
• Learning submodular functions
• scientific article; zbMATH DE number 7051222
• Submodular functions are noise stable

Cites work

• scientific article; zbMATH DE number 3613652 (Why is no real title available?)
• scientific article; zbMATH DE number 7051222 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Approximate modularity revisited
• Approximately additive set functions
• Combinatorial auctions with decreasing marginal utilities
• Gross substitutability: an algorithmic survey
• Hyers-Ulam-Rassias stability of functional equations in nonlinear analysis
• Learning submodular functions
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On Orthogonal Matrices
• On concentrators and related approximation constants
• On maximizing welfare when utility functions are subadditive
• Polynomial approximation on convex subsets of \(\mathbb{R}^n\)
• Self-testing/correcting with applications to numerical problems
• Superconcentrators
• The limitations of optimization from samples
• Uniformly Exhaustive Submeasures and Nearly Additive Set Functions
• Welfare maximization and the supermodular degree
• When are welfare guarantees robust?

Cited in

(7)

• Modularity of confluence: A simplified proof
• Optimal approximations made easy
• Approximate modularity revisited
• Generalized modularity matrices
• Using atomic bounds to get sub-modular approximations
• Approximate modularity: Kalton's constant is not smaller than 3
• Modularity in planted partition model

This page was built for publication: Approximate modularity revisited

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