Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

Authors:
  • GGGagan Goel
    Gagan Goel
  • CKChinmay Karande
    Chinmay Karande
  • PTPushkar Tripathi
    Pushkar Tripathi
  • LWLei Wang
    Lei Wang

Abstract
Applications in complex systems such as the Internet have spawned recent interest in studying situations involving multiple agents with their individual cost or utility functions. In this paper, we introduce an algorithmic framework for studying combinatorial problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems (Vertex Cover, Shortest Path, Perfect Matching, and Spanning Tree) in this setting and establish tight upper and lower bounds for the approximability of these problems.