The core business of Mobile Network Operators (MNO) has moved from network management and phone services to service providing. In contrast to Information Communication Technology (ICT) service providers, MNOs handle large amounts of their customers’ context data and generated content, which can be used to bring value-added services to customers and therefore, generate solid revenues. Given this scenario, this paper describes how Telecom Italia (a major Italian MNO) has prototyped such type of services after a deep research performed in the context-awareness and context management field and using its user-generated content management facilities in federation with other platforms and systems.

Public sensing is a new research area in the fields of wireless sensor networks and mobile computing. It leverages the mobile sensors and system resources readily available in mobile phones to execute sensing tasks. In order to plan, execute and adapt large-scale sensing tasks, applications need to query for the available resources, e.g. the density of certain sensors. We investigate how such information can be provided, and we propose a resource manager for public sensing. Our primary goal is to minimize the energy consumed by the mobile devices to make public sensing feasible without disturbing users. We propose a cluster-based protocol for collecting local views of the resource state using local ad-hoc communication since this is much more energy-efficient than long-range (e.g. cellular) communication. We compare our solution to a standard approach where mobile devices communicate their resource states using the cellular phone network. We show that 65% of the energy is saved and the communication load on the infrastructure is reduced by 90% while an average delivery ratio of 93% is retained.

A major challenge of pervasive context-aware computing and intelligent environments resides in the acquisition and modelling of rich and heterogeneous context data. Decisive aspects of this information are the ongoing human activities at different degrees of granularity. We conjecture that ontology-based activity models are key to support interoperable multilevel activity representation and recognition. In this paper, we report on an initial investigation about the application of probabilistic description logics (DLs) to a framework for the recognition of multilevel activities in intelligent environments. In particular, being based on Log-linear DLs, our approach leverages the potential of highly expressive description logics with probabilistic reasoning in one unified framework. While we believe that this approach is very promising, our preliminary investigation suggests that challenging research issues remain open, including extensive support for temporal reasoning, and optimizations to reduce the computational cost.

Experience using computational perception within the context of art and performance is reported. Four different types of pedagogical projects are presented: a new non-majors introductory computing course, an upper-level course covering computer vision and graphics inan integrated manner, an interactive dance piece, and a peer-led tele-workshop outreach series.

This paper suggests some teaching strategies for Algorithms and AI courses. These courses can have a common goal of teaching complex problem-solving techniques. Based on my experience teaching undergraduates in a small liberal-arts college, the paper offers concrete ideas for working toward this goal. These ideas are supported by relevant studies in cognitive science and education. Together, they provide a plan for structuring lessons and assignments to help student become better problem-solvers.

We resolve a several-years old open question in visibility-based pursuit evasion: how many pursuers are needed to capture an evader in an arbitrary polygonal environment with obstacles? The evader is assumed to be adversarial, moves with the same maximum speed as pursuers, and is "sensed'' by a pursuer only when it lies inline-of-sight of that pursuer. The players move in discrete time steps, and the capture occurs when a pursuer reaches the position of the evader on its move. Our main result is that O( √ h + log n ) pursuers can always win the game with a deterministic search strategy in any polygon with n vertices and h obstacles (holes). In order to achieve this bound, however, we argue that the environment must satisfy a minimum feature size property, which essentially requires the minimum distance between any two vertices to be of the same order as the speed of the players. Without the minimum feature size assumption, we show that Ω < ( √( n /log n )) pursuers are needed in the worst-case even for simply-connected (hole-free) polygons of n vertices!  This reveals an unexpected subtlety that seems to have been overlookedin previous work claiming that O(log n ) pursuers can always win insimply-connected n -gons.  Our lower bound also shows that capturing an evader is inherently more difficult than just "seeing" it because O(log n ) pursuers are provably sufficient for line-of-sight detection even against an arbitrarily fast evaderin simple n -gons.

