The finite horizon investor problem with a budget constraint

We study a model that incorporates a budget constraint in a decision making problem. Our goal is to maximize the expected wealth, where in each time period we can either stop the business getting our current wealth or to continue one additional time period and getting a random revenue. We show that when the wealth is scalar, the problem is NP-hard and we provide an FPTAS. However, when the wealth is vector with at least two components the problem cannot be approximated.     

Formal verification of human-automation interaction

This paper discusses a formal and rigorous approach to the analysis of operator interaction with machines. It addresses the acute problem of detecting design errors in human-machine interaction and focuses on verifying the correctness of the interaction in complex and automated control systems. The paper describes a systematic methodology for evaluating whether the interface provides the necessary information about the machine to enable the operator to perform a specified task successfully and unambiguously. It also addresses the adequacy of information provided to the user via training material (e.g., user manual) about the machine's behavior. The essentials of the methodology, which can be automated and applied to the verification of large systems, are illustrated by several examples and through a case study of pilot interaction with an autopilot aboard a modern commercial aircraft. The expected application of this methodology is an augmentation and enhancement, by formal verification, of human-automation interfaces.     

Intrusion detection for mobile devices using the knowledge-based, temporal abstraction method

In this paper, a new approach for detecting previously unencountered malware targeting mobile device is proposed. In the proposed approach, time-stamped security data is continuously monitored within the target mobile device (i.e., smartphones, PDAs) and then processed by the knowledge-based temporal abstraction (KBTA) methodology. Using KBTA, continuously measured data (e.g., the number of sent SMSs) and events (e.g., software installation) are integrated with a mobile device security domain knowledge-base (i.e., an ontology for abstracting meaningful patterns from raw, time-oriented security data), to create higher level, time-oriented concepts and patterns, also known as temporal abstractions. Automatically-generated temporal abstractions are then monitored to detect suspicious temporal patterns and to issue an alert. These patterns are compatible with a set of predefined classes of malware as defined by a security expert (or the owner) employing a set of time and value constraints. The goal is to identify malicious behavior that other defensive technologies (e.g., antivirus or firewall) failed to detect. Since the abstraction derivation process is complex, the KBTA method was adapted for mobile devices that are limited in resources (i.e., CPU, memory, battery). To evaluate the proposed modified KBTA method a lightweight host-based intrusion detection system (HIDS), combined with central management capabilities for Android-based mobile phones, was developed. Evaluation results demonstrated the effectiveness of the new approach in detecting malicious applications on mobile devices (detection rate above 94% in most scenarios) and the feasibility of running such a system on mobile devices (CPU consumption was 3% on average).     

Of robot ants and elephants: A computational comparison

In the robotics community, there exist implicit assumptions concerning the computational capabilities of robots. Two computational classes of robots emerge as focal points of recent research: robot ants and robot elephants. Ants have poor memory and communication capabilities, but are able to communicate using pheromones, in effect, turning their work area into a shared memory. By comparison, elephants are computationally stronger, have large memory, and are equipped with strong sensing and communication capabilities. Unfortunately, not much is known about the relation between the capabilities of these models in terms of the tasks they can address. In this paper, we present formal models of both ants and elephants, and investigate if one dominates the other. We present two algorithms: AntEater, which allows elephant robots to execute ant algorithms and ElephantGun, which converts elephant algorithms-specified as Turing machines-into ant algorithms. By exploring the computational capabilities of these algorithms, we reach interesting conclusions regarding the computational power of both models.     

Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${\it root} \in V$, and where each edge $e \in E$ is endowed with a length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {\it transmission time} of $P$ is defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {\sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - \epsilon$ for any $\epsilon >0$. The {\sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 \over 2}-\epsilon$ for any $\epsilon >0$.