A real world supply chain planning starts with the demand forecasting as a key input. In most scenarios, especially in fields like e-commerce where demand patterns are complex and are large scale, demand forecasting is done independent of supply chain constraints. There have been a plethora of methods, old and recent, for generating accurate forecasts. However, to the best of our knowledge, none of the methods take supply chain constraints into account during forecasting. In this paper, we are primarily interested in supply chain aware forecasting methods that does not impose any restrictions on demand forecasting process. We assume that the base forecasts follow a distribution from exponential family and are provided as input to supply chain planning by specifying the distribution form and parameters. With this in mind, following are the contributions of our paper. First, we formulate the supply chain aware forecast improvement of a base forecast as finding the game theoretically optimal parameters satisfying the supply chain constraints. Second, for regular distributions from exponential family, we show that this translates to projecting base forecast onto the (convex) set defined by supply constraints, which is at least as accurate as the base forecasts. Third, we note that using off the shelf convex solvers does not scale for large instances of supply chain, which is typical in e-commerce settings. We propose algorithms that scale better with problem size. We propose a general gradient descent based approach that works across different distributions from exponential family. We also propose a network flow based exact algorithm for Laplace distribution (which relates to mean absolute error, which is the most commonly used metric in forecasting). Finally, we substantiate the theoretical results with extensive experiments on a real life e-commerce data set as well as a range of synthetic data sets.

In a team formation problem, one is required to find a group of users that can match the requirements of a collaborative task. Example of such collaborative tasks abound, ranging from software product development to various participatory sensing tasks in knowledge creation. Due to the nature of the task, team members are often required to work on a co-operative basis. Previous studies [1, 2] have indicated that co-operation becomes effective in presence of social connections. Therefore, effective team selection requires the team members to be socially close as well as a division of the task among team members so that no user is overloaded by the assignment. In this work, we investigate how such teams can be formed on a social network.

In this paper, we study the problem of efficiently computing multiple aggregation queries over a data stream. In order to share computation, prior proposals have suggested instantiating certain intermediate aggregates which are then used to generate the final answers for input queries. In this work, we make a number of important contributions aimed at improving the execution and generation of query plans containing intermediate aggregates. These include: (1) a different hashing model, which has low eviction rates, and also allows us to accurately estimate the number of evictions, (2) a comprehensive query execution cost model based on these estimates, (3) an efficient greedy heuristic for constructing good low-cost query plans, (4) provably near-optimal and optimal algorithms for allocating the available memory to aggregates in the query plan when the input data distribution is Zipf-like and Uniform, respectively, and (5) a detailed performance study with real-life IP flow data sets, which show that our multiple aggregates computation techniques consistently outperform the best-known approach.

Cisco's NetFlow collector (NFC) is a powerful example of a real-world product that supports multiple aggregate queries over a continuous stream of IP flow records. NFC enables a plethora of network management tasks like traffic demands estimation, application traffic profiling, etc. In this paper, we investigate two computation sharing techniques for enabling streaming applications such as NFC to scale to hundreds of queries. Our first technique instantiates certain intermediate aggregates which are then used to generate the final answers for input queries. Our second technique coalesces the filter conditions of similar queries and uses the coalesced filter to pre-filter stream data input to these queries. Using these techniques, we propose a heuristic to compute a good query plan and perform extensive simulations to show that our heuristic delivers a factor of over 3 performance improvement compared to a naive approach.

In a wireless network withnodeexclusivespectrumsharing, two popular schedules are maximum weight matching (MWM) schedule and maximum size matching (MSM) schedule. The former has been proved to be throughput optimal and has superior delay properties, and the latter schedules as many links, with packets to transmit, as possible. However, it is challenging to design algorithms for computing these schedules that (i) are distributed, (i.e., only local message exchanges between neighboring nodes are permitted) (ii) have low running times (iii) exchanges a small number of messages. In this paper, we develop algorithms that satisfy these properties and also provide good approximations to MWM and MSM schedules. We also note that constant approximation to MWM leads to improved delay properties. We refer to a round as a length of time over which every node in the network can make at most one message-transmission attempt. We propose distributed algorithms for computing (i) 1/2 - epsi e approximation to MWM schedule in O(log(1/epsi) log2n) rounds, and (ii) 2/3 - epsi approximation to MSM schedule in O((1/epsi) log2n) rounds, where n is the network size. Simulation results with a popular model for wireless ad-hoc networks demonstrate that (i) our algorithms perform within 85% - 95% of the optimal in many scenarios, and (ii) the time-complexity of the algorithms can be reduced considerably in practice. The number of message transmissions for both our algorithms scale as O(n log2n). In summary, ours is the first work to (i) provide half (two-third) approximate distribute algorithms for computing MWM (MSM) schedule with logarithmic time- complexity and quasi-linear message exchanges (ii) demonstrate that the algorithms are close to optimal for realistic topologies.

