Ride sharing is a sustainable, environmentallyfriendly mode of commute that is gaining in popularity. Though there are well-established commercial service providers, there are not many platforms for facilitating peer-to-peer ride sharing, especially in a dynamic scenario, integrated with multi-modal trip planners. Such systems would need to be highly searchoptimized for retrieval of multiple potential ride matches in real time, especially because multi-modal trip planners have a high look-to-book ratio. At the same time, validity of the matches need to be ensured, even in a dynamic setting, while addressing quality considerations and constraints such as maximum detour incurred by rides, walking distance for commuters, and time windows of requests. We describe Xhare-a-Ride (XAR) system, a platform for dynamic peer-to-peer ride sharing, that is scalable, efficient, and highly search-optimized for retrieving multiple potential matches for every ride request, while handling quality considerations. We propose a hierarchical discretization of the geographical region using grids, landmarks and clusters with theoretical guarantees, along with an efficient in-memory indexing of rides for maintaining spatio-temporal validity within a specified error tolerance. This helps eliminate shortest path computation in realtime during search, thus making XAR search-optimized, hence, suitable for integration with a multi-modal trip planner. We discuss modes of integrating XAR with such a trip planner for building an integrated system. Finally, we evaluate XAR thoroughly on ride share request data generated from the NY taxi trip data set on three fronts: (i) empirical performance against the theoretical guarantees as well as trade-off of performance with system parameters, (ii) benchmark XAR against a state-of the-art ride share system, showing a significant improvement in the search efficiency, and finally, (iii) the efficacy of combining ride sharing with public transportation.

Nowadays, brick-and-mortar stores are finding it extremely difficult to retain their customers due to the ever increasing competition from the online stores. One of the key reasons for this is the lack of personalized shopping experience offered by the brick-and-mortar stores. This work considers the problem of persona based shopping recommendation for such stores to maximize the value for money of the shoppers. For this problem, it proposes a non-polynomial time-complexity optimal dynamic program and a polynomial time-complexity non-optimal heuristic, for making top-k recommendations by taking into account shopper persona and her time and budget constraints. In our empirical evaluations with a mix of real-world data and simulated data, the performance of the heuristic in terms of the persona based recommendations (quantified by similarity scores and items recommended) closely matched (differed by only 8% each with) that of the dynamic program and at the same time heuristic ran at least twice faster compared to the dynamic program.

Group buying offers products at significantly reduced prices on the condition that a pre-specified number of buyers would make the purchase. Given the ever-increasing popularity of mobile devices and applications coupled with the typically high price-sensitivity of a significant percentage of users, group buying in mobile environments has the potential to attain dramatically increasing popularity. However, existing solutions for group buying typically involve web-based portals, which are not capable of handling user mobility. Hence, this work proposes an end-to-end mobile group-buying system that can be used for targeted decentralized advertisement and discovery of group buying deals, and group formation to avail a deal. The key contributions are three-fold. First, it proposes an ILP (Integer Linear Programming)-based optimal algorithm for the problem of efficiently forming groups of buyers with the objective of maximizing the overall utility of the solution. Second, it proposes a greedy algorithm for the same problem since solving ILP can take significant time for some problem instances. The greedy algorithm takes an input parameter, which can be tweaked to trade-off its optimality with its running time. Third, performance study shows that the proposed algorithms exhibit good performance in terms of the number of groups formed w.r.t. The requests in the system. Notably, the greedy algorithm provides near-optimal solution and runs significantly faster than the ILP-based optimal algorithm.

Many real-time systems include tasks that need to suspend their execution in order to externalize some of their operations or to wait for data, events or shared resources. Although commonly encountered in real-world systems, study of their timing analysis is still limited due to the problem complexity. In this paper, we invalidate a claim made in one of the earlier works [1], that led to the common belief that the timing analysis of one self-suspending task interacting with non-self suspending sporadic tasks is much easier than in the periodic case. This work highlights the complexity of the problem and presents a method to compute the exact worst-case response time (WCRT) of a self-suspending task with one suspension region. However, as the complexity of the analysis might rapidly grow with the number of tasks, we also define an optimization formulation to compute an upper-bound on the WCRT for tasks with multiple suspension regions. In the experiments, our optimization framework outperforms all previous analysis techniques and often finds the exact WCRT.

The prevalence of mobile devices and applications strongly motivate mobile crowdsourcing for facilitating location-dependent services. We propose LoRUS, a Location-based Relevant User determination System for efficiently retrieving the top-k relevant mobile users in a given spatial window.

