Welfare maximization and the supermodular degree

DOI10.1145/2422436.2422466zbMath1362.91022OpenAlexW2170531897MaRDI QIDQ2986874

Rani Izsak, Uriel Feige

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2422436.2422466

zbMATH Keywords

approximation algorithmscombinatorial auctionssubmodular functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25)

Related Items (15)

Influence maximization problem: properties and algorithms ⋮ Multi-attribute based influence maximization in social networks: algorithms and analysis ⋮ Generalized self-profit maximization in attribute networks ⋮ Competition-based generalized self-profit maximization in dual-attribute network ⋮ Competition-based generalized self-profit maximization in dual-attribute networks ⋮ Weakly Submodular Function Maximization Using Local Submodularity Ratio. ⋮ Parametric monotone function maximization with matroid constraints ⋮ Viral marketing of online game by DS decomposition in social networks ⋮ Sequence submodular maximization meets streaming ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Approximate Modularity Revisited ⋮ Set function optimization ⋮ A Simple and Approximately Optimal Mechanism for a Buyer with Complements ⋮ Generalized self-profit maximization and complementary-profit maximization in attribute networks

Cites Work

• Teachability in computational learning
• Measuring teachability using variants of the teaching dimension
• Teaching a smarter learner.
• Occam's razor
• Pseudorandom generators for space-bounded computation
• On the power of inductive inference from good examples
• A model of interactive teaching
• Learning from different teachers
• On the limits of efficient teachability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• Recent Developments in Algorithmic Teaching
• A theory of the learnable
• Teaching Randomized Learners
• Algorithmic Learning Theory
• A theory of goal-oriented communication
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Welfare maximization and the supermodular degree