Capturing complementarity in set functions by going beyond submodularity/subadditivity

DOI10.4230/LIPICS.ITCS.2019.24MaRDI QIDQ5090397FDOQ5090397

Authors: Wei Chen, Hanrui Zhang, Shang-Hua Teng 

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1805.04436

Recommendations

• Welfare maximization and the supermodular degree
• Constrained monotone function maximization and the supermodular degree
• Communication complexity of combinatorial auctions with submodular valuations
• Inapproximability results for combinatorial auctions with submodular utility functions
• Supermodular mechanism design

zbMATH Keywords

submodularitysubadditivityset functionswelfare maximizationsimple auctionscardinality constrained maximizationmeasure of complementarity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Title not available (Why is that?)
• The Core of an N Person Game
• Title not available (Why is that?)
• Combinatorial auctions with decreasing marginal utilities
• An analysis of approximations for maximizing submodular set functions—I
• Composable and efficient mechanisms
• Algorithmic mechanism design (extended abstract)
• Optimal approximation for the submodular welfare problem in the value oracle model
• Inapproximability results for combinatorial auctions with submodular utility functions
• Network essence: PageRank completion and centrality-conforming Markov chains
• Building a good team: secretary problems and the supermodular degree

Cited In (2)

• Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
• Weakly Submodular Function Maximization Using Local Submodularity Ratio.

This page was built for publication: Capturing complementarity in set functions by going beyond submodularity/subadditivity

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