Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

DOI10.1109/FOCS.2009.81zbMath1292.05245OpenAlexW2134944545MaRDI QIDQ5171231

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

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

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

Related Items (16)

Unnamed Item ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties ⋮ The multi-budget maximum weighted coverage problem ⋮ Approximability of sparse integer programs ⋮ Unnamed Item ⋮ Submodular Function Minimization under a Submodular Set Covering Constraint ⋮ Submodular Cost Allocation Problem and Applications ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ Polyhedral results for a class of cardinality constrained submodular minimization problems ⋮ Robust budget allocation via continuous submodular functions ⋮ A note on submodular function minimization with covering type linear constraints ⋮ Approximation algorithms for the submodular edge cover problem with submodular penalties ⋮ Complexity and approximations for submodular minimization problems on two variables per inequality constraints ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ New approximations and hardness results for submodular partitioning problems

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