Concept
Fonction sous-modulaire
Publications associées (32)
Approximation Algorithms for Allocation and Network Design
In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...
EPFL2023Streaming and Matching Problems with Submodular Functions
Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...
EPFL2022Online Contention Resolution Schemes With Applications To Bayesian Selection Problems
Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen
We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...
2021Actuator Placement under Structural Controllability using Forward and Reverse Greedy Algorithms
Maryam Kamgarpour, Tyler Summers, Baiwei Guo, Orcun Karaca
Actuator placement is an active field of research which has received significant attention for its applications in complex dynamical networks. In this paper, we study the problem of finding a set of actuator placements minimizing the metric that measures t ...
2020Performance guarantees for greedy maximization of non-submodular controllability metrics
Maryam Kamgarpour, Tyler Summers
A key problem in emerging complex cyber-physical networks is the design of information and control topologies, including sensor and actuator selection and communication network design. These problems can be posed as combinatorial set function optimization ...
IEEE2019