Building Steiner Trees with Incomplete Global Knowledge. - David R. Karger; Maria Minkoff (FOCS, 2000)

The prize collecting Steiner tree problem: theory and practice. - David S. Johnson 001; Maria Minkoff; Steven Phillips (SODA, 2000)

Approximation algorithms for combinatorial optimization under uncertainty. - Maria Minkoff (2003)

On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. - Nicole Immorlica; David R. Karger; Maria Minkoff; Vahab S. Mirrokni (SODA, 2004)

Approximation Algorithms for Orienteering and Discounted-Reward TSP. - Avrim Blum; Shuchi Chawla 001; David R. Karger; Terran Lane; Adam Meyerson; Maria Minkoff (SIAM J. Comput., 2007)