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)

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

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)