Now, more than ever, there is a need for computer scientists and data scientists to be socially responsible about the algorithms they design and the products they build. We all have to conscientiously analyze the impact of our work, particularly on historically marginalized communities. As we look towards creating a more just future, this means we also need to provide our students appropriate training, so that we can all address existing social inequities and prevent further social inequities from creeping into our work. Data science1 provides an ideal opportunity to train students to identify existing bias and explore ways to address it. This special session equips educators with tools to bring about this training. The presenters will share their experiences in incorporating data science for social justice in their courses, introducing CS through a social justice lens, and interrogating the collection and use of data. Through moderated group discussions, this special session will collate ideas and strategies from the participants of their respective experiences. The presenters will create and share a repository of the collated ideas to enable a broad swath of educators to incorporate data science for social justice in their respective courses to train the future generation.

Cloud offloading is an indispensable solution to supporting computationally demanding applications on resource constrained mobile devices. In this paper, we introduce the concept of wireless aware joint scheduling and computation offloading (JSCO) for multi-component applications, where an optimal decision is made on which components need to be offloaded as well as the scheduling order of these components. The JSCO approach allows for more degrees of freedom in the solution by moving away from a compiler pre-determined scheduling order for the components towards a more wireless aware scheduling order. For some component dependency graph structures, the proposed algorithm can shorten execution times by parallel processing appropriate components in the mobile and cloud. We define a net utility that trades-off the energy saved by the mobile, subject to constraints on the communication delay, overall application execution time, and component precedence ordering. The linear optimization problem is solved using real data measurements obtained from running multi-component applications on an HTC smartphone and the Amazon EC2, using WiFi for cloud offloading. The performance is further analyzed using various component dependency graph topologies and sizes. Results show that the energy saved increases with longer application runtime deadline, higher wireless rates, and smaller offload data sizes.

The well documented growth in mobile traffic is mainly driven by increasingly sophisticated smart phone applications. Simultaneously, user preference for lighter phones has resulted in more battery power constrained hand-helds that offload computations to resource intensive cloud. This second trend exacerbates the bandwidth crunch often experienced over wireless networks. Our idea (joint cognitive offloading and scheduling) is to use dynamic spectrum access and management concepts from wireless networking to effect computation offloading and scheduling solutions that achieves near optimal trade-offs between the mobile device and wireless resources. We use all radio available interfaces (e.g. WiFi, LTE) in multi-RAT enabled devices to schedule appropriate components of the application to run either on the mobile device or on the resource-rich cloud, while staying adaptive to the conditions of the wireless network.

