The Job-Shop Scheduling Problem (JSSP), under various forms of manufacturing uncertainty, has recently attracted considerable research attention. Most existing studies focus on parameter uncertainty, such as variable processing times, and typically adopt the actor-critic framework. In this paper, we explore a different but prevalent form of uncertainty in JSSP: structural uncertainty. Structural uncertainty arises when a job may follow one of several routing paths, and the selection is determined not by policy, but by situational factors (e.g., the quality of intermediate products) that cannot be known in advance. Existing methods struggle to address this challenge due to incorrect credit assignment: a high-quality action may be unfairly penalized if it is followed by a time-consuming path. To address this problem, we propose a novel method named UP-AAC. In contrast to conventional actor-critic methods, UP-AAC employs an asymmetric architecture. While its actor receives a standard stochastic state, the critic is crucially provided with a deterministic state reconstructed in hindsight. This design allows the critic to learn a more accurate value function, which in turn provides a lower-variance policy gradient to the actor, leading to more stable learning. In addition, we design an attention-based Uncertainty Perception Model (UPM) to enhance the actor's scheduling decisions. Extensive experiments demonstrate that our method outperforms existing approaches in reducing makespan on benchmark instances.

Calibrated Recommendation Systems (CRS) balance user preferences with constraints like diversity, fairness, and novelty to create inclusive recommendation lists. However, existing research often overlooks the mandatory inclusion of sponsored items, assuming unrestricted product selection. In practice, sponsored items, paid for by advertisers, must be included, which can conflict with CRS goals when advertisers' priorities misalign with system objectives. This paper addresses this gap by formulating CRS with sponsored items as a combinatorial optimization problem. We develop efficient approximation algorithms to generate the most calibrated recommendation lists while meeting sponsorship requirements.

Federated Learning (FL) faces challenges due to data heterogeneity, which limits the global model’s performance across diverse client distributions. Personalized Federated Learning (PFL) addresses this by enabling each client to process an individual model adapted to its local distribution. Many existing methods assume that certain global model parameters are difficult to train effectively in a collaborative manner under heterogeneous data. Consequently, they localize or fine-tune these parameters to obtain personalized models. In this paper, we reveal that both the feature extractor and classifier of the global model are inherently strong, and the primary cause of its suboptimal performance is the mismatch between local features and the global classifier. Although existing methods alleviate this mismatch to some extent and improve performance, we find that they either (1) fail to fully resolve the mismatch while degrading the feature extractor, or (2) address the mismatch only post-training, allowing it to persist during training. This increases inter-client gradient divergence, hinders model aggregation, and ultimately leaves the feature extractor suboptimal for client data. To address this issue, we propose FedPFT, a novel framework that resolves the mismatch during training using personalized prompts. These prompts, along with local features, are processed by a shared self-attention-based transformation module, ensuring alignment with the global classifier. Additionally, this prompt-driven approach offers strong flexibility, enabling task-specific prompts to incorporate additional training objectives (\eg, contrastive learning) to further enhance the feature extractor. Extensive experiments show that FedPFT outperforms state-of-the-art methods by up to 5.07%, with further gains of up to 7.08% when collaborative contrastive learning is incorporated.

In this paper, we study a fundamental problem in submodular optimization known as sequential submodular maximization. The primary objective of this problem is to select and rank a sequence of items to optimize a group of submodular functions. The existing research on this problem has predominantly concentrated on the monotone setting, assuming that the submodular functions are non-decreasing. However, in various real-world scenarios, like diversity-aware recommendation systems, adding items to an existing set might negatively impact the overall utility. In response, we propose to study this problem with non-monotone submodular functions and develop approximation algorithms for both flexible and fixed length constraints, as well as a special case with identical utility functions. The empirical evaluations further validate the effectiveness of our proposed algorithms in the domain of video recommendations.

