Christine Chung's Publications

Revenue Maximization in Online Dial a Ride, with Ananya Christman, Nicholas Jaczko, Marina Milan, Anna Vasilchenko, and Scott Westvold.  ATMOS 2017 (17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems).

We study a variation of the Online-Dial-a-Ride Problem where each request comes with not only a source, destination and release time, but also has an associated revenue. The server’s goal is to maximize its total revenue within a given time limit, T. We show that the competitive ratio is unbounded for any deterministic online algorithm for the problem. We then provide a 3-competitive algorithm for the problem in a uniform metric space and a 6-competitive algorithm for the general case of weighted graphs (under reasonable assumptions about the input instance). We conclude with an experimental evaluation of our algorithm in simulated settings inspired by real-world Dial-a-Ride data. Experimental results show that our algorithm performs well when compared to an offline version of the algorithm and a greedy algorithm.

How well do Doodle polls do?, with Danya Alrawi ’16 (undergraduate research student) and Barbara Anthony.  SocInfo 2016 (8th International Conference on Social Informatics).

Web-based 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 worst-case 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. 

Serve or skip: the power of rejection in online bottleneck matching, with Barbara Anthony.  Journal of Combinatorial Optimization, 32(4), 1232-1253, November 2016.  Earlier version appeared in COCOA 2014 (The 8th Annual International Conference on Combinatorial Optimization and Applications).

We consider the online matching problem, where n server-vertices lie in a metric space and n request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. 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 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 Serve-or-Skip 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).  

Fairness in employee scheduling, with Erica Stockwell-Alpert ‘14 (undergraduate research student).  MISTA 2015 (Multidisciplinary International Conference on Scheduling Theory and Applications).

 

We consider the problem of assigning shifts to employees such that (1) all shift coverage requirements are satisfied, (2) employees are available to work all shifts they are assigned, (3) the number of total hours available for distribution is not exceeded, and (4) each employee is assigned the number of hours they need. Our focus in this work is on employee satisfaction (the percentage of their desired hours an employee is assigned) and fairness (the employee satisfaction level should be as uniform as possible). Because the problem is NP-hard, we propose an approximation algorithm for maximizing the minimum employee satisfaction.

Competitive cost-savings in data stream management systems, with Shenoda Guirguis and Anastasia Kurdia.  COCOON 2014 (The 20th International Computing and Combinatorics Conference).

In Continuous Data Analytics and in monitoring applications, hundreds of similar Aggregate Continuous Queries (ACQs) are registered at the Data Stream Management System (DSMS) to continuously monitor the infinite input stream of data tuples. Optimizing the processing of these ACQs is crucial in order for the DSMS to operate at the adequate required scalability. One optimization technique is to share the results of partial aggregation operations between different ACQs on the same data stream. However, finding the query execution plan that attains maximum reduction in total plan cost is computationally expensive.  Weave Share, a multiple ACQs optimizer that computes query plans in a greedy fashion, was recently shown in experiments to achieve more than an order of magnitude improvement over the best existing alternatives.  In this paper we prove that Weave Share approximates the optimal cost-savings to within a factor of 4 for a practical variant of the problem.

Online bottleneck matching, with Barbara Anthony.  Journal of Combinatorial Optimization, Volume 27, Issue 1, pp. 100-114, January 2014.  (Published online: Feb 2013.  Earlier version appeared in COCOA 2012.)

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

Data plan throttling: a simple consumer choice mechanism, with Barbara Anthony.  Proceedings of the IEEE Global Communications Conference (GLOBECOM 2013), pp. 3173-3178, 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 high-speed 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.

Auction-based admission control for continuous queries in a multi-tenant DSMS, with Lory Al Moakar, Panos Chrysanthis, Shenoda Guirguis, Alexandros Labrinidis, Panayiotis Neophytou, and Kirk Pruhs.  International Journal of Next-Generation Computing, Vol 3, No 3, November 2012. 

