אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Submodular functions arise in various fields, including combinatorics, graph theory, information theory, and economics. This thesis addresses two key problems in submodular maximization and presents new algorithmic contributions. The first focuses on the Online Submodular Welfare problem, where bidders with submodular utility functions compete for items arriving sequentially. We propose a randomized algorithm that achieves a tight competitive ratio of 1/4 under adversarial arrivals and improve this to approximately 0.27493 under random arrivals. The second result introduces a Greedy Poisson Process for submodular maximization under matroid constraints, achieving a tight (1 − 1/e − ϵ)-approximation without requiring discretization or rounding. Our algorithm introduces a new framework for submodular maximization under matroid constraints, combining the strengths of both continuous and discrete approaches.