Submodular Functions: Learnability, Structure, and Optimization
From MaRDI portal
Publication:4564777
DOI10.1137/120888909zbMath1395.68228arXiv1008.2159OpenAlexW2964097349MaRDI QIDQ4564777
Maria-Florina Balcan, Nicholas J. A. Harvey
Publication date: 12 June 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1008.2159
optimizationmatroidsdistributional learningalgorithmic game theorysubmodular functionsPAC modelGross substitutes
Learning and adaptive systems in artificial intelligence (68T05) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Rationality and learning in game theory (91A26)
Related Items
Tractability of explaining classifier decisions, Graph cuts with interacting edge weights: examples, approximations, and algorithms, Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- Learning intersections and thresholds of halfspaces
- On concentration of self-bounding functions
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Walrasian equilibrium with gross substitutes
- Geometric algorithms and combinatorial optimization.
- Horn functions and submodular Boolean functions
- Learnability and rationality of choice.
- An analysis of the greedy algorithm for the submodular set covering problem
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- On learning monotone DNF under product distributions
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- Concentration of measure and isoperimetric inequalities in product spaces
- Combinatorial auctions with decreasing marginal utilities
- Submodular functions and optimization.
- Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
- Privately Releasing Conjunctions and the Statistical Query Barrier
- Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- Maximizing Non-monotone Submodular Functions
- Expander codes
- Constant depth circuits, Fourier transform, and learnability
- Are Bitvectors Optimal?
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- Optimal Bundle Pricing
- Expander graphs and their applications
- Agnostically Learning Halfspaces
- Hardness of Learning Halfspaces with Noise
- Oblivious routing in directed graphs with random demands
- A Stab at Approximating Minimum Subadditive Join
- Optimal Value of Information in Graphical Models
- A theory of the learnable
- On the structure of all minimum cuts in a network and applications
- Complexity of Matroid Property Algorithms
- Job Matching, Coalition Formation, and Gross Substitutes
- An analysis of approximations for maximizing submodular set functions—I
- Cryptographic limitations on learning Boolean formulae and finite automata
- Discrete Convex Analysis
- Neural Network Learning
- Learning and Smoothed Analysis
- Submodular Function Minimization under Covering Constraints
- Symmetry and Approximability of Submodular Maximization Problems
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Algorithmic Game Theory
- Probability and Computing
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Communication Complexity of Combinatorial Auctions with Submodular Valuations
- Learning Pseudo-Boolean k-DNF and Submodular Functions
- Truthful randomized mechanisms for combinatorial auctions
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
- Graph colouring and the probabilistic method
- Improved bounds on the sample complexity of learning