The growing popularity of monitoring applications and “Big Data” analytics used by a variety of users will lead to a multi-tenant data stream management system. This paper deals with the problem of admission control of continuous queries, where the stream processing resources are sold to the end users. We employ variable pricing by means of auction-based mechanisms. The admission control auction mechanism determines which queries to admit, and how much to charge the user for each query in a way that maximizes system revenue. The admission mechanism is required to be strategyproof and sybil-immune, incentivizing users to use the system honestly. Specifically, we require that each user maximizes her payoff by bidding her true value of having a query run. We further consider the requirement that the mechanism be sybil-immune: that is, no user can increase her payoff by submitting queries that she does not value. Given the above requirements, the main challenges come from the difficulty of effectively utilizing shared processing of continuous queries. We design several payment mechanisms and experimentally evaluate them.

Completion time scheduling and the WSRPT algorithm, with Bo Xiong, ‘13 (undergraduate research student).  ISCO 2012 (International Symposium on Combinatorial Optimization).

We consider the online scheduling problem of minimizing the total weighted and unweighted completion time on identical parallel machines with preemptible jobs. We show a new general lower bound of 21/19 ≈ 1.105 on the competitive ratio of any deterministic online algorithm for the unweighted problem and 16−14√11≈1.114 for the weighted problem. We then analyze the performance of the natural online algorithm WSRPT (Weighted Shortest Remaining Processing Time). We show that WSRPT is 2-competitive. We also prove that the lower bound on the competitive ratio of WSRPT for this problem is 1.215.

The power of fair pricing mechanisms, with Katrina Ligett, Aaron Roth, and Kirk Pruhs.  Algorithmica, Volume 63, Issue 3, pp. 634-644, July 2012.  (Published online: Nov 2011.  Earlier version appeared in LATIN 2010.)

We explore the revenue capabilities of truthful, monotone (“fair”) allocation and pricing functions for resource-constrained auction mechanisms within a general framework that encompasses unlimited supply auctions, knapsack auctions, and auctions with general non-decreasing convex production cost functions. We study and compare the revenue obtainable in each fair pricing scheme to the profit obtained by the ideal omniscient multi-price auction. We show that for capacitated knapsack auctions, no constant pricing scheme can achieve any approximation to the optimal profit, but proportional pricing is as powerful as general monotone pricing. In addition, for auction settings with arbitrary bounded non-decreasing convex production cost functions, we present a proportional pricing mechanism which achieves a poly-logarithmic approximation. Unlike existing approaches, all of our mechanisms have fair (monotone) prices, and all of our competitive analysis is with respect to the optimal profit extraction.

Expanding CS1: applications across the liberal arts, with Bridget Baird.  Journal of Computing Sciences in Colleges, 25(6), 47-54.  (CCSCNE 2010) [Local copy]

This paper describes how applications in a variety of disciplines can enhance the teaching of the CS1 course. Examples are given from a range of disciplines, including mathematics, economics, linguistics, history, biology, art and music. The applications are linked to the computer science concepts being discussed. Such an approach broadens the appeal of the introductory course and also teaches students valuable problem solving skills.

SRPT is 1.86-competitive for completion time scheduling, with Tim Nonner and Alex Souza.  SODA 2010 (ACM-SIAM Symposium on Discrete Algorithms).

We consider the classical problem of scheduling preemptible jobs, that arrive over time, on identical parallel machines. The goal is to minimize the total completion time of the jobs. In standard scheduling notation of Graham et al. [5], this problem is denoted P|r_j, pmtn|Σ_j c_j. A popular algorithm called SRPT, which always schedules the unfinished jobs with shortest remaining processing time, is known to be 2-competitive, see Phillips et al. [13, 14]. This is also the best known competitive ratio for any online algorithm. However, it is conjectured that the competitive ratio of SRPT is significantly less than 2. Even breaking the barrier of 2 is considered a significant step towards the final answer of this classical online problem. We improve on this open problem by showing that SRPT is 1.86-competitive. This result is obtained using the following method, which might be of general interest: We define two dependent random variables that sum up to the difference between the cost of an SRPT schedule and the cost of an optimal schedule. Then we bound the sum of the expected values of these random variables with respect to the cost of the optimal schedule, yielding the claimed competitiveness. Furthermore, we show a lower bound of 21/19 for SRPT, improving on the previously best known 12/11 due to Lu et al. [11].

Admission control mechanisms for continuous queries in the cloud, with Lory Al Moakar, Panos Chrysanthis, Shenoda Guirguis, Alexandros Labrinidis, Panayiotis Neophytou, and Kirk Pruhs.  ICDE 2010 (IEEE International Conference on Data Engineering).