Social advertising, also known as social promotion, is a method of promoting products or ideas through the use of influential individuals, known as ``seeds,'' on online social networks. Advertisers and platforms are the main players in this ecosystem, with platforms selling viral engagements, such as ``likes,'' to advertisers by inserting ads into the feeds of seeds. Seeds are given monetary incentives by the platform in exchange for their participation in the campaign, and when a follower of a seed engages with an ad, the platform receives payment from the advertiser. Specifically, at the beginning of a campaign, the advertiser submits a budget to the platform and this budget can be used for two purposes: recruiting seeds and paying for the viral engagements generated by the seeds. Note that the first part of payment goes to the seeds and the latter one is the actual revenue collected by the platform. The challenge for the platform is to select a group of seeds that will generate the most revenue within the budget constraints set by the advertiser. This problem is challenging as the objective function can be non-monotone and may take on negative values. This makes traditional methods of submodular optimization and influence maximization inapplicable. We study this problem under both non-adaptive and adaptive settings, and propose effective solutions for each scenario.

Assortment optimization presents a significant challenge for online retail platforms. Its primary objective is to create an optimal selection of products from a vast array of substitutes, which will be displayed to customers with the aim of maximizing expected revenue. The purchase behavior of customers is typically influenced by a choice model that determines the probability of purchasing each product from a given assortment. This paper extends traditional assortment optimization by introducing the integration of influencer marketing, a practice that involves enlisting influencers to promote products and enhance their appeal to customers. While conventional assortment optimization assumes fixed product attractiveness, our model enables platforms to strategically enhance the attractiveness of selected products through influencer marketing, thereby increasing revenue potential. Consequently, we present a novel problem formulation encompassing assortment and influencer marketing planning. Leveraging recent advancements in submodular optimization, we develop effective and efficient solutions for this joint optimization problem.

