Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	张宏扬，宁波大学
Inviter:
Title:	Submodular Functions: Extensions, Distributions, and Algorithms
Time & Venue:	2022.11.20 09:30-10:30 腾讯会议 ID： 266-621-988 会议密码：1120
Abstract:	Submodularity is a fundamental phenomenon in combinatorial optimization. Submodular functions occur in a variety of combinatorial settings such as coverage problems, cut problems, welfare maximization, and many more. Therefore, a lot of work has been concerned with maximizing or minimizing a submodular function, often subject to combinatorial constraints. Many of these algorithmic results exhibit a common structure. Namely, the function is extended to a continuous, usually non-linear, function on a convex domain. In this talk, we mainly investigate the Lovaz extension, the multilinear extension of submodular functions and a 2-approximation algorithm of the symmetric submodular minimization under the cardinality constraint.