Christine Chung's Publications
For a more dependably up-to-date list of my publications, please
see DBLP or Google
scholar.
Serving Rides of Equal Importance for
Time-Limited Dial-a-Ride, with
Barbara M Anthony, Ananya D Christman, and David Yuen. MOTOR 2021 (20th 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 (31st 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 (12th 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 (12th 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 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.