In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both nonadaptive and adaptive settings. It is shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to underrepresentation or overrepresentation of some particular groups. This motivates us to study the submodular maximization problem with group equality, in which we aim to select a group of items to maximize a (possibly nonmonotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0384 .

Running machine learning algorithms on large and rapidly growing volumes of data is often computationally expensive, one common trick to reduce the size of a data set, and thus reduce the computational cost of machine learning algorithms, is probability sampling. It creates a sampled data set by including each data point from the original data set with a known probability. Although the benefit of running machine learning algorithms on the reduced data set is obvious, one major concern is that the performance of the solution obtained from samples might be much worse than that of the optimal solution when using the full data set. In this paper, we examine the performance loss caused by probability sampling in the context of adaptive submodular maximization. We consider a simple probability sampling method which selects each data point with probability at least r. If we set r=1, our problem reduces to finding a solution based on the original full data set. We define sampling gap as the largest ratio between the optimal solution obtained from the full data set and the optimal solution obtained from the samples, over independence systems. Our main contribution is to show that if the sampling probability of each data point is at least r and the utility function is policywise submodular, then the sampling gap is both upper bounded and lower bounded by 1/r. We show that the property of policywise submodular can be found in a wide range of real-world applications, including pool-based active learning and adaptive viral marketing.

In this paper, we study the problem of maximizing the difference between an adaptive submodular (revenue) function and a non-negative modular (cost) function. The input of our problem is a set of n items, where each item has a particular state drawn from some known prior distribution The revenue function g is defined over items and states, and the cost function c is defined over items, i.e., each item has a fixed cost. The state of each item is unknown initially and one must select an item in order to observe its realized state. A policy π specifies which item to pick next based on the observations made so far. Denote by g_{avg}(π) the expected revenue of π and let c_{avg}(π) denote the expected cost of π. Our objective is to identify the best policy π^o ∈ arg max_π g_{avg}(π)-c_{avg}(π) under a k-cardinality constraint. Since our objective function can take on both negative and positive values, the existing results of submodular maximization may not be applicable. To overcome this challenge, we develop a series of effective solutions with performance guarantees. Let π^o denote the optimal policy. For the case when g is adaptive monotone and adaptive submodular, we develop an effective policy π^l such that g_{avg}(π^l) - c_{avg}(π^l) ≥ (1-1/e-ε)g_{avg}(π^o) - c_{avg}(π^o), using only O(nε^{-2}log ε^{-1}) value oracle queries. For the case when g is adaptive submodular, we present a randomized policy π^r such that g_{avg}(π^r) - c_{avg}(π^r) ≥ 1/eg_{avg}(π^o) - c_{avg}(π^o).

As Internet advertisements (also called "ads") revenue growth is being driven further than ever before, one challenge facing publishers, such as Google and Amazon, is to quickly select and place a group of ads in an ad space for each online user with the objective of maximizing the expected revenue. This is especially challenging in the context of mobile advertising due to the smaller screen size of mobile devices and longer user session. We notice that most existing models do not allow the publisher to place the same ad in multiple positions. However, it has been reported that people must see an advertisement at least several times before they will acquire enough interest to consider buying the product or service advertised. To capture this repetition effect we largely generalize the previous model by allowing the publisher to repeat the same ads multiple times. We also notice that many existing models assume that a user will leave the ad session permanently after clicking an ad. Our framework allows a more realistic but complicated user behavior by allowing a user to return to the previous ad session. Our model is able to capture many factors that may affect the click probability of an ad such as the intrinsic quality of the ad, the position of the ad, and all ads that have been previously displayed. We also extend our work to adaptive setting where publishers can dynamically adjust their ad display according to user's feedback. We develop effective algorithms with guarantees of finding either optimal or approximate solutions.

The growing importance of social network for sharing and spreading various contents is leading to the changes in the way of information diffusion. To what extent can social content be diffused highly depends on the size of seed nodes and connectivity of the network. If the seed set is predetermined, then the best way to maximize the content spread is to add connectivities among the users. The existing work shows the content spread maximization problem to be NP-hard. One of the difficulties of designing an effective and efficient algorithm for the content spread maximization problem lies in that the objective function we aim to maximize lacks submodularity. In our work, we formulate the maximize content spread problem from an incremental marginal gain perspective. Although the objective function we derive is not submodular, both submodular lower and upper bounds are constructed and proved. Therefore, we apply the sandwich framework and devise a marginal increment-based algorithm (MIS) that guarantees a data-dependent factor. Furthermore, a novel scalable content spread maximization algorithm influence ranking and fast adjustment (IRFA), which is based on the influence ranking of a single node and fast adjustment with each boosting step in the network, is proposed. Through extensive experiments, we demonstrate that both MIS and IRFA algorithms are effective and outperform other edge selection strategies.

In the past decade, tremendous research effort has been devoted to viral marketing. Most existing works on seed selection in social networks do not take into account the scenario when a profit can be generated from group activities. Each activity has a profit that can be measured by the excitement of the participants. The excitement about one piece of information can vary significantly among different groups of people. Given a social network and a profit function, how can we select the seed users to maximize the expected total amount of profit? This problem is essentially different from the classic influence maximization problem, and existing approaches cannot be directly applied to solve the problem. In this paper, we study the problem of activity profit maximization in social networks. We first prove that the maximizing activity profit problem is nondeterministic polynomial time-hard and cannot be approximated within a constant factor by the simple greedy algorithm. Supermodular degree of a function measures the extent to which it violates submodularity. We design an algorithm that achieves an approximation ratio of (1/(Δ+ 2)) provided that the supermodular degree of the social graph is bounded with A. We then develop an exchange-based technique to further improve the quality of the solution. We also devise a randomized variation approach to overcome the computational burden of the proposed algorithms. Extensive experimental results on three real benchmark data sets demonstrate the efficacy and efficiency of our algorithms over several baseline heuristics.

Traffic measurement in high-speed networks has many applications in improving network performance, assisting resource allocation, and detecting anomalies. In this paper, we study a new problem called k-persistent spread estimation, which measures persist traffic elements in each flow that appear during at least k out of t measurement periods, where k and t can be arbitrarily defined in user queries. Solutions to this problem have interesting applications in network attack detection, popular content identification, user access profiling, etc. Yet, it is under-investigated as the prior work only addresses a special case with a questionable assumption. Designing an efficient and accurate k -persistent estimator requires us to use bitwise SUM (instead of bitwise AND typical in the prior art) to join the information collected from different periods. This seemly simple change has fundamental impact on the mathematical process in deriving an estimator, particular over space-saving virtual bitmaps. Based on real network traces, we show that our new estimator can accurately estimate the k -persistent spreads of the flows. It also performs much better than the existing work on the special case of measuring elements that appear in all periods.

We study the problem of active friending in online social networks. Given an initiator who want to friend a target person on a social network, we propose a strategy to support active friending through a series of recommendation lists. The lists serve as a step-to-step guidance for the initiator. We formulate an optimization problem, Constrained Active Friending CAF), for configuring the recommendation lists in the active friending process. Our goal is to maximize the acceptance probability of the invitation from the initiator to the friending target, by recommending selective intermediate friends to approach the target. We prove that CAF problem is NP-hard under the linear threshold model. We propose an algorithm based on discrete super-differentials that derives a guaranteed approximation for this problem. Extensive evaluation results on benchmark social network datasets validate the effectiveness and efficiency of our algorithms.

