Algorithmic and structural aspects of submodularity in games and optimization

• Grant number: 24/16092-6
• Support Opportunities: Scholarships abroad - Research
• Start date: September 29, 2025
• End date: September 28, 2026
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Carla Negri Lintzmayer
• Grantee: Carla Negri Lintzmayer
• Host Investigator: Martin Loebl
• Host Institution: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brazil
• Institution abroad: Charles University in Prague (CU), Czech Republic

Abstract

This is a research project to be executed at Charles University, under the supervision of Prof. Martin Loebl. Our main goal is to study some problems that involve the notion of submodularity, both from an algorithmic and a structural point of view. Submodularity appears in many valuation functions and, informally, it models contexts where adding more of something gives you less extra benefit. They appear in combinatorial optimization, e.g. in rank functions of matroids, in algorithmic game theory, e.g. to model valuation functions of agents with diminishing returns, or in machine learning, e.g. as objective functions. The responsible researcher visited the host researcher atthe Faculty of Mathematics and Physics of Charles University for some days in April 2024, when they started collaborative work on some problems, with this research period abroad in mind. This project describes these problems and some related ones.