Abstract We study a variant of the offline Dial-a-Ride problem, where each request has a source and destination and the goal is to maximize the number of requests served within a specified time limit. We investigate this problem for the uniform metric space and show that the problem is NP-hard. We then present a 2/3 approximation algorithm called $$\textsc {twochain}$$ T W O C H A I N , which simply looks for pairs of requests that are “chained” together and serves those before serving requests that are not connected to any others. We also show that a natural generalization of this algorithm, k-chain, has an approximation ratio at most 7/9. We also analyze the longest-chain-first algorithm for the problem, characterizing graphs on which it is optimal, and showing that it has an approximation ratio no better than 5/6. Our experiments on all of these algorithms show that $$\textsc {twochain}$$ T W O C H A I N is a promising algorithm, performing nearly as well as more computationally intensive variants. We dedicate this article to the memory of Gerhard Woeginger, whose life and work greatly influenced our professional lives, as expanded upon in the Acknowledgments. Woeginger’s prolific research in scheduling, matching, bin-packing, TSP, and online algorithms in general, all served as important parts of the foundation on which our own scholarly pursuits were shaped and formed over the years. Woeginger also studied Dial-a-Ride (DARP) Problems, as DARP is a generalization both of scheduling problems and of TSP, which were two of his most active areas of research.

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.

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.

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.

Enrollments in CS have been climbing dramatically in recent years at large schools, especially those in the top-tier for CS. This type of growth is part of the normal cycle for CS and is expected anytime that the public perceives that the job market for computing related fields is strong. It is unclear how much of this growth is currently seen on other campuses. The purpose of this BoF session is to discuss what educators at smaller campuses, and particularly liberal arts schools, are currently seeing in regards to enrollment in CS. This information could be of particular interest for those at schools considering cutting programs for economic reasons or those adjusting the number of faculty lines.

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.

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 |rj, pmtn| Σj cj. 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].