Assignment Games with Conflicts: Robust Price of Anarchy and Convergence Results via Semi-Smoothness

We study assignment games in which jobs select machines, and in which certain pairs of jobs may conflict, which is to say they may incur an additional cost when they are both assigned to the same machine, beyond that associated with the increase in load. Questions regarding such interactions apply beyond allocating jobs to machines: when people in a social network choose to align themselves with a group or party, they typically do so based upon not only the inherent quality of that group, but also who amongst their friends (or enemies) chooses that group as well. We show how semi-smoothness, a recently introduced generalization of smoothness, is necessary to find tight bounds on the robust price of anarchy, and thus on the quality of correlated and Nash equilibria, for several natural job-assignment games with interacting jobs. For most cases, our bounds on the robust price of anarchy are either exactly 2 or approach 2. We also prove new convergence results implied by semi-smoothness for our games. Finally we consider coalitional deviations, and prove results about the existence and quality of strong equilibrium.     

Generating test case chains for reactive systems

Testing of reactive systems is challenging because long input sequences are often needed to drive them into a state to test a desired feature. This is particularly problematic in on-target testing, where a system is tested in its real-life application environment and the amount of time required for resetting is high. This article presents an approach to discovering a test case chain—a single software execution that covers a group of test goals and minimizes overall test execution time. Our technique targets the scenario in which test goals for the requirements are given as safety properties. We give conditions for the existence and minimality of a single test case chain and minimize the number of test case chains if a single test case chain is infeasible. We report experimental results with our ChainCover tool for C code generated from Simulink models and compare it to state-of-the-art test suite generators.     

Is It Possible to Retain Customer Loyalty When a Service Has Failed?

This article aims to analyze the impact of recovery on loyalty in the context of a service chain characterized by the e‐quality–perceived value–loyalty relationship. A sample of 91 out of 1,201 respondents claimed to have had service problems with an online travel agency website. A causal model to test relationships was performed using structural equations modeling, and it was found that data fit with the proposed model. The really important point to retaining customers is quality. It is not so clear that the recovery effort might affect loyalty. Our findings underpin some previous stream of literature confirming that recovery does not always affect loyalty. Although the literature has not reached a consensus in this topic, we add new elements in this debate.     

Detecting end-effectors on 2.5D data using geometric deformable models: Application to human pose estimation

End-effectors are usually related to the location of limbs, and their reliable detection enables robust body tracking as well as accurate pose estimation. Recent innovation in depth cameras has re-stated the pose estimation problem. We focus on the information provided by these sensors, for which we borrow the name 2.5D data from the Graphics community. In this paper we propose a human pose estimation algorithm based on topological propagation. Geometric Deformable Models are used to carry out such propagation, implemented according to the Narrow Band Level Set approach. A variant of the latter method is proposed, including a density restriction which helps preserving the topological properties of the object under analysis. Principal end-effectors are extracted from a directed graph weighted with geodesic distances, also providing a skeletal-like structure describing human pose. An evaluation against reference methods is performed with promising results. The proposed solution allows a frame-wise end-effector detection, with no temporal tracking involved, which may be generalized to the tracking of other objects beyond human body.     

Solving weighted CSPs with meta-constraints by reformulation into satisfiability modulo theories

We introduce WSimply, a new framework for modelling and solving Weighted Constraint Satisfaction Problems (WCSP) using Satisfiability Modulo Theories (SMT) technology. In contrast to other well-known approaches designed for extensional representation of goods or no-goods, and with few declarative facilities, our approach aims to follow an intensional and declarative syntax style. In addition, our language has built-in support for some meta-constraints, such as priority and homogeneity, which allows the user to easily specify rich requirements on the desired solutions, such as preferences and fairness. We propose two alternative strategies for solving these WCSP instances using SMT. The first is the reformulation into Weighted SMT (WSMT) and the application of satisfiability test based algorithms from recent contributions in the Weighted Maximum Satisfiability field. The second one is the reformulation into an operation research-like style which involves an optimisation variable or objective function and the application of optimisation SMT solvers. We present experimental results of two well-known problems: the Nurse Rostering Problem (NRP) and a variant of the Balanced Academic Curriculum Problem (BACP), and provide some insights into the impact of the addition of meta-constraints on the quality of the solutions and the solving time.     

Search combinators

The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or users are faced with a general-purpose programming language whose features are not tailored towards writing search heuristics. As a result, major improvements in performance may remain unexplored. This article introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple modeling language for search (high-level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). By allowing the user to define application-tailored search strategies from a small set of primitives, search combinators effectively provide a rich domain-specific language (DSL) for modeling search to the user. Remarkably, this DSL comes at a low implementation cost to the developer of a constraint solver. The article discusses two modular implementation approaches and shows, by empirical evaluation, that search combinators can be implemented without overhead compared to a native, direct implementation in a constraint solver.     

EOQ Model: The Case in Which the Placing of Orders Is Rewarded

The first models of optimization of inventory management costs have undergone few changes since they were developed at the beginning of the last century. It is only with the passage of time that new scenarios have appeared with the introduction of new systems of production, and consequently of new strategies in the logistics chain. In this article, we analyze and propose a revision of the basic inventory model of economic order quantity first defined by Harris in 1913 for a scenario in which the owner of the stock receives a bonus or reward each time he replenishes his stock. This situation arises when the supplier receives a benefit (which he then shares with the customer) when managing his stock replenishment. An array of nested models is shown to illustrate this scenario, from which the constraints of previous scenarios have been removed. The model provides insights into the negotiation of batch size between supplier and buyer in a win‐win environment in the specific situation in which the supplier gives a bonus to the buyer at each stock replenishment. © 2011 Wiley Periodicals, Inc.     

VALENCE: affective visualisation using EEG

VALENCE is an interactive visualisation controlled by live brainwave monitoring. We used a wireless EEG headset to monitor the player's alpha waves (an indicator of relaxation) and valence (an indicator of emotion or arousal). The game world is an emergent system of attractive and repulsive forces responding to EEG input.