We consider the problem of fair resource allocation for tasks where a resource can be assigned to at most one task, without any fractional allocation. The system is heterogeneous: capacity and cost may vary across resources, and different tasks may have different resource demand. Due to heterogeneity of resources, the cost of allocating a task in isolation, without any other competing task, may differ significantly from its allocation cost when the task is allocated along with other tasks. In this context, we consider the problem of allocating resource to tasks, while ensuring that the cost is distributed fairly across the tasks, namely, the ratio of allocation cost of a task to its isolation cost is minimized over all tasks. We show that this fair resource allocation problem is strongly NP-Hard even when the resources are of unit size by a reduction from 3-partition. Our central results are an LP rounding based algorithm with an approximation ratio of 2+ O(ϵ) for the problem when resources are of unit size, and a near-optimal greedy algorithm for a more restricted version. The above fair allocation problem arises for resource allocation in various context, such as, allocating computing resources for reservations requests from tenants in a data centre, allocating resources to computing tasks in grid computing, or allocating personnel for tasks in service delivery organizations.

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising a constant number (denoted by t ) of distinct types of processors—such a platform is referred to as a t-type platform . We present two algorithms, LPG IM and LPG NM , each providing the following guarantee. For a given t-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet their deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then : (i) LPG IM succeeds in finding such an assignment where the same restriction on task migration applies (intra-migrative) but given a platform in which only one processor of each type is 1 + α × t -1/ t times faster and (ii) LPG NM succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which every processor is 1 + α times faster. The parameter α is a property of the task set; it is the maximum of all the task utilizations that are no greater than one. To the best of our knowledge, for t-type heterogeneous multiprocessors: (i) for the problem of intra-migrative task assignment, no previous algorithm exists with a proven bound and hence our algorithm, LPG IM , is the first of its kind and (ii) for the problem of non-migrative task assignment, our algorithm, LPG NM , has superior performance compared to state-of-the-art.

Consider the problem of assigning implicit deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors - such a platform is referred to as two-type platform. We present two line arithmic time-complexity algorithms, SA and SA-P, each providing the following guarantee. For a given two-type platform and a given task set, if there exists a feasible task to-processor-type assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type, then (i) using SA, it is guaranteed to find such a feasible task-to-processor-type assignment where the same restriction on task migration applies but given a platform in which processors are 1 + α/2 times faster and (ii) SA-P succeeds in finding a feasible task-to-processor assignment where tasks are not allowed to migrate between processors but given a platform in which processors are 1 + α times faster, where 0 <; α ≤ 1. The parameter is a property of the task set α it is the maximum utilization of any task which is less than or equal to 1.

Consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct kinds of processors. We propose a polynomial-time approximation scheme (PTAS) for this problem. It offers the following guarantee: for a given task set and a given platform, if there exists a feasible task-to-processor assignment, then given an input parameter, ϵ, our PTAS succeeds, in polynomial time, in finding such a feasible task-to-processor assignment on a platform in which each processor is 1+3ϵ times faster. In the simulations, our PTAS outperforms the state-of-the-art PTAS and also for the vast majority of task sets, it requires significantly smaller processor speedup than (its upper bound of) 1+3ϵ for successfully determining a feasible task-to-processor assignment.

Consider the problem of scheduling a set of implicit deadline sporadic tasks on a heterogeneous multiprocessor platform to meet all deadlines. Tasks cannot migrate and each processor is either of type-1 or type-2 (with each task having different execution speed on each processor type). We present a new algorithm, FF-3C, for this problem. FF-3C offers low time-complexity and provably good performance. Specifically, (i) its time-complexity is O(n*max(m,log n)), where n is the number of tasks and m is the number of processors and (ii) it offers the guarantee that if a task set can be scheduled by an optimal task assignment scheme to meet deadlines then FF-3C meets deadlines as well if given processors twice as fast. We also present several extensions to FF-3C, these offer the same time-complexity and performance guarantee as that of FF-3C but in addition, they offer improved average-case performance. Via experiments with randomly generated task sets, we compare the performance of our new algorithms and two established state-of-art algorithms (and variations of the latter). We evaluate algorithms based on (i) running time and (ii) the necessary multiplication factor, i.e., the amount of extra speed of processors the algorithm needs, for a given task set, so as to succeed, compared to an optimal task assignment scheme. Overall our new algorithms compare favorably to the state-of-art. One in particular (FF-4C-COMB), in our experimental evaluations, runs 12000 to 160000 times faster and has significantly smaller necessary multiplication factor than state-of-art algorithms.

Automakers are trying to make vehicles more intelligent and safe by embedding processors which can be used to implement ldquoby-wirerdquo applications for taking smart decisions on the road or assisting the driver in doing the same. Given this proliferation, there is a need to minimize the computing power required without affecting the performance and safety of the applications. The latter is especially important since these by-wire applications are distributed and real-time in nature and involve deadline bound computations on critical data gathered from the environment. These applications have stringent requirements on the freshness of data items and completion time of the tasks. Our work studies one such safety-related automotive application namely, automatic merge control (AMC) which ensures safe vehicle maneuver in the region where two or more roads intersect.As our contributions, we (i) propose two merge algorithms for amc: head of the lane (HoL) and all feasible sequences (AFS) (ii) demonstrate how DSRC-based wireless communication protocol can be leveraged for the development of AMC (iii) present a real-time approach towards designing AMC by integrating mode-change and real-time repository concepts for reducing the processing power requirements and (iv) provide a scheduling strategy to meet AMC taskspsila timing requirements. Simulations and implementation on robotic vehicular platforms demonstrate the advantages of using our approach for constructing merge-by-wire systems.