The Algorithms For Optimizing Approximately Submodular Functions

Submodularity is an intuitive notion to characterize diminishing returns.As for set func-tion,it indicates that an element has more contribution onto a smaller set than onto a larger one.Submodular functions play important roles in many applications arising from the real life,since it exhibits sufficient structure such that a mathematically beautiful and practically useful theory can be developed smoothly.With the development of artificial intelligence and machine learn-ing,many research results on submodular optimization have attracted the attention of numerous scholars.Even though submodularity has been a ubiquitous concept emerged in many fields,there are still many non-submodular objective functions arising in real-life applications,such as any-time linear prediction,boosting information spread in social networks,interpretation of deep neural networks and high dimensional sparse regression in machine learning,and many others.A large number of studies show that these functions meet some submodularity even not strictly,which are called approximately submodular functions by many researchers later.Actually,approximately submodular functions exist as a very natural property in engineer-ing science,management science,computer science,economics and many other disciplines,resulting in a variety of submodular optimization problems.In this thesis,we mainly study the approximately submodular functions and their variants both in parameterized and structured forms.Based on the greedy technique mainly,and supplemented by local search and threshold methods,we design approximation algorithms and provide theoretical analysis.This thesis takes data volume as the research clue.Under the assumption of all information known,we investigate the problem of maximizing approximately submodular functions subject to knapsack and matroid constraints.Depending on the differences of matroid,we study both single matroid andk-matroid.By the greedy local search technique,we present approximation algorithms with constant approximation ratios.For the single matroid and knapsack constraints,we get (?)-approximation algorithm;for thek-matroid and knapsack con-straints,the approximation ratio is(?),whereis a parameter characterizing diminishing returns,which changes with differentk-.When the objective function becomes sub-modular,our results are consistent with those investigated in the literature under the same type of constraints.When faced with uncontrollable massive data,it is no longer practical to store and ana-lyze the whole data in the traditional way.Extracting effective information from massive data has become a necessary choice.Then we study the approximately submodular maximization problem with cardinality constraints,and design four streaming algorithms based on the tech-niques of greedy and threshold methods.According to the data information,we get a sin-gle pass min(?)-approximation algorithm with known optimal objective value and (?)approximation algorithm which scans the whole data two-pass.Based on the results,we provide two general single-pass streaming algorithms,whose approximation ratio is(?).For both of the general single-pass streaming algorithms,the memory is(?)and the update time is(?).Compared with the unique algorithm for solving approximately submodular maximization problem with cardinality constraints under streaming model,our algorithm has advantages in both the solution quality and time complexity.Similar to streaming model,online model is born to meet the needs of The Times.On-line model has more stringent requirements for decision making.The streaming model focuses on the memory to store data,while online model focuses on decision.In addition,except for describing approximately submodular functions in the form of parameters,structured one also attracts the research interest of many scholars.We study the problem of maximizing the differ-ence of two set functions under online model,and propose three online algorithms,which cover from special case to general one.No matter from the models or the results,our work is a further extension to the existing results of related problems.Maximizing the difference of two set functions can be reduced to the problem of minimiz-ing the ratio of two set functions equivalently.As for the model,we take advantage of the greedy ratio method to design approximation algorithm and perform corresponding analysis,which in-cludes more kinds of functions.This thesis is a complete introduction to the approximately submodule function,whether from the content or from the form.It is helpful for readers to have a comprehensive understanding of approximately submodular function and it is a fruitful work.