Algorithms and Optimization

I also like to work on basic algorithms and optimization problems from time to time, and have recently worked on several interesting problems including improving the state-of-the-art algorithms for finding the minimum path cover of a DAG (see picture below), decomposing a flow network into a minimum number of path flows, and a job scheduling problem to minimize peak demand (relevant to smart power grids).

Select Publications

• Manuel Cáceres, Massimo Cairo, Andreas Grigorjew, Shahbaz Khan, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu, and Lucia Williams. 2024. Width Helps and Hinders Splitting Flows. ACM Transactions on Algorithms 20, 2, Article 13 (April 2024). doi.org/110.1145/3641820

• Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu. Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 359-376. doi.org/10.1137/1.9781611977073.18

• Elliott Pryor, Brendan Mumey, and Sean Yaw. 2020. Scheduling Jobs with Precedence Constraints to Minimize Peak Demand. Proceedings of Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020. 140–150. doi.org/10.1007/978-3-030-64843-5_10