 anthonyb@southwestern.edu
 512.863.1448
 FondrenJones 309
Notable Achievements
Professor of Computer Science Barbara Anthony was a coauthor on a poster titled “Unplugged Parallelism for FirstYear CS Majors” at the 53rd ACM Technical Symposium on Computer Science Education (SIGCSE ’22). Anthony also participated in the affiliated event Dream Big: Addressing Computing for the Social Good in the CS Curricula.
Barbara M. Anthony
Professor of Computer Science
Expertise
Approximation Algorithms, Network Design Problems. Selected areas in Operations Research, Graph Theory, Algorithmic Game Theory.
Dr. Barbara Anthony teaches a variety of computer science courses, including the introductory courses in Java and Data Structures, core courses in Discrete Math, Algorithms, and Programming Languages, electives in Databases, Operations Research, and Theory of Computation, and the capstone in Software Engineering. She has taught a First Year Seminar exploring the Internet and a variety of web applications, Colloquium in Computer Science, an a course designed to prepare students to compete in the International Collegiate Programming Contest. She sometimes teaches Introduction to Statistics on the Mathematics side of the department. She also has conducted numerous independent studies, from explorations of topics with firstyear students through seniors doing research as part of an Honors project. She is the faculty supervisor for CSC academic internships. She is currently the faculty advisor for UPE, the CS Honor Society, and is happy to help organize a number of CSthemed events throughout the year.
She received her PhD in Algorithms, Combinatorics, and Optimization from Carnegie Mellon University in 2008 and her BA from Rice University in 2001 with majors in Computational and Applied Math, French, and Mathematics. She is an ACM Senior Member, a member of UPE, CCSC and SIAM, and a certified American Sign Language interpreter.
“Computer Science is relevant for everyone these days, and has great interdisciplinary potential, especially at a liberal arts institution. As such, I believe lowerlevel courses should be accessible to any SU student, and students should be exposed to both the breadth and depth of the field.”
 Barbara Anthony
