Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

Multi-objective Maximization of Monotone Submodular Functions with Cardinality Constraint

Rajan Udwani

Room 210 #25

Keywords: [ Combinatorial Optimization ] [ Theory ] [ Optimization ] [ Submodular Optimization ] [ Non-Convex Optimization ] [ Algorithms ]


Abstract: We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as max|A|=kmini{1,,m}fi(A). While it is widely known that greedy methods work well for a single objective, the problem becomes much harder with multiple objectives. In fact, Krause et al.\ (2008) showed that when the number of objectives m grows as the cardinality k i.e., m=Ω(k), the problem is inapproximable (unless P=NP). On the other hand, when m is constant Chekuri et al.\ (2010) showed a randomized (11/e)ϵ approximation with runtime (number of queries to function oracle) nm/ϵ3. %In fact, the result of Chekuri et al.\ (2010) is for the far more general case of matroid constant. We focus on finding a fast and practical algorithm that has (asymptotic) approximation guarantees even when m is super constant. We first modify the algorithm of Chekuri et al.\ (2010) to achieve a (11/e) approximation for m=o(klog3k). This demonstrates a steep transition from constant factor approximability to inapproximability around m=Ω(k). Then using Multiplicative-Weight-Updates (MWU), we find a much faster ˜O(n/δ3) time asymptotic (11/e)2δ approximation. While the above results are all randomized, we also give a simple deterministic (11/e)ϵ approximation with runtime knm/ϵ4. Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.

Live content is unavailable. Log in and register to view live content