Greedy Maximization of Functions with Bounded Curvature under Partition Matroid Constraints
Greedy Maximization of Functions with Bounded Curvature under Partition Matroid Constraints
We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone submodular functions and monotone subadditive functions. Even though constrained maximization problems of monotone submodular functions have been extensively studied, little is known about greedy maximization of non-monotone …