Christine Chung's Publications

*Serving Rides of Equal Importance for Time-Limited
Dial-a-Ride*, with Barbara M Anthony, Ananya D Christman, and David
Yuen*. *MOTOR 2021 (*20 ^{th }International Conference on
Mathematical Optimization Theory and Operations Research*). LNCS, vol 12755: 35-50.
Springer 2021.

We
consider a variant of the offline Dial-a-Ride 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 polynomial-time 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. We also show that the
approximation ratio for a reasonable class of algorithms for this problem is
unbounded, unless the graph diameter is bounded. We then show that the
segmented best path (SBP) algorithm is a 4-approximation. We then present an
algorithm, *k*-Sequence, that
repeatedly serves the fastest set of *k*
remaining requests, and provide upper and lower bounds on its performance.

*Improved
Bounds for Revenue Maximization in Time-Limited Online Dial-a-Ride, *with A.D. Christman*, *N. Jaczko, T. Li, S. Westvold, X. Xu, D. Yuen.* Springer Nature Operations
Research Forum, 2(39), July 2021. *

In
the Online Dial-a-Ride Problem (OLDARP), a server travels to serve requests for
rides. We consider a variant where each request specifies a source,
destination, release time, and revenue that is earned for serving the request.
The goal is to maximize the total revenue earned within a given time limit. We
first prove that no non-preemptive deterministic online algorithm can be
guaranteed to earn more than half the revenue earned by OPT. We then
investigate the SEGMENTED BEST PATH (SBP) algorithm, for which the previously
established bounds on competitive ratio were 4 and 6, under reasonable
assumptions about the input instance. We eliminate the gap by proving that the
competitive ratio is 5 (under the same assumptions) and also prove that this
bound is tight. When revenues are uniform, we prove that SBP has competitive
ratio 4. Next we provide a competitive analysis of SBP on complete bipartite
graphs. We conclude with experimental results that suggest that SBP would be
effective if applied in practice.

*Equilibria in
Doodle Polls Under Three Tie-breaking Rules*, with Barbara M Anthony. *Theoretical
Computer Science*, Volume 822, 2020, Pages 61-71.

Doodle polls allow people to schedule meetings or events based on
time preferences of participants. Each participant indicates on a web-based
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-theoretic 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 tie-breaking, random
candidate, and random voter tie-breaking. 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.

*New Bounds for Maximizing Revenue in Online
Dial-a-Ride*, with Ananya Christman, Nicholas
Jaczko, Tianzhi
Li, Scott Westvold, and Xinyue
Xu, and David Yuen. IWOCA 2020 (*31 ^{st} International Workshop on
Combinatorial Algorithms*). LNCS, vol 12126. Springer,
2020.

In the Online-Dial-a-Ride Problem (OLDARP) a server travels
through a metric space to serve requests for rides. We consider a variant where each request
specifies a source, destination, release time, and revenue that is earned for
serving the request. The goal is to maximize the total revenue earned within a
given time limit. We prove that no non-preemptive deterministic online
algorithm for OLDARP can be guaranteed to earn more than twice the revenue
earned by an optimal offline solution. We then investigate the Segmented Best
Path (

*Maximizing
the Number of Rides Served for Dial-a-Ride*, with Barbara M Anthony,
Ricky Birnbaum, Sara Boyd, Ananya Christman,
Patrick Davis, Jigar Dhimar,
and David Yuen. ATMOS
2019 (*Symposium on Algorithmic Approaches for
Transportation Modelling, Optimization, and Systems*).

We study a variation of offline Dial-a-Ride, 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 NP-hard 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.

*Robustly
Assigning Unstable Items*, with Ananya Das Christman,
Nicholas Jaczko, Scott Westvold,
and David Yuen. *Journal of Combinatorial Optimization, *January
2020. Earlier version appeared in COCOA 2018 (12^{th}
*Annual International Conference on
Combinatorial Optimization and Applications*). LNCS, vol 11346.
Springer, 2018.

We study the
Robust Assignment Problem where the goal is to assign items of various types to
containers without exceeding container capacity. We seek an assignment that
uses the fewest number of containers and is robust, that is, if any item
becomes corrupt causing all containers with that type of item to become
unstable, every other item type is still assigned to a stable container. We
begin by presenting an optimal polynomial time algorithm that finds a robust
assignment using the minimum number of containers for the case when the
containers have infinite capacity. Then we consider the case where all
containers have some fixed capacity and give an optimal polynomial-time
algorithm for the special case where each type of item has the same size. When
the sizes of the item types are non-uniform, we provide a polynomial-time
2-approximation for the problem. We also prove that the approximation ratio of
our algorithm is no lower than 1.813.

*Inefficiency of
Equilibria in Doodle Polls*, with Barbara Anthony. COCOA
2018 (12^{th} *Annual
International Conference on Combinatorial Optimization and Applications*). LNCS, vol 11346.
Springer, 2018.

Doodle polls allow people to schedule meetings or events based on
time preferences of participants. Each participant indicates on a web-based
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-theoretic 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 tie-breaking and randomized
tie-breaking. 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.

*How Bad is Selfish Doodle
Voting?*, with Barbara Anthony. Extended
Abstract in AAMAS 2018
(Proceedings of the 17th *International
Conference on Autonomous Agents and Multiagent
Systems*, Stockholm, Sweden, pp. 1856-1858, July 10-15, 2018.

*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 8^{th}
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 20^{th}
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.