In this paper, we investigate a largely extended version of classical MAB problem, called networked combinatorial bandit problems. In particular, we consider the setting of a decision maker over a networked bandits as follows: each time a combinatorial strategy, e.g., a group of arms, ischosen, and the decision maker receives a rewardresulting from her strategy and also receives a side bonusresulting from that strategy for each arm's neighbor. This is motivated by many real applications such as on-line social networks where friends can provide their feedback on shared content, therefore if we promote a product to a user, we can also collect feedback from her friends on that product. To this end, we consider two types of side bonus in this study: side observation and side reward. Upon the number of arms pulled at each time slot, we study two cases: single-play and combinatorial-play. Consequently, this leaves us four scenarios to investigate in the presence of side bonus: Single-play with Side Observation, Combinatorial-play with Side Observation, Single-play with Side Reward, and Combinatorial-play with Side Reward. For each case, we present and analyze a series of zero regret polices where the expect of regret over time approaches zero as time goes to infinity. Extensive simulations validate the effectiveness of our results.

Although influence maximization problem has been extensively studied over the past ten years, majority of existing work adopt one of the following models: full-feedback model or zero-feedback model. In the zero-feedback model, we have to commit the seed users all at once in advance, this strategy is also known as non-adaptive policy. In the full-feedback model, we select one seed at a time and wait until the diffusion completes, before selecting the next seed. Full-feedback model has better performance but potentially huge delay, zero-feedback model has zero delay but poorer performance since it does not utilize the observation that may be made during the seeding process. To fill the gap between these two models, we propose partial-feedback model, which allows us to select a seed at any intermediate stage. We develop a novel alpha-greedy policy that achieves a bounded approximation ratio.

With the advent of virtualization technologies, cloud computing resource allocation issue plays an important role. However, the existing studies have not fully considered the heterogeneous demands from different cloud tenants. To tackle this, we design a more flexible cloud resource allocation mechanism which can maximize the profit of the cloud provider and support three general types of resource requirements from the cloud tenants. In this work, the jobs from tenants will bid for the usage of VMs in 3 types: 1) fixed time intervals, 2) time window intervals and 3) Time window slice intervals. We proved that the proposed approximation allocation mechanism has an approximation factor which approaches 1.58 when cmcloses to infinity.

It has been reported that 40% of consumers will share an email offer with their friend and 28% of consumers will share deals via social media platforms. This motivates us to study the influence maximization discount allocation problem: given a social network and a limited marketing budget, which set of initial users should be selected to receive the discount, and how much should the discounts be worth? Our goal is to maximize the number of customers who finally adopt the target product. We investigate this problem under both non-adaptive and adaptive settings. In the first setting, we have to commit the set of initial users and corresponding discounts all at once in advance. In the latter case, given that an user has been offered a discount, we are able to know immediately her decision on whether or not to accept that discount, therefore, the decision process is performed in a sequential manner based on the feedback from previously selected users. We propose a simple greedy policy with an approximation ratio of (1-1/e) in non-adaptive setting. For the significantly more complex adaptive setting, we propose a series of adaptive policies with bounded approximation ratio in terms of expected utility.

Social advertising (or social promotion) is an effective approach that produces a significant cascade of adoption through influence in the online social networks. The goal of this work is to optimize the ad allocation from the platform's perspective. On the one hand, the platform would like to maximize revenue earned from each advertiser by exposing their ads to as many people as possible, on the other hand, the platform wants to reduce free-riding to ensure the truthfulness of the advertiser. To this end, we introduce a utility function that can access the above tradeoff. Based on this utility function, we define and study two social advertising problems: budgeted social advertising problem and unconstrained social advertising problem. In the first problem, we aim at selecting a set of seeds for each advertiser that maximizes the utility while setting budget constraints on the attention cost; in the second problem, we propose to optimize a linear combination of the utility and attention costs. We prove that both problems are NP-hard, and then develop constant factor approximation algorithms for both problems.

