Southwestern University: Profile

Areas of expertise

Approximation Algorithms, Network Design Problems

Selected areas in Operations Research, Graph Theory, Computational Geometry

Currently exploring Algorithmic Game Theory

Dr. Anthony teaches a variety of computer science courses, from the lower-level language courses through upper-level theory courses. She also teaches an FYS exploring the Internet and a variety of web applications. She also enjoys independent studies with students, whether it's a first-year exploring a new topic or a senior doing new research as part of an honors project. She is currently the faculty advisor for UPE, the CS Honor Society, and is happy to help organize a number of CS-themed events throughout the year.

Education

PhD, Carnegie Mellon University 2008
BA, Rice University 2001

Teaching Philosophy

Computer Science is relevant for everyone these days, and has great interdisciplinary potential, especially at a liberal arts institution. As such, I believe lower-level courses should be accessible to any SU student, and students should be exposed to both the breadth and depth of the field.

Previous Courses

Computer Science I (in Java); CS II: Data Structures; Discrete Mathematics; Algorithms in C++: Theory of Computation; Operations Research; CS Colloqium; First-Year Seminar; Various Independent Studies

Publications

"Online Bottleneck Matching," with Christine Chung, Proceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA'12), LNCS 7402, pp. 257-268, August 2012.

We consider the online bottleneck matching problem, where k server-vertices lie in a metric space and k request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. The goal is to minimize the maximum distance between any request and its server. Because no algorithm can have a competitive ratio better than O(k) for this problem, we use resource augmentation analysis to examine the performance of three algorithms: the naive Greedy algorithm, Permutation, and Balance. We show that while the competitive ratio of Greedy improves from exponential (when each server-vertex has one server) to linear (when each server-vertex has two servers), the competitive ratio of Permutation remains linear. The competitive ratio of Balance is also linear with an extra server at each server-vertex, even though it has been shown that an extra server makes it constant-competitive for the min-weight matching problem.

"Operations research: Broadening computer science in a liberal arts college," Proceedings of the 43rd ACM Technical Symposium on Computer Science Education (SIGCSE '12), pp. 463-468, February 2012.

Operations research, while not traditionally taught at many small or liberal arts colleges, can be a significant asset to the offerings of a computer science department. Often seen as a discipline at the intersection of mathematics, computer science, business, and engineering, it has great interdisciplinary potential and practical appeal, allowing for recruitment of students who may not consider taking a CS0 or CS1 course. A special topics course in operations research was offered by the computer science department at Southwestern University as an upper-level elective, and it was also cross-listed as a business and mathematics elective. Not only did the course benefit computer science majors who appreciated the applications and different perspectives, but it provided a means for the department to serve a wider population, increased interdisciplinary education, and resulted in a filled-to-capacity upper-level course in computer science for the first time in recent memory. This course is now being considered as a permanent elective that will interest computer science majors and minors as well as draw in students from disciplines across campus. For departments with limited faculty resources for teaching non-major courses, offering an operations research course provides an alternative that simultaneously serves the department and the campus as a whole.

"Some Families of Fixed Points for the Eccentric Digraph Operator," with Richard Denman and Alison Marr, Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 78, pp. 245-260, August 2011.

We investigate the existence of fixed point families for the eccentric digraph (ED) operator, which was introduced in [Buckley]. In [Gimbert, Miller, Ruskey and Ryan], the notion of the period $\rho(G)$ of a digraph G (under the ED operator) was defined, and it was observed, but not proved, that for any odd positive integer m, $C_m \times C_m$ is periodic, and that $\rho(ED(C_m \times C_m)) = 2\rho(ED(C_m))$. Also in [Gimbert, Miller, Ruskey and Ryan] the following question was posed: which digraphs are fixed points under the digraph operator? We provide a proof for the observations about $C_m \times C_m$, and in the process show that these products comprise a family of fixed points under ED. We then provide a number of other interesting examples of fixed point families.

"Implementing Ruppert's Algorithm for Generic Curves in 2D," with Matthew Flatau, 19th International Meshing Roundtable (Conference) Research Notes, October 2010.

While quality implementations exist for meshing straight-line inputs, fewer are available for handling curved inputs, even in 2D. Many are based on the well-known Ruppert's algorithm which has led to a large body of research in meshing. In this work, we provide a software package that handles a variety of smooth inputs in 2D, based on a minimal modification of Ruppert's algorithm. Existing software for curved inputs lacks the elegance of Ruppert's original algorithm (and subsequent improvements) or is application-specific. In contrast, we seek to keep the core of our work as similar as possible to Ruppert's algorithm to allow our software to benefit from related research and to be easily updated for additional input curve types. In particular, the differences in our implementation versus the original are limited to two pre-processing steps in the spirit of Pav and Walkington and a generalized midpoint calculation.

Until the IMR webpage is updated, feel free to email me for a copy. The code is freely available under the MIT License at code.google.com/p/reuleaux/

"A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems" with Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan, Mathematics of Operations Research, Vol. 35, No. 1, pp. 79-101, February 2010.

This paper studies an extension of the k-median problem under uncertain demand. We are given an n-vertex metric space (V, d) and m client sets $\{S_i \subseteq V\}_{i = 1}^m$. The goal is to open a set of k facilities F such that the worst-case connection cost over all the client sets is minimized, i.e., \min_{F \subseteq V, |F| = k}\max_{i \in [m]}\left \{\sum_{j \in S_i} d(j, F)\right\}, where for any $F \subseteq V, d(j, F) = \min_{f \in F} d(j, f)$. This is a "min-max" or "robust" version of the k-median problem. Note that in contrast to the recent papers on robust and stochastic problems, we have only one stage of decision-making where we select a set of k facilities to open. Once a set of open facilities is fixed, each client in the uncertain client-set connects to the closest open facility. We present a simple, combinatorial O(log n + log m)-approximation algorithm for the robust k-median problem that is based on reweighting/Lagrangean-relaxation ideas. In fact, we give a general framework for (minimization) k-facility location problems where there is a bound on the number of open facilities. We show that if the location problem satisfies a certain "projection" property, then both the robust and stochastic versions of the location problem admit approximation algorithms with logarithmic ratios. We use our framework to give the first approximation algorithms for robust and stochastic versions of several location problems such as k-tree, capacitated k-median, and fault-tolerant k-median.

"Approximation Algoirthms for Network Design with Uncertainty", Ph.D. Thesis, Carnegie Mellon University, 2008.

"A Plant Location Guide for the Unsure" with Vineet Goyal, Anupam Gupta, and Viswanath 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 Anupam 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

Member, Association of Computing Machinery (ACM)

SIGACT: Special Interest Group on Algorithms and Computation Theory
SIGCSE: Special Interest Group on Computer Science Education

Member, Society for Industrial and Applied Mathematics (SIAM)

Member, Institute for Operations Research and the Management Sciences (INFORMS)

Member, Upsilon Pi Epsilon (UPE), Computer Science Honorary Society