A key challenge in reducing the burden of cardiovascular disease is matching patients to treatments that are most appropriate for them. Different cardiac assessment tools have been developed to address this goal. Recent research has focused on heart rate motifs, i.e., short-term heart rate sequences that are over- or under-represented in long-term electrocardiogram (ECG) recordings of patients experiencing cardiovascular outcomes, which provide novel and valuable information for risk stratification. However, this approach can leverage only a small number of motifs for prediction and results in difficult to interpret models. We address these limitations by identifying latent structure in the large numbers of motifs found in long-term ECG recordings. In particular, we explore the application of topic models to heart rate time series to identify functional sets of heart rate sequences and to concisely describe patients using task-independent features for various cardiovascular outcomes. We evaluate the approach on a large collection of real-world ECG data, and investigate the performance of topic mixture features for the prediction of cardiovascular mortality. The topics provided an interpretable representation of the recordings and maintained valuable information for clinical assessment when compared with motif frequencies, even after accounting for commonly used clinical risk scores.

This paper addresses the problem of automated advice provision in settings that involve repeated interactions between people and computer agents. This problem arises in many real world applications such as route selection systems and office assistants. To succeed in such settings agents must reason about how their actions in the present influence people's future actions. This work models such settings as a family of repeated bilateral games of incomplete information called ``choice selection processes'', in which players may share certain goals, but are essentially self-interested. The paper describes several possible models of human behavior that were inspired by behavioral economic theories of people's play in repeated interactions. These models were incorporated into several agent designs to repeatedly generate offers to people playing the game. These agents were evaluated in extensive empirical investigations including hundreds of subjects that interacted with computers in different choice selections processes. The results revealed that an agent that combined a hyperbolic discounting model of human behavior with a social utility function was able to outperform alternative agent designs, including an agent that approximated the optimal strategy using continuous MDPs and an agent using epsilon-greedy strategies to describe people's behavior. We show that this approach was able to generalize to new people as well as choice selection processes that were not used for training. Our results demonstrate that combining computational approaches with behavioral economics models of people in repeated interactions facilitates the design of advice provision strategies for a large class of real-world settings.

In many dynamic matching applications — especially high-stakes ones — the competitive ratios of prior-free online algorithms are unacceptably poor. The algorithm should take distributional information about possible futures into account in deciding what action to take now. This is typically done by drawing sample trajectories of possible futures at each time period, but may require a prohibitively large number of trajectories or prohibitive memory and/or computation to decide what action to take. Instead, we propose to learn potentials of elements (e.g., vertices) of the current problem. Then, at run time, we simply run an offline matching algorithm at each time period, but subtracting out in the objective the potentials of the elements used up in the matching. We apply the approach to kidney exchange. Kidney exchanges enable willing but incompatible patient-donor pairs (vertices) to swap donors. These swaps typically include cycles longer than two pairs and chains triggered by altruistic donors. Fielded exchanges currently match myopically, maximizing the number of patients who get kidneys in an offline fashion at each time period. Myopic matching is sub-optimal; the clearing problem is dynamic since patients, donors, and altruists appear and expire over time. We theoretically compare the power of using potentials on increasingly large elements: vertices, edges, cycles, and the entire graph (optimum). Then, experiments show that by learning vertex potentials, our algorithm matches more patients than the current practice of clearing myopically. It scales to exchanges orders of magnitude beyond those handled by the prior dynamic algorithm.

Successive elimination of candidates is often a route to making manipulation intractable to compute. We prove that eliminating candidates does not necessarily increase the computational complexity of manipulation. However, for many voting rules used in practice, the computational complexity increases. For example, it is already known that it is NP-hard to compute how a single voter can manipulate the result of single transferable voting (the elimination version of plurality voting). We show here that it is NP-hard to compute how a single voter can manipulate the result of the elimination version of veto voting, of the closely related Coombs’ rule, and of the elimination versions of a general class of scoring rules.