Details about some of my research can be found in my publication list, but one of the reasons that I came to Southwestern is so that I can work with students on research projects, not all of which lead to publications, though some do. Descriptions of some of the projects with students follow.
If you are an SU student interested in doing research with me, please email or drop by my office!
If you want me to write a recommendation letter for you, please complete this form.
Spring 2022: Alejandro Medina and Mark Mueller are working with me on the next steps of the Doodle Poll research project, extending the analysis to the data collected throughout the United States.
Fall 2020: Miryam Galvez and Chris Ojonta worked with me on the Doodle poll research project. We revised the study, originally conceived in Spring 2020, to work with social distancing during the pandemic. More than 200 college students participated in an IRBapproved research study where they were asked to complete Doodlestyle polls on their availability based on a hypothetical schedule they were provided. Sam Taylor funding made it possible to provide participants with a gift card in appreciation of their time. We analyzed a subset of the responses fron Southwestern University participants in various ways, including using Python scripts we developed to characterize certain performance. Miryam presented some results from our work at the 2021 Texas Academy of Sciences (Virtual) Annual Meeting in February 2021, and we had a paper accepted to the 18th International Conference on Cooperative Design, Visualization, and Engineering in October 2021.
Spring 2020: Daniel B. Merritt worked with me to begin user studies on my Doodle poll research, which had previously been largely theoretical. Since this is ongoing work that will likely involve user studies in Fall 2020, only limited details about the goals of the work can be provided publicly. Webbased Doodle polls (www.doodle.com) are a form of approval voting where participants indicate, for example, their reported availability to meet at a particular time. Since Doodle polls capture only the yes/no votes, and not other details, we will give human participants simulated Doodle polls where they report various aspects. Daniel’s contributions focused on creating the materials for the user study (though gaining IRB approval and beginning data collection was postponed due to COVID19) and developing Python scripts to facilitate the processing of the data that will be collected.
Spring 2019: Cameron Henkel extended upon a course project from the Operations Research elective I teach, where he and his groupmates analyzed the Georgetown bus system (GoGEO) and associated partnerships, including those with rideshare companies. In this project, he leveraged the Google Maps API in conjunction with public census tract data encoded as GeoJSON files to creating a data visualization tool for understanding rideshare data in a local context. While it can be fully locally hosted, allowing entities to maintain control over who has access to the data, online hosting is likewise supported by the webbased backend.
Spring 2019: Continuing a project from the Operations Research course, Katie Dyo, Devon Fulcher, and Greg O’Brien worked to deploy the tool they had developed for the Office of Admission. Each spring, alumni volunteers write to the families of admitted students, with assignments made based on shared academic interests, cocurricular interests, and geographic proximity. Using operations research techniques, we developed a software solution to this problem, that generates a list of studentalumni matches based on a computed compatibility metric and student attributes.
Spring 2019: Sara Boyd, Devon Fulcher, and Daniel Maldonado competed in the 35th annual Mathematical Contest in Modeling, sponsored by the Consortium for Mathematics and Its Applications (COMAP). For their research and modeling of a complex scenario, they earned an honorable mention.
Fall 2018 and Spring 2019: Cameron Henkel and Colin Scruggs developed https://surad.io, a mobile app and website for streaming the live shows produced by Southwestern University Radio’s DJs and talk show hosts. This app allows students to listen in wherever they are, in a format that is familiar to them. This work was done as part of a King Creativity Project.
Summer 2018: Sara Boyd, Bobby Garza, Alexander Hoffman, Stan Kannegieter, and Daniel Merritt competed in the Binance Dexathon Blockchain Coding Competition under Dr. Anthony’s supervision. The goal of the decentralized exchange coding competition was to improve on Binance’s current blockchain implementation. Along with learning more about the blockchain and practicing their software skills, the students also gained valuable experience in project management and working with teammates in remote locations. For their submission, Binance awarded the team a 10,000 BNB grant.
Spring 2018: Sara Boyd worked with me on research on a variant of the DialaRide problem, particularly the version with uniform revenues and a uniform metric. By showing that even this fundamental version is NPhard, we give insights into techniques and analysis for other variants of the problem. In addition, we explored algorithms for the uniform revenue uniform metric variant. The culmination of the work resulted in a coauthored paper on “Maximizing the number of rides served for DialaRide”, whose details are in the publication list. In Spring 2020, in part due to this work, Sara was named a finalist for the Computing Research Association Outstanding Undergraduate Researchers Award.
Fall 2017 and Spring 2018: Cameron Henkel worked on a Smart Medication Dispenser (a King Creativity project). Motivated by a desire to help his grandmother and others like her, he used a Raspberry Pi equipped with a ZWaves Developer Kit, gained experience with 3D printing, and developed software solutions which allow features like dispensing medication, restricting it to those with access, and notifications to caregivers about the dispensing. Cameron was the grand prize winner of ZWave Smart Home Maker Challenge, and presented his work at the CES Conference in Vegas.
Spring 2017: Ryan Beeman continued a course project from my Operations Research course to develop a scheduling tool for Faith in Action Georgetown, a central Texasbased nonprofit organization whose primary goal is to preserve the independence of local senior citizens by providing them transportation to errands, social events, and medical appointments. As a nonprofit organization that relies heavily on the support and activity of volunteers, efficient use of their limited funding and staff time is crucial in maintaining positive relationships with volunteers and providing the most benefit to the community. Prior to this project, Faith in Action spent a substantial amount of time scheduling rides by pairing clients (senior citizens who requested a ride) with volunteer drivers. Motivated by operations research techniques, we developed a tool to improve the scheduling process. Using data from Faith in Action’s database we created a userfriendly Excel spreadsheet to calculate a volunteer driver’s “willingness” to accept any particular ride. By contacting volunteers with a higher willingness score first, schedulers can more quickly match clients with drivers, thus reducing the total time necessary to complete scheduling each week, while maintaining a personal interaction with volunteers. Ryan plans to gain some work experience and then enroll in a master’s program in Data Science.
Spring 2017: As a firstyear computer science major, Austin Moninger worked with me to develop Java code used in ongoing research about Doodle polls. Online Doodle polls allow for the selection of a ‘good’ meeting time, with participants indicating their availability for a selection of times provided by the poll creator, essentially by voting yes or no to each time slot. Yet, a single participant can greatly impact the quality of the selected time, as measured by the total social welfare, either positively or negatively. We seek Nash equilibria: informally, there is a certain appeal when all participants look at the overall responses and cannot change their reported availability to better their personal outcome based on what other individuals have indicated. We implement Java code that aids in checking for Nash equilibria while maintaining that responses must be sincere, ensuring that no one says no to a time slot that is more desirable than one to which they said yes. This research helped Austin obtain an REU at Texas State in summer 2017.
Fall 2014  Fall 2015: Christine Harbour and Jordan King worked with me on empirically evaluating approximation algorithms for various problems. The earlier work resulted in a paper for them in the Consortium for Computing Sciences in Colleges: South Central Region Student Paper EJournal titled “An Empirical Evaluation of a kCenter 2Approximation Algorithm”, which they were able to present at the April 2015 conference. Later work then focused on approximation algorithms for bottleneck matching, and Christine presented a poster at the 2015 Grace Hopper Celebration of Women in Computing entitled “An Empirical Evaluation of Approximation Algorithms for Two Graph Problems”. Her 2016 poster at the Consortium for Computing Sciences in Colleges: South Central Conference, “An Empirical Evaluation of Approximation Algorithms for Online Bottleneck Matching”, earned first place in the student poster competition. The culmination of the work resulted in a coauthored paper on “Greedy Is Good: An Empirical Evaluation of Three Algorithms for Online Bottleneck Matching”, whose details are in the publication list. Christine is a Software Developer at eOne Solutions, and Jordan is a Software Developer at Spiceworks.
Spring 2015: Natalia Rodriguez’s project involved “Visualizing Big Data Through Juxtaposition: Mapping Body Image with Instagram Data”. She presented this work at the 2015 ACM Richard Tapia Celebration of Diversity in Computing. Natalia was one of three winners of the inaugural NCWIT Collegiate Award in 2015 for this research. She has been a Software Developer at Indicative, and a Helen Fellow in Data Visualization at the American Museum of Natural History.
Fall 2014: Kathryn Reagan had been a Community Engaged Learning Teaching Assistant in my Operations Research course in Spring 2014, and in Fall 2014 we began an IRBapproved study of the impact of the communityengaged learning component of that course, which resulted in a joint publication on “CommunityEngaged Projects in Operations Research”, with details in the publication list. After graduation, Kathryn became a consultant at ThoughtWorks, a position she had sought since first encountering that company at a Grace Hopper Celebration of Women in Computing conference she had attended early in her Southwestern years.
Fall 2014: Rebecca Wilson worked with me on several projects related to supporting underrepresented groups in computer science. One of them resulted in a publication for her entitled “CS Club: A Student Built Culture of Computing” in the Consortium for Computing Sciences in Colleges: South Central Region Student Paper EJournal, which she also got to present at the conference in April 2015. Rebecca is an Application Developer at Union Pacific Railroad.
Fall 2013: Paris Nelson worked with me on a project about genetic algorithms, with his poster presentation entitled “There and Back Again: A Genetic Algorithm Approach to the TSP” winning a prize at the Consortium for Computing Sciences in Colleges: South Central Conference. An article about another of Paris’s projects can be found here. After Southwestern, he began his career at Accenture.
Fall 2012: Erick Bauman worked with me to create a website and underlying database for a local nonprofit foster care organization, allowing tracking of information about employees and children in their system, with the necessary security and privacy constraints. Erick went on to the PhD program in Computer Science in the Systems and Software Security Lab at The University of Texas at Dallas. Erick was also involved in several other projects at Southwestern, including ones described in this link.
Fall 2010Spring 2011: As part of an Honors Project, Matthew Flatau and I developed software to implement Ruppert’s algorithm for generic curves in twodimensions, used in mesh generation. This resulted in the Research Note at the International Meshing Roundtable (see Publications list), where Matthew presented about our work. Matthew went on to graduate study in Computer Science at the University of WisconsinMadison, and then became a software developer at Epic.
Spring 2009: Dak Erwin (as of 2017, a Software Engineer at b.well Connected Health) and I explored Latency on Wireless Sensor Networks when he was a firstyear student at Southwestern.
Selected Funding Awards
NCWIT Extension Services Learning Circles $10,000 to support the recruitment and retention of women in computing, 2019.
NSF SSTEM Award, Broadening the Net: Promoting Success in the Sciences for All Students, Southwestern University, CoPI, 5 years, $614,325, July 2015.
Google CS Engagement Award ($5000), towards the development and integration of instructional materials for increasing student engagement and retention in introductory computer science classes, Spring 2015. One of 53 CS faculty and instructors from colleges and universities in 24 U.S. states to receive this award.
Student coauthors underlined.
“Questions of Sincerity in Cooperative Doodle Polls” with Miryam Galvez and Chris Ojonta. In: Luo Y. (eds) 18th International Conference on Cooperative Design, Visualization, and Engineering (CDVE 2021). Lecture Notes in Computer Science, vol 12983, Springer, October 2021.
Online tools like Doodle polls are frequently used for meeting coordination and other decentralized cooperative decision making. Since Doodle polls are a form of approval voting, theoretical results from voting theory often underpin work in this area. Sincerity, where a voter never says yes to a lesspreferred option without saying yes to all more preferable choices, is a common assumption in approval voting. However, that does not take into account cooperative behavior sometimes exhibited by users when others’ responses are known. We conduct a user study investigating the extent to which collegestudent participants in Doodlestyle polls were sincere, reporting on responses from one institution.
“Using the UCSC Genome Browser in a Database Course” Journal of Computing Sciences in Colleges, Volume 37, Number 2, pp. 2329, October 2021.
Students can benefit greatly from working with real databases in their first Database course. A database for a university is a common textbook example, in part due to its familiarity, but privacy and other considerations typically preclude course access to this and many other large, meaningful databases. This paper reports on two semesters’ experience using the University of California Santa Cruz Genome Browser [6] in a Database course, allowing midlevel computer science undergraduates to gain handson experience with a large realworld database. Anonymous survey feedback from students in both semesters was positive for both engagement and increased knowledge. The activity described within can easily be adopted by others, requires no software installation, and can be adapted to the desired length and difficulty level.
“Serving rides of equal importance for budgeted DialaRide” with Ananya Christman, Christine Chung and David Yuen. In: Pardalos P., Khachay M., Kazakov A. (eds) Mathematical Optimization Theory and Operations Research (MOTOR 2021). Lecture Notes in Computer Science, vol 12755, pp. 3550, conference held July 2021.
We consider a variant of the offline DialaRide problem with a single server where each request has a source, destination, and a prize earned for serving it. The goal for the server is to serve requests within a given time limit so as to maximize the total prize money. We consider the variant where prize amounts are uniform which is equivalent to maximizing the number of requests served. This setting is applicable when all rides may have equal importance such as paratransit services. We first prove that no polynomialtime algorithm can be guaranteed to serve the optimal number of requests, even when the time limit for the algorithm is augmented by any constant factor c >=1. We also show that if lambda = t_max/t_min, where t_max and t_min denote the largest and smallest edge weights in the graph, the approximation ratio for a reasonable class of algorithms for this problem is unbounded, unless lambda is bounded. We then show that the segmented best path (SBP) algorithm from [8] is a 4approximation. We then present our main result, an algorithm, k Sequence, that repeatedly serves the fastest set of k remaining requests, and provide upper and lower bounds on its performance. We show kSequence has approximation ratio at most 2+ ceil(lambda)/k and at least 1 + lambda/k and that is tight when 1+lambda/k \geq k. Thus, for the case of k = 1, i.e., when the algorithm repeatedly serves the quickest request, it has approximation ratio 1+lambda, which is tight for all lambda. We also show that even as k grows beyond the size of lambda, the ratio never improves below 9/7.
“Directed Zagreb Indices” with Alison M. Marr, 18th CologneTwente Workshop on Graphs and Combinatorial Optimization, Graphics and Combinatorial Optimization: from Theory to Applications, AIRO Springer Series, Volume 5, pp. 181193, 2021. (Conference in Ischia, Italy in September 2020 (postponed from June 2020 due to COVID19).
Zagreb indices for undirected graphs were introduced nearly 50 years ago. Their original development was related to uses in chemistry, but over time mathematicians have also found them to be an interesting topic of study. We define and introduce Zagreb indices for directed graphs, give results that parallel many of the conjectures and theorems that exist for the original Zagreb indices, and produce results specific to the directed graph case.
“Equilibria in Doodle Polls under Three TieBreaking Rules” with Christine Chung, Theoretical Computer Science, Volume 822, pp. 6171, June 2020.
Doodle polls allow people to schedule meetings or events based on time preferences of participants. Each participant indicates on a webbased poll form which time slots they find acceptable and a time slot with the most votes is chosen. This is a social choice mechanism known as approval voting, in which a standard assumption is that all voters vote sincerely—no one votes “no” on a time slot they prefer to a time slot they have voted “yes” on. We take a gametheoretic approach to understanding what happens in approval voting assuming participants vote sincerely. While our instances are framed in the context of the Doodle poll application, the results apply more broadly to approval voting. First we characterize Doodle poll instances where sincere pure Nash Equilibria (NE) exist, under lexicographic tiebreaking, random candidate, and random voter tiebreaking. We then study the quality of such NE voting profiles in Doodle polls, showing the price of anarchy and price of stability are both unbounded, even when a time slot that many participants vote yes for is selected. Finally, we find some reasonable conditions under which the quality of the NE (and strong NE) is good.
”Introducing Parallelism to FirstYear CS Majors” with D.C. Erdil, O. Glebova, and R. Montante, [Poster], 51st ACM Technical Symposium on Computer Science Education (SIGCSE ’20), March 2020. Conference cancelled on day of presentation due to COVID19, moved to online format.
We propose to strengthen the computer science (CS) curriculum by embedding parallel concepts in a required firstsemester seminar taken by all incoming declared CS majors. We introduce students to parallel computing concepts through a series of unplugged activities so that students see parallel approaches as a natural form of solution to a task. We describe a pilot offering of the class and activities, with measurements and analysis of what students selfreport and their performance on assessments.
“Maximizing the number of rides served for DialaRide” with Ricky Birnbaum, Sara Boyd, Ananya Christman, Christine Chung, Patrick Davis, Jigar Dhimar, and David Yuen, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), OASICS Vol. 75, pp. 11:111:15, September 2019.
We study a variation of offline DialaRide, where each request has not only a source and destination, but also a revenue that is earned for serving the request. We investigate this problem for the uniform metric space with uniform revenues. While we present a study on a simplified setting of the problem that has limited practical applications, this work provides the theoretical foundation for analyzing the more general forms of the problem. Since revenues are uniform the problem is equivalent to maximizing the number of served requests. We show that the problem is NPhard and present a 2/3 approximation algorithm. We also show that a natural generalization of this algorithm has an approximation ratio at most 7/9.
“Greedy Is Good: An Empirical Evaluation of Three Algorithms for Online Bottleneck Matching,” with Christine Harbour and Jordan King, Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 108, pp. 1531, February 2019.
We empirically evaluate the performance of three approximation algorithms for the online bottleneck matching problem. In this matching problem, k serververtices lie in a metric space and k requestvertices that arrive over time each must immediately be permanently assigned to a serververtex. The goal is to minimize the maximum distance between any request and its assigned server. We consider the naive GREEDY algorithm, as well as PERMUTATION, and BALANCE, each of which were constructed to counter certain challenges in the online problem. We analyze the performance of each algorithm on a variety of data sets, considering each both in the original model, where applicable, and in the resource augmentation setting when an extra server is introduced at each serververtex. While no algorithm strictly dominates, GREEDY frequently performs the best, and thus is recommended due to its simplicity.
”Inefficiency of Equilibria in Doodle Polls”, with Christine Chung, In: Kim D., Uma R., Zelikovsky A. (eds) Combinatorial Optimization and Applications. COCOA 2018. Lecture Notes in Computer Science, vol 11346. Springer, 2018.
Doodle polls allow people to schedule meetings or events based on time preferences of participants. Each participant indicates on a webbased poll form which time slots they find acceptable and a time slot with the most votes is chosen. This is a social choice mechanism known as approval voting, in which a standard assumption is that all voters vote sincerely—no one votes “no” on a time slot they prefer to a time slot they have voted “yes” on. We take a gametheoretic approach to understanding what happens in Doodle polls assuming participants vote sincerely. First we characterize Doodle poll instances where sincere pure Nash Equilibria (NE) exist, both under lexicographic tiebreaking and randomized tiebreaking. We then study the quality of such NE voting profiles in Doodle polls, showing the price of anarchy and price of stability are both unbounded, even when a time slot that many participants vote yes for is selected. Finally, we find some reasonable conditions under which the quality of the NE (and strong NE) is good.
“Modernizing the Mythical ManMonth”, with Valentin Cantu, Jr., Journal of Computing Sciences in Colleges, Volume 34, Number 2, pp. 110116, December 2018.
The Mythical ManMonth: Essays on Software Engineering by Dr. Fred Brooks is often required reading in many software engineering classes and recommended by practitioners throughout industry as a text with which computer scientists should be familiar. Yet, while many of the conceptual ideas that were first presented decades ago are still applicable today, aspects of the presentation of the material are lacking in inclusivity, posing additional challenges for faculty who are trying to increase diversity within the discipline. Thus, we propose a studentdeveloped portrayal of some of the concepts in a modernized fashion, presented as a menu and incorporating ideas from the foodservice industry, a model that more college students are directly familiar with than the surgical team.
“How Bad is Selfish Doodle Voting?” [Extended Abstract], with C. Chung, Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018), Stockholm, Sweden, pp. 18561858, July 1015, 2018.
Doodle polls allow people to schedule meetings or events based on the time preferences of participants. Each participant indicates on a webbased poll form which time slots they find acceptable and a time slot with the most votes is chosen. This is a social choice mechanism known as approval voting, in which a standard assumption is that all voters vote sincerely: no one votes no on a time slot they prefer to a time slot they have voted yes on. We take a game theoretical approach to understanding what happens in Doodle polls assuming participants vote sincerely.
Many computer science courses use final exams as one means of evaluating student performance within the course, but developing meaningful assessments can be both difficult and timeconsuming. Students and faculty alike can experience both stress and frustration with various aspects of the exam process. By stepping back and evaluating the overall goals of computer science courses and the curriculum, some questions arise as viable options for final exams in a variety of computer science courses. These questions enable students to consider prior courses, projects or presentations within the course, future use of the material, or handle what may be perceived as incomplete coverage in the final exam. Some potential concerns about these questions are addressed. While these questions will not replace all of the traditional questions, they may provide different types of assessment information, and enable reflection for both students and faculty.
“CommunityEngaged Projects in Operations Research,” with Kathryn Reagan, Science Education & Civic Engagement: An International Journal, Volume 9, Issue 2, pp. 512, Summer 2017.
Communityengaged learning is not very common in technical fields, but including relevant projects in courses can make it feasible and successful. We present an implementation of an operations research course at a liberal arts college. Working with one of four nonprofit community partners to optimize aspects of their organization, students gained insight into relevant, realworld applications of the field of operations research. By considering many aspects of their solution when presenting it to community partners, students were exposed to some issues facing local nonprofit organizations. We discuss the specific implementation of this course, including both positive learning outcomes and challenging factors.
While enrollments in computer science courses may be increasing overall, the recruitment and retention of women and minorities in computer science remains a pervasive problem. First Year Seminars at universities are relatively common, and though they take on a variety of formats, many are designed to help with the transition to college and to increase retention. For three years, a computer science faculty member taught a First Year Seminar, broadly about the Internet, though with limited technical details, surveying the students about their perceptions of computer science. The results, while not conclusive, may provide motivation for other computer science professors to teach a First Year Seminar related to technology.
“How Well Do Doodle Polls Do?,” with Danya Alrawi and Christine Chung, Proceedings of the 8th International Conference on Social Informatics (SocInfo16), LNCS 10046, Volume 1, pp. 323, November 2016.
Webbased Doodle polls, where respondents indicate their availability for a collection of times provided by the poll initiator, are an increasingly common way of selecting a time for an event or meeting. Yet group dynamics can markedly influence an individual’s response, and thus the overall solution quality. Via theoretical worstcase analysis, we analyze certain common behaviors of Doodle poll respondents, including when participants are either more generous with or more protective of their time, showing that deviating from one’s “true availability” can have a substantial impact on the overall quality of the selected time. We show perhaps counterintuitively that being more generous with your time can lead to inferior time slots being selected, and being more protective of your time can lead to superior time slots being selected. We also bound the improvement and degradation of outcome quality under both types of behaviors.
“Serve or Skip: The Power of Rejection for Online Bottleneck Matching,” with Christine Chung, Journal of Combinatorial Optimization, Volume 32, Issue 4, pp. 12321253, November 2016.
We consider the online matching problem, where n serververtices lie in a metric space and n requestvertices that arrive over time each must immediately be permanently assigned to a serververtex. We focus on the egalitarian bottleneck objective, where the goal is to minimize the maximum distance between any request and its server. It has been shown that while there are effective algorithms for the utilitarian objective (minimizing total cost) in the resource augmentation setting where the offline adversary has half the resources, these are not effective for the egalitarian objective. Thus, we propose a new ServeorSkip (SoS) bicriteria analysis model, where the online algorithm may reject or skip up to a specified number of requests, and propose two greedy algorithms: GriNN(t) and GRIN_(t) . We show that the SoS model of resource augmentation analysis can essentially simulate the doubledservercapacity model, and then examine the performance of GriNN(t) and GRIN_(t).
“Complete rpartite graphs determined by their domination polynomial,” with Michael Picollelli, Graphs and Combinatorics, Volume 31, Issue 6, pp. 19932002, November 2015.
The domination polynomial of a graph is the polynomial whose coefficients count the number of dominating sets of each cardinality. A recent question asks which graphs are uniquely determined (up to isomorphism) by their domination polynomial. In this paper, we completely describe the complete rpartite graphs which are; in the bipartite case, this settles in the affirmative a conjecture of Aalipour et al. (Ars Comb, 2014).
“Conditions for the Bicolorability of Primitive Hypergraphs,” with Richard Denman, Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 94, pp. 2741, August 2015.
A primitive hypergraph is a hypergraph with maximum cardinality three and maximum degree three such that every 3edge is adjacent only to 2edges and is incident only to vertices of degree two. Deciding the bicolorability of a primitive hypergraph is NPcomplete (a straightforward consequence of results in Kratochvil and Tuza). We provide sufficient conditions, similar to the Sterboul conditions proved by Defossez, for the existence of a bicoloring of a primitive hypergraph, and we provide a polynomial algorithm for bicoloring a primitive hypergraph if those conditions hold. We then draw a connection between this algorithm and the wellknown necessary and sufficient conditions given by Berge for maximal matchings in graphs, which leads to a characterization of bicolorability of primitive hypergraphs.
“The Power of Rejection in Online Bottleneck Matching,” with Christine Chung, Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA’14), LNCS, pp. 395411, December 2014.
We consider the online matching problem, where n serververtices lie in a metric space and n requestvertices that arrive over time each must immediately be permanently assigned to a serververtex. We focus on the egalitarian bottleneck objective, where the goal is to minimize the maximum distance between and request and its server. It has been demonstrated that while there are effective algorithms for the utilitarian objective (minimizing total cost) in the resource augmentation setting where the offline adversary has half the resources, these are not effective for the egalitarian objective. Thus, we propose a new ServeorSkip bicriteria analysis model, where the online algorithm may reject or skip up to a specified number of requests, and propose two greedy algorithms: GriNN(t) and Grin*(t). We show that the ServeorSkip model of resource augmentation analysis can simulate the doubledserver capacity model, and then characterize the performance of GriNN(T) and Grin*(t).
“Offering an Undergraduate Computer Science Colloquium,” Journal of Computing Sciences in Colleges, Volume 29, Number 4, pp. 612, April 2014.
An undergraduate computer science colloquium is presented that can enhance the educational opportunities for students at a small liberal arts college while providing an additional communitybuilding venue for majors at various stages of their college careers. Presentation skills are a key component of this onecredit course, and the pass/fail grading system can alleviate some student concerns about their performance and allow them to focus on improving in this critical area. Additionally, though the number of electives offered at a small college may be small, a colloquium provides the means for exposure to a greater breadth of computer science topics, potentially helping students develop new interests within the discipline. After being piloted as a special topics course in Spring 2011, Southwestern University has now added the undergraduate colloquium to the regular spring course offerings.
“Online Bottleneck Matching,” with Christine Chung, Journal of Combinatorial Optimization, Volume 27, Issue 1, pp. 100114, January 2014. An earlier version appeared in Proceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA’12), LNCS 7402, pp. 257268, August 2012.
We consider the online bottleneck matching problem, where k serververtices lie in a metric space and k requestvertices that arrive over time each must immediately be permanently assigned to a serververtex. 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 serververtex has one server) to linear (when each serververtex has two servers), the competitive ratio of Permutation remains linear. The competitive ratio of Balance is also linear with an extra server at each serververtex, even though it has been shown that an extra server makes it constantcompetitive for the minweight matching problem.
“Data Plan Throttling: A Simple Consumer Choice Mechanism,” with Christine Chung, Proceedings of the IEEE Global Communications Conference (GLOBECOM 2013), pp. 31733178, December 2013.
Despite only a small portion of unlimited data plan users experiencing throttling each month, it is a prominent source of complaints from users and a significant concern for mobile network operators. We propose a simple mechanism that allows users to choose when they want their data transmission “fast,” and when they want it “slow.” Users still have the same cap on total highspeed transfer before being throttled, and hence may still be subject to throttling, but now they are given some control. We propose a basic model of payoffs, and demonstrate that the proposed mechanism would be preferable to the user over the throttling policies currently in place. We then consider the impacts that extend beyond a single user, and provide a framework for determining the aggregate effects of such a mechanism.
“Operations research: Broadening computer science in a liberal arts college,” Proceedings of the 43rd ACM Technical Symposium on Computer Science Education (SIGCSE ’12), pp. 463468, 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 upperlevel elective, and it was also crosslisted 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 filledtocapacity upperlevel 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 nonmajor 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. 245260, 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 straightline inputs, fewer are available for handling curved inputs, even in 2D. Many are based on the wellknown 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 applicationspecific. 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 preprocessing steps in the spirit of Pav and Walkington and a generalized midpoint calculation.
Feel free to email me for a copy. The code is freely available under the MIT License at http://code.google.com/p/reuleaux/
“A Plant Location Guide for the Unsure: Approximation Algorithms for MinMax Location Problems” with Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan, Mathematics of Operations Research, Vol. 35, No. 1, pp. 79101, February 2010.
This paper studies an extension of the kmedian problem under uncertain demand. We are given an nvertex 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 worstcase connection cost over all the client sets is minimized, i.e., \min_{F \subseteq V, PIPE F PIPE = 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 “minmax” or “robust” version of the kmedian problem. Note that in contrast to the recent papers on robust and stochastic problems, we have only one stage of decisionmaking where we select a set of k facilities to open. Once a set of open facilities is fixed, each client in the uncertain clientset connects to the closest open facility. We present a simple, combinatorial O(log n + log m)approximation algorithm for the robust kmedian problem that is based on reweighting/Lagrangeanrelaxation ideas. In fact, we give a general framework for (minimization) kfacility 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 ktree, capacitated kmedian, and faulttolerant kmedian.
“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 ACMSIAM Symposium on Discrete Algorithms (SODA), 2008.
Consider a minmax version of the kmedian 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 reversegreedy algorithm for the minmax version of the problem. Using this, we give algorithms for faulttolerant and capacitated versions of kmedian, as well as the ktree problem. Finally, we show that stochastic versions of kcenter are as hard as denseksubgraph.
“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.

Biography
Dr. Barbara Anthony teaches a variety of computer science courses, including the introductory courses in Java and Data Structures, core courses in Discrete Math, Algorithms, and Programming Languages, electives in Databases, Operations Research, and Theory of Computation, and the capstone in Software Engineering. She has taught a First Year Seminar exploring the Internet and a variety of web applications, Colloquium in Computer Science, an a course designed to prepare students to compete in the International Collegiate Programming Contest. She sometimes teaches Introduction to Statistics on the Mathematics side of the department. She also has conducted numerous independent studies, from explorations of topics with firstyear students through seniors doing research as part of an Honors project. She is the faculty supervisor for CSC academic internships. She is currently the faculty advisor for UPE, the CS Honor Society, and is happy to help organize a number of CSthemed events throughout the year.
She received her PhD in Algorithms, Combinatorics, and Optimization from Carnegie Mellon University in 2008 and her BA from Rice University in 2001 with majors in Computational and Applied Math, French, and Mathematics. She is an ACM Senior Member, a member of UPE, CCSC and SIAM, and a certified American Sign Language interpreter.
“Computer Science is relevant for everyone these days, and has great interdisciplinary potential, especially at a liberal arts institution. As such, I believe lowerlevel courses should be accessible to any SU student, and students should be exposed to both the breadth and depth of the field.”
 Barbara Anthony 
Research
Details about some of my research can be found in my publication list, but one of the reasons that I came to Southwestern is so that I can work with students on research projects, not all of which lead to publications, though some do. Descriptions of some of the projects with students follow.
If you are an SU student interested in doing research with me, please email or drop by my office!
If you want me to write a recommendation letter for you, please complete this form.
Spring 2022: Alejandro Medina and Mark Mueller are working with me on the next steps of the Doodle Poll research project, extending the analysis to the data collected throughout the United States.
Fall 2020: Miryam Galvez and Chris Ojonta worked with me on the Doodle poll research project. We revised the study, originally conceived in Spring 2020, to work with social distancing during the pandemic. More than 200 college students participated in an IRBapproved research study where they were asked to complete Doodlestyle polls on their availability based on a hypothetical schedule they were provided. Sam Taylor funding made it possible to provide participants with a gift card in appreciation of their time. We analyzed a subset of the responses fron Southwestern University participants in various ways, including using Python scripts we developed to characterize certain performance. Miryam presented some results from our work at the 2021 Texas Academy of Sciences (Virtual) Annual Meeting in February 2021, and we had a paper accepted to the 18th International Conference on Cooperative Design, Visualization, and Engineering in October 2021.
Spring 2020: Daniel B. Merritt worked with me to begin user studies on my Doodle poll research, which had previously been largely theoretical. Since this is ongoing work that will likely involve user studies in Fall 2020, only limited details about the goals of the work can be provided publicly. Webbased Doodle polls (www.doodle.com) are a form of approval voting where participants indicate, for example, their reported availability to meet at a particular time. Since Doodle polls capture only the yes/no votes, and not other details, we will give human participants simulated Doodle polls where they report various aspects. Daniel’s contributions focused on creating the materials for the user study (though gaining IRB approval and beginning data collection was postponed due to COVID19) and developing Python scripts to facilitate the processing of the data that will be collected.
Spring 2019: Cameron Henkel extended upon a course project from the Operations Research elective I teach, where he and his groupmates analyzed the Georgetown bus system (GoGEO) and associated partnerships, including those with rideshare companies. In this project, he leveraged the Google Maps API in conjunction with public census tract data encoded as GeoJSON files to creating a data visualization tool for understanding rideshare data in a local context. While it can be fully locally hosted, allowing entities to maintain control over who has access to the data, online hosting is likewise supported by the webbased backend.
Spring 2019: Continuing a project from the Operations Research course, Katie Dyo, Devon Fulcher, and Greg O’Brien worked to deploy the tool they had developed for the Office of Admission. Each spring, alumni volunteers write to the families of admitted students, with assignments made based on shared academic interests, cocurricular interests, and geographic proximity. Using operations research techniques, we developed a software solution to this problem, that generates a list of studentalumni matches based on a computed compatibility metric and student attributes.
Spring 2019: Sara Boyd, Devon Fulcher, and Daniel Maldonado competed in the 35th annual Mathematical Contest in Modeling, sponsored by the Consortium for Mathematics and Its Applications (COMAP). For their research and modeling of a complex scenario, they earned an honorable mention.
Fall 2018 and Spring 2019: Cameron Henkel and Colin Scruggs developed https://surad.io, a mobile app and website for streaming the live shows produced by Southwestern University Radio’s DJs and talk show hosts. This app allows students to listen in wherever they are, in a format that is familiar to them. This work was done as part of a King Creativity Project.
Summer 2018: Sara Boyd, Bobby Garza, Alexander Hoffman, Stan Kannegieter, and Daniel Merritt competed in the Binance Dexathon Blockchain Coding Competition under Dr. Anthony’s supervision. The goal of the decentralized exchange coding competition was to improve on Binance’s current blockchain implementation. Along with learning more about the blockchain and practicing their software skills, the students also gained valuable experience in project management and working with teammates in remote locations. For their submission, Binance awarded the team a 10,000 BNB grant.
Spring 2018: Sara Boyd worked with me on research on a variant of the DialaRide problem, particularly the version with uniform revenues and a uniform metric. By showing that even this fundamental version is NPhard, we give insights into techniques and analysis for other variants of the problem. In addition, we explored algorithms for the uniform revenue uniform metric variant. The culmination of the work resulted in a coauthored paper on “Maximizing the number of rides served for DialaRide”, whose details are in the publication list. In Spring 2020, in part due to this work, Sara was named a finalist for the Computing Research Association Outstanding Undergraduate Researchers Award.
Fall 2017 and Spring 2018: Cameron Henkel worked on a Smart Medication Dispenser (a King Creativity project). Motivated by a desire to help his grandmother and others like her, he used a Raspberry Pi equipped with a ZWaves Developer Kit, gained experience with 3D printing, and developed software solutions which allow features like dispensing medication, restricting it to those with access, and notifications to caregivers about the dispensing. Cameron was the grand prize winner of ZWave Smart Home Maker Challenge, and presented his work at the CES Conference in Vegas.
Spring 2017: Ryan Beeman continued a course project from my Operations Research course to develop a scheduling tool for Faith in Action Georgetown, a central Texasbased nonprofit organization whose primary goal is to preserve the independence of local senior citizens by providing them transportation to errands, social events, and medical appointments. As a nonprofit organization that relies heavily on the support and activity of volunteers, efficient use of their limited funding and staff time is crucial in maintaining positive relationships with volunteers and providing the most benefit to the community. Prior to this project, Faith in Action spent a substantial amount of time scheduling rides by pairing clients (senior citizens who requested a ride) with volunteer drivers. Motivated by operations research techniques, we developed a tool to improve the scheduling process. Using data from Faith in Action’s database we created a userfriendly Excel spreadsheet to calculate a volunteer driver’s “willingness” to accept any particular ride. By contacting volunteers with a higher willingness score first, schedulers can more quickly match clients with drivers, thus reducing the total time necessary to complete scheduling each week, while maintaining a personal interaction with volunteers. Ryan plans to gain some work experience and then enroll in a master’s program in Data Science.
Spring 2017: As a firstyear computer science major, Austin Moninger worked with me to develop Java code used in ongoing research about Doodle polls. Online Doodle polls allow for the selection of a ‘good’ meeting time, with participants indicating their availability for a selection of times provided by the poll creator, essentially by voting yes or no to each time slot. Yet, a single participant can greatly impact the quality of the selected time, as measured by the total social welfare, either positively or negatively. We seek Nash equilibria: informally, there is a certain appeal when all participants look at the overall responses and cannot change their reported availability to better their personal outcome based on what other individuals have indicated. We implement Java code that aids in checking for Nash equilibria while maintaining that responses must be sincere, ensuring that no one says no to a time slot that is more desirable than one to which they said yes. This research helped Austin obtain an REU at Texas State in summer 2017.
Fall 2014  Fall 2015: Christine Harbour and Jordan King worked with me on empirically evaluating approximation algorithms for various problems. The earlier work resulted in a paper for them in the Consortium for Computing Sciences in Colleges: South Central Region Student Paper EJournal titled “An Empirical Evaluation of a kCenter 2Approximation Algorithm”, which they were able to present at the April 2015 conference. Later work then focused on approximation algorithms for bottleneck matching, and Christine presented a poster at the 2015 Grace Hopper Celebration of Women in Computing entitled “An Empirical Evaluation of Approximation Algorithms for Two Graph Problems”. Her 2016 poster at the Consortium for Computing Sciences in Colleges: South Central Conference, “An Empirical Evaluation of Approximation Algorithms for Online Bottleneck Matching”, earned first place in the student poster competition. The culmination of the work resulted in a coauthored paper on “Greedy Is Good: An Empirical Evaluation of Three Algorithms for Online Bottleneck Matching”, whose details are in the publication list. Christine is a Software Developer at eOne Solutions, and Jordan is a Software Developer at Spiceworks.
Spring 2015: Natalia Rodriguez’s project involved “Visualizing Big Data Through Juxtaposition: Mapping Body Image with Instagram Data”. She presented this work at the 2015 ACM Richard Tapia Celebration of Diversity in Computing. Natalia was one of three winners of the inaugural NCWIT Collegiate Award in 2015 for this research. She has been a Software Developer at Indicative, and a Helen Fellow in Data Visualization at the American Museum of Natural History.
Fall 2014: Kathryn Reagan had been a Community Engaged Learning Teaching Assistant in my Operations Research course in Spring 2014, and in Fall 2014 we began an IRBapproved study of the impact of the communityengaged learning component of that course, which resulted in a joint publication on “CommunityEngaged Projects in Operations Research”, with details in the publication list. After graduation, Kathryn became a consultant at ThoughtWorks, a position she had sought since first encountering that company at a Grace Hopper Celebration of Women in Computing conference she had attended early in her Southwestern years.
Fall 2014: Rebecca Wilson worked with me on several projects related to supporting underrepresented groups in computer science. One of them resulted in a publication for her entitled “CS Club: A Student Built Culture of Computing” in the Consortium for Computing Sciences in Colleges: South Central Region Student Paper EJournal, which she also got to present at the conference in April 2015. Rebecca is an Application Developer at Union Pacific Railroad.
Fall 2013: Paris Nelson worked with me on a project about genetic algorithms, with his poster presentation entitled “There and Back Again: A Genetic Algorithm Approach to the TSP” winning a prize at the Consortium for Computing Sciences in Colleges: South Central Conference. An article about another of Paris’s projects can be found here. After Southwestern, he began his career at Accenture.
Fall 2012: Erick Bauman worked with me to create a website and underlying database for a local nonprofit foster care organization, allowing tracking of information about employees and children in their system, with the necessary security and privacy constraints. Erick went on to the PhD program in Computer Science in the Systems and Software Security Lab at The University of Texas at Dallas. Erick was also involved in several other projects at Southwestern, including ones described in this link.
Fall 2010Spring 2011: As part of an Honors Project, Matthew Flatau and I developed software to implement Ruppert’s algorithm for generic curves in twodimensions, used in mesh generation. This resulted in the Research Note at the International Meshing Roundtable (see Publications list), where Matthew presented about our work. Matthew went on to graduate study in Computer Science at the University of WisconsinMadison, and then became a software developer at Epic.
Spring 2009: Dak Erwin (as of 2017, a Software Engineer at b.well Connected Health) and I explored Latency on Wireless Sensor Networks when he was a firstyear student at Southwestern.
Selected Funding Awards
NCWIT Extension Services Learning Circles $10,000 to support the recruitment and retention of women in computing, 2019.
NSF SSTEM Award, Broadening the Net: Promoting Success in the Sciences for All Students, Southwestern University, CoPI, 5 years, $614,325, July 2015.
Google CS Engagement Award ($5000), towards the development and integration of instructional materials for increasing student engagement and retention in introductory computer science classes, Spring 2015. One of 53 CS faculty and instructors from colleges and universities in 24 U.S. states to receive this award.
Received funding through the Computing Research Association CREU (Collaborative Research Experience for Undergraduates) for two underrepresented students to do research with me for the 20142015 academic year. ($3000 per student, plus travel money, totaling $7500 initially, with additional travel funds provided for Tapia 2015) 
Publications
Student coauthors underlined.
“Questions of Sincerity in Cooperative Doodle Polls” with Miryam Galvez and Chris Ojonta. In: Luo Y. (eds) 18th International Conference on Cooperative Design, Visualization, and Engineering (CDVE 2021). Lecture Notes in Computer Science, vol 12983, Springer, October 2021.
Online tools like Doodle polls are frequently used for meeting coordination and other decentralized cooperative decision making. Since Doodle polls are a form of approval voting, theoretical results from voting theory often underpin work in this area. Sincerity, where a voter never says yes to a lesspreferred option without saying yes to all more preferable choices, is a common assumption in approval voting. However, that does not take into account cooperative behavior sometimes exhibited by users when others’ responses are known. We conduct a user study investigating the extent to which collegestudent participants in Doodlestyle polls were sincere, reporting on responses from one institution.
“Using the UCSC Genome Browser in a Database Course” Journal of Computing Sciences in Colleges, Volume 37, Number 2, pp. 2329, October 2021.
Students can benefit greatly from working with real databases in their first Database course. A database for a university is a common textbook example, in part due to its familiarity, but privacy and other considerations typically preclude course access to this and many other large, meaningful databases. This paper reports on two semesters’ experience using the University of California Santa Cruz Genome Browser [6] in a Database course, allowing midlevel computer science undergraduates to gain handson experience with a large realworld database. Anonymous survey feedback from students in both semesters was positive for both engagement and increased knowledge. The activity described within can easily be adopted by others, requires no software installation, and can be adapted to the desired length and difficulty level.
“Serving rides of equal importance for budgeted DialaRide” with Ananya Christman, Christine Chung and David Yuen. In: Pardalos P., Khachay M., Kazakov A. (eds) Mathematical Optimization Theory and Operations Research (MOTOR 2021). Lecture Notes in Computer Science, vol 12755, pp. 3550, conference held July 2021.
We consider a variant of the offline DialaRide problem with a single server where each request has a source, destination, and a prize earned for serving it. The goal for the server is to serve requests within a given time limit so as to maximize the total prize money. We consider the variant where prize amounts are uniform which is equivalent to maximizing the number of requests served. This setting is applicable when all rides may have equal importance such as paratransit services. We first prove that no polynomialtime algorithm can be guaranteed to serve the optimal number of requests, even when the time limit for the algorithm is augmented by any constant factor c >=1. We also show that if lambda = t_max/t_min, where t_max and t_min denote the largest and smallest edge weights in the graph, the approximation ratio for a reasonable class of algorithms for this problem is unbounded, unless lambda is bounded. We then show that the segmented best path (SBP) algorithm from [8] is a 4approximation. We then present our main result, an algorithm, k Sequence, that repeatedly serves the fastest set of k remaining requests, and provide upper and lower bounds on its performance. We show kSequence has approximation ratio at most 2+ ceil(lambda)/k and at least 1 + lambda/k and that is tight when 1+lambda/k \geq k. Thus, for the case of k = 1, i.e., when the algorithm repeatedly serves the quickest request, it has approximation ratio 1+lambda, which is tight for all lambda. We also show that even as k grows beyond the size of lambda, the ratio never improves below 9/7.
“Directed Zagreb Indices” with Alison M. Marr, 18th CologneTwente Workshop on Graphs and Combinatorial Optimization, Graphics and Combinatorial Optimization: from Theory to Applications, AIRO Springer Series, Volume 5, pp. 181193, 2021. (Conference in Ischia, Italy in September 2020 (postponed from June 2020 due to COVID19).
Zagreb indices for undirected graphs were introduced nearly 50 years ago. Their original development was related to uses in chemistry, but over time mathematicians have also found them to be an interesting topic of study. We define and introduce Zagreb indices for directed graphs, give results that parallel many of the conjectures and theorems that exist for the original Zagreb indices, and produce results specific to the directed graph case.
“Equilibria in Doodle Polls under Three TieBreaking Rules” with Christine Chung, Theoretical Computer Science, Volume 822, pp. 6171, June 2020.
Doodle polls allow people to schedule meetings or events based on time preferences of participants. Each participant indicates on a webbased poll form which time slots they find acceptable and a time slot with the most votes is chosen. This is a social choice mechanism known as approval voting, in which a standard assumption is that all voters vote sincerely—no one votes “no” on a time slot they prefer to a time slot they have voted “yes” on. We take a gametheoretic approach to understanding what happens in approval voting assuming participants vote sincerely. While our instances are framed in the context of the Doodle poll application, the results apply more broadly to approval voting. First we characterize Doodle poll instances where sincere pure Nash Equilibria (NE) exist, under lexicographic tiebreaking, random candidate, and random voter tiebreaking. We then study the quality of such NE voting profiles in Doodle polls, showing the price of anarchy and price of stability are both unbounded, even when a time slot that many participants vote yes for is selected. Finally, we find some reasonable conditions under which the quality of the NE (and strong NE) is good.
”Introducing Parallelism to FirstYear CS Majors” with D.C. Erdil, O. Glebova, and R. Montante, [Poster], 51st ACM Technical Symposium on Computer Science Education (SIGCSE ’20), March 2020. Conference cancelled on day of presentation due to COVID19, moved to online format.
We propose to strengthen the computer science (CS) curriculum by embedding parallel concepts in a required firstsemester seminar taken by all incoming declared CS majors. We introduce students to parallel computing concepts through a series of unplugged activities so that students see parallel approaches as a natural form of solution to a task. We describe a pilot offering of the class and activities, with measurements and analysis of what students selfreport and their performance on assessments.
“Maximizing the number of rides served for DialaRide” with Ricky Birnbaum, Sara Boyd, Ananya Christman, Christine Chung, Patrick Davis, Jigar Dhimar, and David Yuen, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), OASICS Vol. 75, pp. 11:111:15, September 2019.
We study a variation of offline DialaRide, where each request has not only a source and destination, but also a revenue that is earned for serving the request. We investigate this problem for the uniform metric space with uniform revenues. While we present a study on a simplified setting of the problem that has limited practical applications, this work provides the theoretical foundation for analyzing the more general forms of the problem. Since revenues are uniform the problem is equivalent to maximizing the number of served requests. We show that the problem is NPhard and present a 2/3 approximation algorithm. We also show that a natural generalization of this algorithm has an approximation ratio at most 7/9.
“Greedy Is Good: An Empirical Evaluation of Three Algorithms for Online Bottleneck Matching,” with Christine Harbour and Jordan King, Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 108, pp. 1531, February 2019.
We empirically evaluate the performance of three approximation algorithms for the online bottleneck matching problem. In this matching problem, k serververtices lie in a metric space and k requestvertices that arrive over time each must immediately be permanently assigned to a serververtex. The goal is to minimize the maximum distance between any request and its assigned server. We consider the naive GREEDY algorithm, as well as PERMUTATION, and BALANCE, each of which were constructed to counter certain challenges in the online problem. We analyze the performance of each algorithm on a variety of data sets, considering each both in the original model, where applicable, and in the resource augmentation setting when an extra server is introduced at each serververtex. While no algorithm strictly dominates, GREEDY frequently performs the best, and thus is recommended due to its simplicity.
”Inefficiency of Equilibria in Doodle Polls”, with Christine Chung, In: Kim D., Uma R., Zelikovsky A. (eds) Combinatorial Optimization and Applications. COCOA 2018. Lecture Notes in Computer Science, vol 11346. Springer, 2018.
Doodle polls allow people to schedule meetings or events based on time preferences of participants. Each participant indicates on a webbased poll form which time slots they find acceptable and a time slot with the most votes is chosen. This is a social choice mechanism known as approval voting, in which a standard assumption is that all voters vote sincerely—no one votes “no” on a time slot they prefer to a time slot they have voted “yes” on. We take a gametheoretic approach to understanding what happens in Doodle polls assuming participants vote sincerely. First we characterize Doodle poll instances where sincere pure Nash Equilibria (NE) exist, both under lexicographic tiebreaking and randomized tiebreaking. We then study the quality of such NE voting profiles in Doodle polls, showing the price of anarchy and price of stability are both unbounded, even when a time slot that many participants vote yes for is selected. Finally, we find some reasonable conditions under which the quality of the NE (and strong NE) is good.
“Modernizing the Mythical ManMonth”, with Valentin Cantu, Jr., Journal of Computing Sciences in Colleges, Volume 34, Number 2, pp. 110116, December 2018.
The Mythical ManMonth: Essays on Software Engineering by Dr. Fred Brooks is often required reading in many software engineering classes and recommended by practitioners throughout industry as a text with which computer scientists should be familiar. Yet, while many of the conceptual ideas that were first presented decades ago are still applicable today, aspects of the presentation of the material are lacking in inclusivity, posing additional challenges for faculty who are trying to increase diversity within the discipline. Thus, we propose a studentdeveloped portrayal of some of the concepts in a modernized fashion, presented as a menu and incorporating ideas from the foodservice industry, a model that more college students are directly familiar with than the surgical team.
“How Bad is Selfish Doodle Voting?” [Extended Abstract], with C. Chung, Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018), Stockholm, Sweden, pp. 18561858, July 1015, 2018.
Doodle polls allow people to schedule meetings or events based on the time preferences of participants. Each participant indicates on a webbased poll form which time slots they find acceptable and a time slot with the most votes is chosen. This is a social choice mechanism known as approval voting, in which a standard assumption is that all voters vote sincerely: no one votes no on a time slot they prefer to a time slot they have voted yes on. We take a game theoretical approach to understanding what happens in Doodle polls assuming participants vote sincerely.
“Several questions which work for almost any computer science exam,” Journal of Computing Sciences in Colleges, Volume 33, Number 2, pp. 107112, December 2017.Many computer science courses use final exams as one means of evaluating student performance within the course, but developing meaningful assessments can be both difficult and timeconsuming. Students and faculty alike can experience both stress and frustration with various aspects of the exam process. By stepping back and evaluating the overall goals of computer science courses and the curriculum, some questions arise as viable options for final exams in a variety of computer science courses. These questions enable students to consider prior courses, projects or presentations within the course, future use of the material, or handle what may be perceived as incomplete coverage in the final exam. Some potential concerns about these questions are addressed. While these questions will not replace all of the traditional questions, they may provide different types of assessment information, and enable reflection for both students and faculty.
“CommunityEngaged Projects in Operations Research,” with Kathryn Reagan, Science Education & Civic Engagement: An International Journal, Volume 9, Issue 2, pp. 512, Summer 2017.
Communityengaged learning is not very common in technical fields, but including relevant projects in courses can make it feasible and successful. We present an implementation of an operations research course at a liberal arts college. Working with one of four nonprofit community partners to optimize aspects of their organization, students gained insight into relevant, realworld applications of the field of operations research. By considering many aspects of their solution when presenting it to community partners, students were exposed to some issues facing local nonprofit organizations. We discuss the specific implementation of this course, including both positive learning outcomes and challenging factors.
“A First Year Seminar’s Impact on Interest in Computer Science,” Journal of Computing Sciences in Colleges, Volume 32, Number 2, pp. 8389, December 2016.While enrollments in computer science courses may be increasing overall, the recruitment and retention of women and minorities in computer science remains a pervasive problem. First Year Seminars at universities are relatively common, and though they take on a variety of formats, many are designed to help with the transition to college and to increase retention. For three years, a computer science faculty member taught a First Year Seminar, broadly about the Internet, though with limited technical details, surveying the students about their perceptions of computer science. The results, while not conclusive, may provide motivation for other computer science professors to teach a First Year Seminar related to technology.
“How Well Do Doodle Polls Do?,” with Danya Alrawi and Christine Chung, Proceedings of the 8th International Conference on Social Informatics (SocInfo16), LNCS 10046, Volume 1, pp. 323, November 2016.
Webbased Doodle polls, where respondents indicate their availability for a collection of times provided by the poll initiator, are an increasingly common way of selecting a time for an event or meeting. Yet group dynamics can markedly influence an individual’s response, and thus the overall solution quality. Via theoretical worstcase analysis, we analyze certain common behaviors of Doodle poll respondents, including when participants are either more generous with or more protective of their time, showing that deviating from one’s “true availability” can have a substantial impact on the overall quality of the selected time. We show perhaps counterintuitively that being more generous with your time can lead to inferior time slots being selected, and being more protective of your time can lead to superior time slots being selected. We also bound the improvement and degradation of outcome quality under both types of behaviors.
“Serve or Skip: The Power of Rejection for Online Bottleneck Matching,” with Christine Chung, Journal of Combinatorial Optimization, Volume 32, Issue 4, pp. 12321253, November 2016.
We consider the online matching problem, where n serververtices lie in a metric space and n requestvertices that arrive over time each must immediately be permanently assigned to a serververtex. We focus on the egalitarian bottleneck objective, where the goal is to minimize the maximum distance between any request and its server. It has been shown that while there are effective algorithms for the utilitarian objective (minimizing total cost) in the resource augmentation setting where the offline adversary has half the resources, these are not effective for the egalitarian objective. Thus, we propose a new ServeorSkip (SoS) bicriteria analysis model, where the online algorithm may reject or skip up to a specified number of requests, and propose two greedy algorithms: GriNN(t) and GRIN_(t) . We show that the SoS model of resource augmentation analysis can essentially simulate the doubledservercapacity model, and then examine the performance of GriNN(t) and GRIN_(t).
“Complete rpartite graphs determined by their domination polynomial,” with Michael Picollelli, Graphs and Combinatorics, Volume 31, Issue 6, pp. 19932002, November 2015.
The domination polynomial of a graph is the polynomial whose coefficients count the number of dominating sets of each cardinality. A recent question asks which graphs are uniquely determined (up to isomorphism) by their domination polynomial. In this paper, we completely describe the complete rpartite graphs which are; in the bipartite case, this settles in the affirmative a conjecture of Aalipour et al. (Ars Comb, 2014).
“Conditions for the Bicolorability of Primitive Hypergraphs,” with Richard Denman, Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 94, pp. 2741, August 2015.
A primitive hypergraph is a hypergraph with maximum cardinality three and maximum degree three such that every 3edge is adjacent only to 2edges and is incident only to vertices of degree two. Deciding the bicolorability of a primitive hypergraph is NPcomplete (a straightforward consequence of results in Kratochvil and Tuza). We provide sufficient conditions, similar to the Sterboul conditions proved by Defossez, for the existence of a bicoloring of a primitive hypergraph, and we provide a polynomial algorithm for bicoloring a primitive hypergraph if those conditions hold. We then draw a connection between this algorithm and the wellknown necessary and sufficient conditions given by Berge for maximal matchings in graphs, which leads to a characterization of bicolorability of primitive hypergraphs.
“The Power of Rejection in Online Bottleneck Matching,” with Christine Chung, Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA’14), LNCS, pp. 395411, December 2014.
We consider the online matching problem, where n serververtices lie in a metric space and n requestvertices that arrive over time each must immediately be permanently assigned to a serververtex. We focus on the egalitarian bottleneck objective, where the goal is to minimize the maximum distance between and request and its server. It has been demonstrated that while there are effective algorithms for the utilitarian objective (minimizing total cost) in the resource augmentation setting where the offline adversary has half the resources, these are not effective for the egalitarian objective. Thus, we propose a new ServeorSkip bicriteria analysis model, where the online algorithm may reject or skip up to a specified number of requests, and propose two greedy algorithms: GriNN(t) and Grin*(t). We show that the ServeorSkip model of resource augmentation analysis can simulate the doubledserver capacity model, and then characterize the performance of GriNN(T) and Grin*(t).
“Offering an Undergraduate Computer Science Colloquium,” Journal of Computing Sciences in Colleges, Volume 29, Number 4, pp. 612, April 2014.
An undergraduate computer science colloquium is presented that can enhance the educational opportunities for students at a small liberal arts college while providing an additional communitybuilding venue for majors at various stages of their college careers. Presentation skills are a key component of this onecredit course, and the pass/fail grading system can alleviate some student concerns about their performance and allow them to focus on improving in this critical area. Additionally, though the number of electives offered at a small college may be small, a colloquium provides the means for exposure to a greater breadth of computer science topics, potentially helping students develop new interests within the discipline. After being piloted as a special topics course in Spring 2011, Southwestern University has now added the undergraduate colloquium to the regular spring course offerings.
“Online Bottleneck Matching,” with Christine Chung, Journal of Combinatorial Optimization, Volume 27, Issue 1, pp. 100114, January 2014. An earlier version appeared in Proceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA’12), LNCS 7402, pp. 257268, August 2012.
We consider the online bottleneck matching problem, where k serververtices lie in a metric space and k requestvertices that arrive over time each must immediately be permanently assigned to a serververtex. 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 serververtex has one server) to linear (when each serververtex has two servers), the competitive ratio of Permutation remains linear. The competitive ratio of Balance is also linear with an extra server at each serververtex, even though it has been shown that an extra server makes it constantcompetitive for the minweight matching problem.
“Data Plan Throttling: A Simple Consumer Choice Mechanism,” with Christine Chung, Proceedings of the IEEE Global Communications Conference (GLOBECOM 2013), pp. 31733178, December 2013.
Despite only a small portion of unlimited data plan users experiencing throttling each month, it is a prominent source of complaints from users and a significant concern for mobile network operators. We propose a simple mechanism that allows users to choose when they want their data transmission “fast,” and when they want it “slow.” Users still have the same cap on total highspeed transfer before being throttled, and hence may still be subject to throttling, but now they are given some control. We propose a basic model of payoffs, and demonstrate that the proposed mechanism would be preferable to the user over the throttling policies currently in place. We then consider the impacts that extend beyond a single user, and provide a framework for determining the aggregate effects of such a mechanism.
“Operations research: Broadening computer science in a liberal arts college,” Proceedings of the 43rd ACM Technical Symposium on Computer Science Education (SIGCSE ’12), pp. 463468, 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 upperlevel elective, and it was also crosslisted 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 filledtocapacity upperlevel 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 nonmajor 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. 245260, 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 straightline inputs, fewer are available for handling curved inputs, even in 2D. Many are based on the wellknown 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 applicationspecific. 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 preprocessing steps in the spirit of Pav and Walkington and a generalized midpoint calculation.
Feel free to email me for a copy. The code is freely available under the MIT License at http://code.google.com/p/reuleaux/
“A Plant Location Guide for the Unsure: Approximation Algorithms for MinMax Location Problems” with Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan, Mathematics of Operations Research, Vol. 35, No. 1, pp. 79101, February 2010.
This paper studies an extension of the kmedian problem under uncertain demand. We are given an nvertex 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 worstcase connection cost over all the client sets is minimized, i.e., \min_{F \subseteq V, PIPE F PIPE = 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 “minmax” or “robust” version of the kmedian problem. Note that in contrast to the recent papers on robust and stochastic problems, we have only one stage of decisionmaking where we select a set of k facilities to open. Once a set of open facilities is fixed, each client in the uncertain clientset connects to the closest open facility. We present a simple, combinatorial O(log n + log m)approximation algorithm for the robust kmedian problem that is based on reweighting/Lagrangeanrelaxation ideas. In fact, we give a general framework for (minimization) kfacility 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 ktree, capacitated kmedian, and faulttolerant kmedian.
“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 ACMSIAM Symposium on Discrete Algorithms (SODA), 2008.
Consider a minmax version of the kmedian 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 reversegreedy algorithm for the minmax version of the problem. Using this, we give algorithms for faulttolerant and capacitated versions of kmedian, as well as the ktree problem. Finally, we show that stochastic versions of kcenter are as hard as denseksubgraph.
“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.
In the News
Eight Southwestern Faculty Members Awarded Prestigious Grants from the 2019 Sam Taylor Fellowship Fund
The competitive funding will allow SU faculty to pursue various research projects.