Continuing with the theme of combinatorial optimization and approximate algorithms, Stephen presented a simple approximate greedy algorithm for optimizing monotone, submodular set functions.
An example problem is the NP-hard set cover problem or optimal sensor placement.
For more on submodularity, see these lecture notes or my personal notes.
Previous: Approximate algorithms for metric traveling salesman
Brian presented on combinatorial optimization, specifically, some approximation algorithms for the (metric) traveling salesman problem.
continue reading ❯