Submodular Order Maximization subject to a p-matchoid matroid

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Date
2022-10-17
Department
Major/Subject
Data Science
Mcode
SCI3115
Degree programme
Master's Programme in ICT Innovation
Language
en
Pages
25+9
Series
Abstract
Recently, Udwani defined a new class of set functions under monotonicity and subadditivity, called submodular order functions, which is a subfamily of submodular functions. Informally, the submodular order function admits a very limited form of submodularity which is defined over a specific permutation of the ground set. His work pointed out the intriguing connection between streaming submodular maximization and submodular order maximization. Inspired by a 0.25-approximation streaming algorithm for maximizing a monotone submodular function subject to a matroid constraint, Udwani gave a 0.25-approximation algorithm for submodular order functions maximization subject to a matroid constraint. Based on the above results, we would like to explore further in which cases it is feasible to generalize from streaming submodular maximization algorithms to submodular order maximization algorithms. As a more general constraint than matroid, p-matchoid is a collection of p matroids with each matroid defined on some subsets of the ground set. Related work gave a 1/4p-approximation streaming algorithm for monotone submodular functions maximization under a p-matchoid constraint. Inspired by the above algorithms and the intriguing connection, we used some techniques to try to generalize several streaming algorithms for submodular functions to the offline algorithms for submodular order functions, including interleaved partitions and incremental values. Assuming that the objective function f is subadditive and non-negative, we gave a 1/4p-approximation algorithm for monotone submodular order maximization to a p-matchoid constraint. In addition, we summarize the failures of other cases
Description
Supervisor
Austrin, Per
Thesis advisor
Gionis, Aristides
Keywords
theoretical computer science, approximation algorithms, matchoid, combinatorial optimization, submodular order maximization, submodular maximization
Other note
Citation