In this paper, we propose new "low-overhead" network monitoring techniques to detect violations of path-level QoS guarantees like end-to-end delay, loss, etc. Unlike existing path monitoring schemes, our approach does not calculate QoS parameters for all paths. Instead, it monitors QoS values for only a few paths, and exploits the fact that path anomalies are rare and anomalous states are well separated from normal operation, to rule out path QoS violations in most situations. We propose a heuristic to select a small subset of network paths to monitor while ensuring that no QoS violations are missed. Experiments with an ISP topology from the Rocketfuel data set show that our heuristic can deliver almost a 50% decrease in monitoring overhead compared to previous schemes.

IEEE 802.11 WiFi equipment based wireless mesh networks have recently been proposed as an inexpensive approach to connect far-flung rural areas. Such networks are built using high-gain directional antennas that can establish long-distance wireless point-to-point links. Some nodes in the network (called gateway nodes) are directly connected to the wired internet, and the remaining nodes connect to the gateway(s) using one or more hops. The dominant cost of constructing such a mesh network is the cost of constructing antenna towers at nodes. The cost of a tower depends on its height, which in turn depends on the length of its links and the physical obstructions along those links. We investigate the problem of selecting which links should be established such that all nodes are connected, while the cost of constructing the antenna towers required to establish the selected links is minimized. We show that this problem is NP-hard and that a better than O(log n) approximation cannot be expected, where n is the number of vertices in the graph. We then present the first algorithm in the literature, for this problem, with provable performance bounds. More precisely, we present a greedy algorithm that is an O(log n) approximation algorithm for this problem. Finally, through simulations, we compare our approximation algorithm with both the optimal solution, and a naive heuristic.

In many distributed environments, the primary function of monitoring software is to detect anomalies, i.e., instances when system behavior deviates substantially from the norm. In this paper, we propose communication-efficient schemes for the anomaly detection problem, which we model as one of detecting the violation of global constraints defined over distributed system variables. Our approach eliminates the need to continuously track the global system state by decomposing global constraints into local constraints that can be checked efficiently at each site. Only in the occasional event that a local constraint is violated, do we resort to more expensive global constraint checking. We show that the problem of selecting the local constraints, based on frequency distribution of individual system variables, so as to minimize the communication cost is NP-hard. We propose approximation algorithms for computing provably near-optimal (in terms of the number of messages) local constraints. Experimental results with real-life network traffic data sets demonstrate that our technique can reduce message communication overhead by as much as 70% compared to existing data distribution-agnostic approaches.

In this paper, we develop passive network tomography techniques for inferring link-level anomalies like excessive loss rates and delay from path-level measurements. Our approach involves placing a few passive monitoring devices on strategic links within the network, and then passively monitoring the performance of network paths that pass through those links. In order to keep the monitoring infrastructure and communication costs low, we focus on minimizing (1) the number of passive probe devices deployed, and (2) the set of monitored paths. For mesh topologies, we show that the above two minimization problems are NP-hard, and consequently, devise polynomial-time greedy algorithms that achieve a logarithmic approximation factor, which is the best possible for any algorithm. We also consider tree topologies typical of Enterprise networks, and show that while similar NP-hardness results hold, constant factor approximation algorithms are possible for such topologies.

Recently, there has been a growing interest in gossip-based protocols that employ randomized communication to ensure robust information dissemination. In this paper, we present a novel gossip-based scheme using which all the nodes in an n-node overlay network can compute the common aggregates of MIN, MAX, SUM, AVERAGE, and RANK of their values using O(n log log n) messages within O(log n log log n) rounds of communication. To the best of our knowledge, ours is the first result that shows how to compute these aggregates with high probability using only O(n log log n) messages. In contrast, the best known gossip-based algorithm for computing these aggregates requires O(nlog n) messages and O(log n) rounds. Thus, our algorithm allows system designers to trade off a small increase in round complexity with a significant reduction in message complexity. This can lead to dramatically lower network congestion and longer node lifetimes in wireless and sensor networks, where channel bandwidth and battery life are severely constrained.