With the recent introduction of Spot Instances in the Amazon Elastic Compute Cloud (EC2), users can bid for resources and, thus, control the balance of reliability versus monetary costs. Mechanisms and tools that deal with the cost-reliability tradeoffs under this scheme are of great value for users seeking to reduce their costs while maintaining high reliability. In this paper, we propose a set of bidding strategies under several service-level agreement (SLA) constraints. In particular, we aim to minimize the monetary cost and volatility of resource provisioning. Essentially, to derive an optimal bidding strategy, we formulate this problem as a Constrained Markov Decision Process (CMDP). Based on this model, we are able to obtain an optimal randomized bidding strategy through linear programming. Using real Instance price traces and workload models, we compare several adaptive checkpointing schemes in terms of monetary costs and job completion time. We evaluate our model and demonstrate how users should bid optimally on Spot Instances to reach different objectives with desired levels of confidence.

Wireless Sensor Networks (WSN) are widely adopted to monitor and collect data, such as temperature, humidity etc., from the physical environment. Those sensor readings often exhibit strong spacial-temporal correlations, e.g., sensor readings from nearby sensors tend to be similar, and sensor readings from consecutive time slots are also highly correlated. As in our previous works, we first introduce the concept of Quality of Monitoring (QoM), and further define an utility function to quantify the QoM under different sensing schedules. In particular, the utility function is non-decreasing submodular function which is able to capture the spacial-temporal correlations among sensor readings. The objective of this work is to develop a set of distributed sensing schedules in order to achieve the highest QoM subject to energy constraint (e.g., under fixed working duty cycle). Extensive experiments validate our theoretical results. Notice that most existing works on this topic put their focus on centralized sensing schedule, which is shown to be extremely difficult to implement in large scale networked sensor system.

Information propagation in delay tolerant networks (DTN) is difficult due to the lack of continues connectivity. Most of previous work put their focus on the information propagation in static network. In this work, we examine two closely related problems on information propagation in predicable DTN. In particular, we assume that during a certain time period, the interacting process among nodes is known a priori or can be predicted. The first problem is to select a set of initial source nodes, subject to budget constraint, in order to maximize the total weight of nodes that receive the information at the final stage. This problem is well-known influence maximization problem which has been extensively studied for static networks. The second problem we want to study is minimum cost initial set problem, in this problem, we aim to select a set of source nodes with minimum cost such that all the other nodes can receive the information with high probability. We conduct extensive experiments using $10,000$ users from real contact trace.

With the recent introduction of Spot Instances in the Amazon Elastic Compute Cloud (EC2), users can bid for resources and thus control the balance of reliability versus monetary costs. Mechanisms and tools that deal with the cost-reliability trade-offs under this schema are of great value for users seeking to lessen their costs while maintaining high reliability. In this paper, we propose a set of bidding strategies to minimize the cost and volatility of resource provisioning. Essentially, to derive an optimal bidding strategy, we formulate this problem as a Constrained Markov Decision Process (CMDP). Based on this model, we are able to obtain an optimal randomized bidding strategy through linear programming. Using real Instance Price traces and workload models, we compare several adaptive check-pointing schemes in terms of monetary costs and job completion time. We evaluate our model and demonstrate how users should bid optimally on Spot Instances to reach different objectives with desired levels of confidence.

Due to advances in low power micro-sensor technology, energy harvesting techniques, we can now build large scale solar-powered sensor networks to support long-running operations. Solar powered sensors often harvest variable amounts of energy in different weather conditions. Then a primary requirement for an efficient and a long-running solar-powered sensor system is to adapt to changing environment conditions and resources, and to gather as much valuable data as possible. Sensing and collecting data at a constant rate, without taking into account energy availability or data deliverability, will either drain the battery or waste resources. In this work, we design and test a highly efficient and robust solar-powered system SmartMote; and we further present an energy and value of information (VoI) aware routing strategy, that balances the rates of sensing with packet delivery for SmartMote. SmartMote achieves fairness and near maximum utility across the network. We deploy SmartMote in a forest with 100 sensors in order to monitor the humidity, temperature and luminance intensity. Our experimental results corroborate our design.

