Guided Combinatorial Algorithms for Submodular Maximization

ABSTRACT

Submodularity is natural diminishing returns property that a set function may satisfy and is analogous to the convexity property of a continuous function. Submodular functions arise in many applications, such as viral marketing, data summarization, and sensor network coverage, for example. The best-known approximation factor for constrained submodular optimization is 0.401 and relies on algorithms using continuous extensions of the submodular function that are impractical to implement. However, the best-known ratio for a combinatorial algorithm is 1/e ≈ 0.367. In this talk, I will describe combinatorial algorithms that narrow the gap between the continuous and combinatorial ratios and are practical as shown in an empirical evaluation.

BIOGRAPHY

Alan Kuhnle is an Assistant Professor of Computer Science & Engineering at Texas A&M University. His work focuses on the design and analysis of scalable algorithms for combinatorial optimization problems arising in data science applications, such as vehicle routing and marketing on social networks.