Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

DOI10.1109/FOCS.2009.81MaRDI QIDQ5171231zbMATH OpenOpenAlexFDO

Authors Gagan Goel, C. Karande, Pushkar Tripathi, Lei Wang

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2009.81

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited in

(19)

• Polyhedral results for a class of cardinality constrained submodular minimization problems
• Complexity and approximations for submodular minimization problems on two variables per inequality constraints
• Robust budget allocation via continuous submodular functions
• Approximation algorithms for the submodular edge cover problem with submodular penalties
• New approximations and hardness results for submodular partitioning problems
• An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
• The multi-budget maximum weighted coverage problem
• Submodular function minimization under a submodular set covering constraint
• Submodular Cost Allocation Problem and Applications
• Submodular functions: learnability, structure, and optimization
• Multi-agent submodular optimization
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• Contractors' minimum spanning tree
• Approximability of sparse integer programs
• Minimization problems with non-submodular cover constraint
• Online dynamic submodular optimization
• Shortest cycles with monotone submodular costs
• A note on submodular function minimization with covering type linear constraints
• Cuts in graphs with matroid constraints

This page was built for publication: Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

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