Greedy Maximization of Functions with Bounded Curvature under Partition Matroid Constraints

• DOI: 10.1609/aaai.v33i01.33012272
• Publication Date: 2019-09-10T07:41:27Z
• Authors: Tobias Friedrich; Andreas Göbel; Frank Neumann; Francesco Quinzan; Ralf Rothenberger
• Keywords: Submodular set function; Subadditivity; Entropy maximization; Weighted matroid; Oriented matroid; Maximization

We investigate the performance of a deterministic GREEDY algorithm for problem maximizing functions under partition matroid constraint. consider non-monotone submodular and monotone subadditive functions. Even though constrained maximization problems have been extensively studied, little is known about greedy or functions.
 give approximation guarantees on these problems, in terms curvature. find that this simple heuristic yields strong guarantee broad class discuss applicability our results to three real-world problems: Maximizing determinant function positive semidefinite matrix, related such as maximum entropy sampling problem, cut directed graphs, combinatorial auction games.
 conclude well-suited approach problems. Overall, we present evidence support idea that, when dealing with bounded curvature, one needs not search (approximate) monotonicity get good approximate solutions.