Math & Computer Science

Barbara Anthony

Assistant Professor of Computer Science

Areas of expertise

Approximation Algorithms, Network Design Problems



Education

PhD, Carnegie Mellon University 2008
BA, Rice University 2001

Courses: Fall 2009

Computer Science I
Discrete Mathematics
Theory of Computation

Publications

Selected Publications:

"Approximation Algorithms for Network Design with Uncertainty", PhD Thesis, 2008.

"A Plant Location Guide for the Unsure" with V. Goyal, A. Gupta, and V. Nagarajan, Proceedings
of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.

Consider a min-max version of the k-median problem, where we are given m possible demand sets, and the goal is to locate k medians to minimize the cost they incur on the worst of these demand sets. We give a logarithmic approximation for this problem. In fact, we give some general conditions such that if a location problem satisfies these conditions, there is a reverse-greedy algorithm for the min-max version of the problem. Using this, we give algorithms for fault-tolerant and capacitated versions of k-median, as well as the k-tree problem. Finally, we show that stochastic versions of k-center are as hard as dense-k-subgraph.

"Infrastructure Leasing Problems" with A. Gupta, Proceedings of the Twelfth Conference on Integer Programming and Combinatorial Optimization (IPCO), 2007.

Consider the following Steiner Tree leasing problem: We are given a graph with a prespecified root, and a sequence of terminal sets such that the j'th set wants to connect to the root on day j. However, instead of obtaining edges for a single day at a time, or for infinitely long, we are allowed to lease edges for various periods: say {a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy?

We give a general approach to solving such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization.


Groups & Affiliations

Association of Computing Machinery (ACM)

SIGACT: Special Interest Group on Algorithms and Computation Theory

SIGCSE: Special Interest Group on Computer Science Education

Society for Industrial and Applied Mathematics (SIAM)

Upsilon Pi Epsilon (UPE), Computer Science Honorary Society

Registry of Interpreters for the Deaf (RID)