2017/11/17 by Rajan Udwani, Udwani, Rajan · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Infrastructure Maintenance and Monitoring
paper · pdf · doi:10.48550/arxiv.1711.06428
We consider the problem of multi-objective maximization of monotone\nsubmodular functions subject to cardinality constraint, often formulated as\n\max|A|=k\min_i\∈ 1,\…,m fi(A). While it is widely known that\ngreedy methods work well for a single objective, the problem becomes much\nharder with multiple objectives. In fact, Krause et al. (2008) showed that\nwhen the number of objectives m grows as the cardinality k i.e.,\nm=\Ω(k), the problem is inapproximable (unless P=NP). On the other\nhand, when m is constant Chekuri et al. (2010) showed a randomized\n(1-1/e)-\ε approximation with runtime (number of queries to function\noracle) nm/\ε3. %In fact, the result of Chekuri et al. (2010) is\nfor the far more general case of matroid constant.\n We focus on finding a fast and practical algorithm that has (asymptotic)\napproximation guarantees even when m is super constant. We first modify the\nalgorithm of Chekuri et al. (2010) to achieve a (1-1/e) approximation for\nm=o(\(k)/(\log3 k)). This demonstrates a steep transition from constant\nfactor approximability to inapproximability around m=\Ω(k). Then using\nMultiplicative-Weight-Updates (MWU), we find a much faster\n\O(n/\δ3) time asymptotic (1-1/e)2-\δ approximation. While\nthe above results are all randomized, we also give a simple deterministic\n(1-1/e)-\ε approximation with runtime knm/\ε4. Finally, we\nrun synthetic experiments using Kronecker graphs and find that our MWU inspired\nheuristic outperforms existing heuristics.\n