2019/06/14 by Rishabh Iyer, Iyer, Rishabh
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.1906.06393
Robust optimization is becoming increasingly important in machine learning\napplications. In this paper, we study a unified framework of robust submodular\noptimization. We study this problem both from a minimization and maximization\nperspective (previous work has only focused on variants of robust submodular\nmaximization). We do this under a broad range of combinatorial constraints\nincluding cardinality, knapsack, matroid as well as graph-based constraints\nsuch as cuts, paths, matchings and trees. Furthermore, we also study robust\nsubmodular minimization and maximization under multiple submodular upper and\nlower bound constraints. We show that all these problems are motivated by\nimportant machine learning applications including robust data subset selection,\nrobust co-operative cuts and robust co-operative matchings. In each case, we\nprovide scalable approximation algorithms and also study hardness bounds.\nFinally, we empirically demonstrate the utility of our algorithms on synthetic\ndata, and real-world applications of robust cooperative matchings for image\ncorrespondence, robust data subset selection for speech recognition, and image\ncollection summarization with multiple queries.\n