In this paper, we study two tightly coupled topics in online social networks (OSN): relationship classification and information propagation. The links in a social network often reflect social relationships among users. In this work, we first investigate identifying the relationships among social network users based on certain social network property and limited pre-known information. Social networks have been widely used for online marketing. A critical step is the propagation maximization by choosing a small set of seeds for marketing. Based on the social relationships learned in the first step, we show how to exploit these relationships to maximize the marketing efficacy. We evaluate our approach on large scale real-world data from Renren network, showing that the performances of our relationship classification and propagation maximization algorithm are pretty good in practice.

A real-time monitor and rescue system must be able to both quickly and reliably detect the event happening in its monitoring region. Furthermore, it is required to fulfill certain rescue mission, e.g., navigate victims to exit through safe path in case of emergency. Current monitor and rescue approaches generally rely on either teleoperated robots, or teams of wireless robots. Typically the robots used in these systems tend to have high cost which make them unpractical in large scale deployment and applications. In this work, we present a realtime monitor and rescue system, TelosW-Bot Net, utilizing integrated networks. The integrated network is an integration of stationary sensor networks and robots: static sensor networks comprised of large numbers of small, simple, and inexpensive wireless sensors, and the robots which can communicate and controlled by sensor nodes. We demonstrate the efficacy of our system in real test bed composed of 46 sensors, which is one of the largest robotic sensor network to our knowledge, providing empirical results.

In this work, we present a monitor and rescue system utilizing hybrid networks which is a integration of stationary sensor networks and mobile sensor networks: stationary sensor networks comprised of large numbers of small, simple, and inexpensive wireless sensors, and the mobile sensor network contains a set of mobile sensors (robots). The static sensors in our network have “monitoring” ability, i.e., any activated static sensor can detect the event as long as its sensing range intersects the event region. And the mobile sensors have “moving” and “rescuing” ability, e.g., they can move toward the event region with limited speed and further perform certain rescuing/processing operations on the event. We can consider the event as a hazard, e.g., wild fire, and the mobile sensors as fireman robots. As soon as the fire is detected by the static sensors, the fireman robots are expected to move from its initial location to the hazard region within minimum latency. We define the reaction delay of the system as the delay from the occurrence of event till at least one mobile sensor reaches the event. In order to satisfy certain reaction delay requirement while minimizing the total cost, we propose a number of deployment strategies for the stationary sensor network and mobile sensor network respectively. We further design a random wake-up scheduling for the static sensors for the sake of energy efficiency. Finally, we propose a pure distributed motion strategy for mobile sensors without reliance on localization services such as GPS, focusing on simple algorithms for distributed decision making and information propagation. We demonstrate the efficacy of our system in simulation, providing empirical results.

The benefits of using mobile sink to prolong sensor network lifetime have been well recognized. However, few provably theoretical results remain are developed due to the complexity caused by time-dependent network topology. In this work, we investigate the optimum routing strategy for the static sensor network. We further propose a number of motion stratifies for the mobile sink(s) to gather real time data from static sensor network, with the objective to maximize the network lifetime. Specially, we consider a more realistic model where the moving speed and path for mobile sinks are constrained. Our extensive experiments show that our scheme can significantly prolong entire network lifetime and reduce delivery delay.

Recent technological advances have motivated large-scale deployment of RFID systems. RFID readers are often static and carefully deployed in a planned manner. However, the distribution and movements of tags are often dynamically changed and unpredictable. We study a challenging problem of scheduling the activation of the readers without collision such that the system can work in a stable way in the long term. Here a schedule is stable if at any time slot, the number of total unread tags is bounded from above with high probability under this scheduling. In this paper, we propose a stable reader activation scheduling protocol, RASPberry, in multi-reader RFID systems. We analytically prove that our scheduling protocol, RASPberry, is stable if the arrival rate of tags is less than the processing rate of all readers. In RASPberry, at any time slot, a reader can determine its status using only information of readers within a local neighborhood. To the best of our knowledge, this is the first work to address the stability problem of reader activation scheduling in RFID systems. Our extensive simulations show that our system performs very well.

Event detection is an essential task for wireless sensor networks. In this paper we present the design and implementation of MC-Detect, an efficient scheme for detecting and estimating events in the network. With sparse samples processed at the basestation, our approach reduces the transmission and computation cost of low power sensor nodes. Our demonstration shows the real-time event detection in practice on a small network of TelosB motes.