This paper investigates the problem of computing the optimal trajectories of multiple data MULEs (e.g., robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks. By relying on a slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood ( k-TSPN) and the k-rooted path cover problem with neighborhood ( k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them along with two simpler heuristic algorithms. We also conduct simulations to compare the performance of the proposed approaches with the existing alternatives. Our simulation results indicate that the proposed algorithms outperform the competitors on average.

In this paper we present a novel algorithm, Energy Efficient Weighted Load Balanced Routing (E-WLBR), to increase network lifetime for ad hoc wireless networks by applying weighted load-balancing strategies to the network. We show that E-WLBR significantly outperforms the Energy-opportunistic Weighted Minimum Energy Algorithm (E-WME) (an asymptotically optimal algorithm shown in [7] to outperform a host of other algorithms) in throughput and efficient network energy utilization by communicating global network conditions with minimal control message overhead.

This paper considers the problem of computing the optimal trajectories of multiple mobile elements (e.g. robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks (WSNs). By relying on slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood (k-TSPN) and the k-rooted path cover problem with neighborhood (k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them. Our simulation results indicate our algorithms outperform their alternatives.

Minimizing power consumption is crucial in battery power-limited secure wireless mobile networks. In this paper, we (a) introduce a hardware/software set-up to measure the battery power consumption of encryption algorithms through real-life experimentation, (b) based on the profiled data, propose mathematical models to capture the relationships between power consumption and security, and (c) formulate and solve security maximization subject to power constraints. Numerical results are presented to illustrate the gains that can be achieved in using solutions of the proposed security maximization problems subject to power constraints.

Recently there has been much progress on the design of approximation algorithms for a variety of scheduling problems in which the goal is to minimize the average weighted completion time of the jobs scheduled. Many of these approximation algorithms have been inspired by polyhedral formulations of the scheduling problems and their use in computing optimal solutions to small instances. In this paper we demonstrate that the progress in the design and analysis of approximation algorithms for these problems also yields techniques with improved computational efficacy. Specifically, we give a comprehensive experimental study of a number of these approximation algorithms for 1|rj∑wjCj, the problem of scheduling jobs with release dates on one machine so as to minimize the average weighted completion time of the jobs scheduled. We study both the quality of lower bounds given for this problem by different linear-programming relaxations and combinatorial relaxations, and the quality of upper bounds delivered by a number of approximation algorithms based on them. The best algorithms, on almost all instances, come within a few percent of the optimal average weighted completion time. Furthermore, we show that this can usually be achieved with O(n log n) computation. In addition we observe that on most kinds of synthetic data used in experimental studies a simple greedy heuristic, used in successful combinatorial branch-and-bound algorithms for the problem, outperforms (on average) all of the LP-based heuristics. We identify, however, other classes of problems on which the LP-based heuristics are superior and report on experiments that give a qualitative sense of the range of dominance of each. We consider the impact of local improvement on the solutions as well. We also consider the performance of the algorithms for the average weighted flow-time criterion, which, although equivalent to average weighted completion time at optimality, is provably much harder to approximate. Nonetheless, we demonstrate that for most instances we consider that the algorithms give very good results for this criterion as well. Finally, we extend the techniques to a rather different and more complex problem that arises from an actual manufacturing application: resource-constrained project scheduling. In this setting as well, the techniques yield algorithms with improved performance; we give the best-known solutions for a set of instances provided by BASF AG, Germany.

In this paper, we analyze the performance of on-line image transmission algorithms designed to minimize wastage of battery energy and bandwidth over bursty wireless channels. These algorithms estimate the wireless channel state in an online fashion and adapt accordingly. Theoretical basis for these algorithms are presented using competitive analysis. Computational and transmission energy consumption factors are taken into account. Experimental results show that some of the proposed algorithms can result in significant performance improvement.

Delivering multimedia content over the network pose several challenges that include higher bandwidth and sensitivity to packet losses resulting due to congestion and/or transmission errors. Multiple description coding (MDC) is one of the source coding approaches to alleviate the problems of packet loss in a network since MDC splits the source information into several descriptions which can then be transmitted over several paths in the network. Parallel delivery of descriptions over multiple paths should guarantee better quality of transmission. In this paper we investigate the performance of a generalized MDC scheme over multi-path and single path scenarios and compare its performance to a layered single description (SDC) scheme. In the multi-path case, multimedia content is delivered via k-shortest paths that are selected on the basis of the packet loss probability of overall links in that path. Our experimental results show that MDC scheme always outperforms the SDC scheme in terms of PSNR quality for both single and multi-path transmissions. The improvement varies from 7 dB at (5% packet loss) to 13 dB at (20% packet loss) for the single path and by 3 dB to 9 dB respectively for the multi-path transmission.

In this paper we consider the problem of planning the execution of a set of tasks, where each task has associated some processing time and has to be transported to some destination. The problem arises in various applications in production planning and scheduling. We address several variants of the problem and discuss implementations of some of the proposed solutions. The objective is to compute a processing-and-delivery schedule so as to minimize the sum of delivery completion times. All the variants we consider are NP-hard. We experimentally evaluate the performance of some heuristics and show that the shortest processing time (SPT) heuristic consistently yields good schedules. We also briefly discuss results on scheduling with transportation in planar weighted subdivisions, that specifically address the computation of transportation times.

In this paper, we present solutions to minimize wastage of battery power and bandwidth through the design of efficient transmission control strategies. We present several on-line transmission techniques. We analyze the proposed algorithms using competitive analysis techniques against an optimal off-line strategy, which has perfect knowledge of the channel conditions in future. We show that all of our techniques are highly competitive with a majority of them having a small constant-factor (at most 2) competitive ratio.

Conventional two-tier databases have shown performance limitations in the presence of many concurrent clients. We propose logical grouping of clients (or clustering) as the means to improve the performance of collaborative networked databases. In this paper, we discuss a three-tier client-server database architecture (3t-CSD) featuring the above partitioning. The proposed clustering is based on the similarity of clients' access patterns. Each cluster is supervised by a designated manager that coordinates data sharing among its members. A number of clients is optimally partitioned if sites in each individual cluster have the maximum common data access probability possible. We initially show that the optimal client clustering problem is NP-complete and then we develop two approximate solutions based on abstraction and filtering of statistics for client access patterns. Our main goal is to compare the performance of the conventional and three-tier client-server database architecture with respect to the transaction turnaround times and object response times. After developing system prototypes that implement both two-tier and 3t-CSDs, we experimentally show that as long as good client-clustering is possible, the 3t-CSD architecture yields sizable gains over its conventional counterpart. We also compare and evaluate the effectiveness of the two proposed techniques used to create client clusters. Finally, we examine the role of several preprocessing schemes used to reduce the volume of the input data supplied to the clustering techniques.

We study the problem of wavelength assignment for multicast in order to maximize the network capacity in all-optical wavelength-division multiplexing networks. The motivation behind this work is to minimize the call blocking probability by maximizing the remaining network capacity after each wavelength assignment. While all previous studies on the same objective concentrate only on the unicast case, we study the problem for the multicast case. For a general multicast tree, we prove that the multicast wavelength assignment problem of maximizing the network capacity is NP-hard and propose two efficient greedy algorithms. We also study the same problem for a special network topology, a bidirectional ring network, which is practically the most important topology for optical networks. For bidirectional ring networks, a special multicast tree with at most two leaf nodes is constructed. Polynomial time algorithms for multicast wavelength assignment to maximize the network capacity exist under such a special multicast tree with regard to different splitting capabilities. Our work is the first effort to study the multicast wavelength assignment problem under the objective of maximizing network capacity.

In conventional two-tier client-server databases, clients access and modify shared data resident in a common server. As the number of clients increases, the centralized database server can become a performance bottleneck. In order to overcome this scalability problem, a three-tier client-server configuration has been proposed that features the partitioning of clients into logical clusters. Here, the objective is to maximize the data sharing among the clients in each cluster. We propose a genetic algorithm to create such client clusters and evaluate two different techniques for generating the initial solution populations. We compare the performance of the two-tier and three-tier configurations with respect to the transaction turnaround times and object response times. Our experimental results indicate that the clustered architecture can offer improved performance over its two-tier counterpart.

We consider the problem of scheduling a parallel loop with independent iterations on a network of heterogeneous workstations, and demonstrate the effectiveness of a variant of factoring, a scheduling policy originating in the context of shared address-space homogeneous multiprocessors. In the new scheme, weighted factoring, processors are dynamically assigned decreasing size chunks of iterations in proportion to their processing speeds. Through experiments on a network of SUN Sparc workstations we show that weighted factoring significantly outperforms variants of a work-stealing load-balancing algorithm and on certain applications dramatically outperforms factoring as well. We then study weighted work assignment analytically, giving upper and lower bounds on its performance under the assumption that the processor iteration execution times can be modeled as weighted random variables. Department of Computer Science, Polytechnic University, Brooklyn, NY, 11201. Research supported by AR...