As an example, consider the network design problem of min-cost spanning tree. In the classical setting, we are given costs on the individual edges of the underlying graph G, and the cost of a subset of edges is just the additive cost. However, in practice, cost functions are not always additive. Often they follow the economies of scale or the decreasing marginal cost property. Submodular functions mathematically characterize the class of all such functions. This work aims at designing algorithms for combinatorial optimization problems under these more complex cost functions. Another generalization that we consider is when there are multiple agents with their own cost functions.
In this talk, I will review recent results in submodular optimization, and present our new results on the approximability of various different problems (Spanning Tree, Shortest Path, Vertex Cover, and Perfect Matching) in the above general framework.
Based on joint work with Chinmay Karande, Pushkar Tripathi, and Lei Wang.