Amazon, Google, and IBM now sell cloud computing services. We consider the setting of a for-profit business selling data stream monitoring/management services and we investigate auction-based mechanisms for admission control of continuous queries. When submitting a query, each user also submits a bid of how much she is willing to pay for that query to run. The admission control auction mechanism then determines which queries to admit, and how much to charge each user in a way that maximizes system revenue while being strategyproof and sybil immune, incentivizing users to use the system honestly. Specifically, we require that each user maximizes her payoff by bidding her true value of having her query run. We design several payment mechanisms and experimentally evaluate them. We describe the provable game theoretic characteristics of each mechanism alongside its performance with respect to maximizing profit and total user payoff.

On the price of stability for undirected network design, with Giorgos Christodoulou, Katrina Ligett, Evangelia Pyrga, and Rob van Stee.  WAOA 2009 (Workshop on Approximation and Online Algorithms).

We continue the study of the effects of selfish behavior in the network design problem. We provide new bounds for the price of stability for network design with fair cost allocation for undirected graphs. We consider the most general case, for which the best known upper bound is the Harmonic number H_n , where n is the number of agents, and the best previously known lower bound is 12/7 ≈ 1.778.  We present a nontrivial lower bound of 42/23 ≈ 1.8261. Furthermore, we show that for two players, the price of stability is exactly 4/3, while for three players it is at least 74/48 ≈ 1.542 and at most 1.65. These are the first improvements on the bound of H_n for general networks. In particular, this demonstrates a separation between the price of stability on undirected graphs and that on directed graphs, where H_n is tight. Previously, such a gap was only known for the cases where all players have a shared source, and for weighted players.

Stochastic stability in internet router congestion games, with Evangelia Pyrga.  SAGT 2009 (Symposium on Algorithmic Game Theory).  For a more complete version of this work, see the relevant chapter of my PhD thesis.

Congestion control at bottleneck routers on the internet is a long standing problem. Many policies have been proposed for effective ways to drop packets from the queues of these routers so that network endpoints will be inclined to share router capacity fairly and minimize the overflow of packets trying to enter the queues. We study just how effective some of these queuing policies are when each network endpoint is a self-interested player with no information about the other players’ actions or preferences. By employing the adaptive learning model of evolutionary game theory, we study policies such as Droptail, RED, and the greedy-flow-punishing policy proposed by Gao et al. [10] to find the stochastically stable states: the states of the system that will be reached in the long run.

The price of stochastic anarchy, with Katrina Ligett, Kirk Pruhs and Aaron Roth.  SAGT 2008 (Symposium on Algorithmic Game Theory).

We consider the solution concept of stochastic stability, and propose the price of stochastic anarchy as an alternative to the price of (Nash) anarchy for quantifying the cost of selfishness and lack of coordination in games. As a solution concept, the Nash equilibrium has disadvantages that the set of stochastically stable states of a game avoid: unlike Nash equilibria, stochastically stable states are the result of natural dynamics of computationally bounded and decentralized agents, and are resilient to small perturbations from ideal play. The price of stochastic anarchy can be viewed as a smoothed analysis of the price of anarchy, distinguishing equilibria that are resilient to noise from those that are not. To illustrate the utility of stochastic stability, we study the load balancing game on unrelated machines. This game has an unboundedly large price of Nash anarchy even when restricted to two players and two machines. We show that in the two player case, the price of stochastic anarchy is 2, and that even in the general case, the price of stochastic anarchy is bounded. We conjecture that the price of stochastic anarchy is O(m), matching the price of strong Nash anarchy without requiring player coordination. We expect that stochastic stability will be useful in understanding the relative stability of Nash equilibria in other games where the worst equilibria seem to be inherently brittle.

The online transportation problem: on the exponential boost of one extra server, with Kirk Pruhs and Patchrawat Uthaisombut.  LATIN 2008 (Latin American Theoretical Informatics Symposium).

We present a poly-log-competitive deterministic online algorithm for the online transportation problem on hierarchically separated trees when the online algorithm has one extra server per site. Using metric embedding results in the literature, one can then obtain a poly-log-competitive randomized online algorithm for the online transportation on an arbitrary metric space when the online algorithm has one extra server per site.