Approximate modularity revisited

DOI10.1137/18M1173873zbMATH Open1437.68072OpenAlexW3001914552WikidataQ126318186 ScholiaQ126318186MaRDI QIDQ5211809FDOQ5211809

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

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

zbMATH Keywords

learninglinear functionsset functions

Mathematics Subject Classification ID

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

Cites Work

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

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)