Approximate Modularity Revisited

DOI10.1137/18M1173873zbMath1437.68072OpenAlexW3001914552WikidataQ126318186 ScholiaQ126318186MaRDI QIDQ5211809

Inbal Talgam-Cohen, Michal Feldman, 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) Real- or complex-valued set functions (28A10) Combinatorial optimization (90C27)

Related Items (1)

Approximate modularity: Kalton’s constant is not smaller than 3

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyers-Ulam-Rassias stability of functional equations in nonlinear analysis
• Self-testing/correcting with applications to numerical problems
• Polynomial approximation on convex subsets of \(\mathbb{R}^n\)
• Gross substitutability: an algorithmic survey
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• On concentrators and related approximation constants
• Combinatorial auctions with decreasing marginal utilities
• Welfare maximization and the supermodular degree
• Uniformly Exhaustive Submeasures and Nearly Additive Set Functions
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Approximately additive set functions
• Superconcentrators
• On Orthogonal Matrices
• The limitations of optimization from samples
• Approximate modularity revisited
• When Are Welfare Guarantees Robust
• On Maximizing Welfare When Utility Functions Are Subadditive
• Learning submodular functions

This page was built for publication: Approximate Modularity Revisited