"Non UBC"@en .
"DSpace"@en .
"Udwani, Rajan"@en .
"2019-07-17T09:10:01Z"@en .
"2019-01-17T16:11"@en .
"We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as $\max_{|A|=k}\min_{i\in\{1,\dots,m\}}f_i(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=\Omega(k)$, the problem is inapproximable (unless $P=NP$). We focus on the case where the number of objectives is super-constant yet much smaller than the cardinality of the chosen set. We propose the first constant factor algorithms for this regime, including one with the best achievable asymptotic guarantee and also a more practical nearly linear time algorithm. Experiments on synthetic data show that a heuristic based on our more practical and fast algorithm outperforms existing heuristics."@en .
"https://circle.library.ubc.ca/rest/handle/2429/71026?expand=metadata"@en .
"42.0"@en .
"video/mp4"@en .
""@en .
"Author affiliation: Columbia University"@en .
"Banff (Alta.)"@en .
"10.14288/1.0379889"@en .
"eng"@en .
"Unreviewed"@en .
"Vancouver : University of British Columbia Library"@en .
"Banff International Research Station for Mathematical Innovation and Discovery"@en .
"Attribution-NonCommercial-NoDerivatives 4.0 International"@en .
"http://creativecommons.org/licenses/by-nc-nd/4.0/"@en .
"Postdoctoral"@en .
"BIRS Workshop Lecture Videos (Banff, Alta)"@en .
"Mathematics"@en .
"Operations research, mathematical programming"@en .
"Computer science"@en .
"Applied computer science"@en .
"Multi-objective Maximization of Monotone Submodular Functions with Cardinality Constraint"@en .
"Moving Image"@en .
"http://hdl.handle.net/2429/71026"@en .