Dynamic Complexity Theory Revisited

Dynamic complexity investigates the required effort to maintain knowledge about a property of a structure under changing operations. This article introduces a refined notion of dynamic problems which takes the initial structure into account. It develops the basic structural complexity notions accordingly. It also shows that the dynamic version of the LOGCFL-complete problem D₂LREACH(acyclic) can be maintained with first-order updates.     

Truthful Approximation Mechanisms for Scheduling Selfish Related Machines

We consider the problem of scheduling jobs on related machines owned by selfish agents. We provide a 5-approximation deterministic truthful mechanism, the first deterministic truthful result for the problem. Previously, Archer and Tardos showed a 2-approximation randomized mechanism which is truthful in expectation only (a weaker notion of truthfulness). In case the number of machines is constant, we provide a deterministic Fully Polynomial-Time Approximation Scheme (FPTAS) and a suitable payment scheme that yields a truthful mechanism for the problem. This result, which is based on converting FPTAS to monotone FPTAS, improves a previous result of Auletta et al., who showed a (4 + ε)-approximation truthful mechanism.     

CODIRO: A New System for Obtaining Data Concerning Consumer Behavior Based on Data Factors of High Interest Determined by the Analyst

The aim of this paper is to propose a new system for the strategic use of customer data that includes and integrates such differing data sources as company databases, mobile telephone networks and Internet data and is a consumer research support system for the discovery of new marketing opportunities. This system, called CODIRO, will be discussed in this paper using a case study of the effects on sales of processed food product television commercials. A system for verifying the validity of consumer behavior models will also be described and discussed. Use of the CODIRO analysis system makes it easy to introduce, into the analytic model, consumer attitude changes and in-store data of many types that have not been used to measure advertising and promotional activity effectiveness in the past.     

An approach to efficient business intelligent system for financial prediction

A concept of business intelligent system for financial prediction is considered in this paper. It provides data needed for fast, precise and good business decision support to all levels of management. The aim of the project is the development of a new online analytical processing oriented on case-based reasoning (CBR) where a previous experience for every new problem is taken into account. Methodological aspects have been tested in practice as a part of the management information system development project of “Novi Sad Fair”. A case study of an improved application of CBR in prediction of future payments is discussed in the paper. This paper is originally presented at The International Conference on Hybrid Information Technology 2006, at the special session on “Intelligent Information Systems for Financial Engineering”, November 2006 in Cheju Island, Korea.     

Emergency department status boards: user-evolved artefacts for inter- and intra-group coordination

Large, easily viewed status boards are commonly used in some healthcare settings such as emergency departments, operating theaters, intensive care units, and inpatient wards. Because these artefacts were developed by front-line users, and have little to no supervisory or regulatory control, they offer valuable insights into the theories of work and hazard held by those users. Although the status boards case were locally developed over many years for within-group coordination, they have also become useful for between-group coordination across organizational boundaries. In this paper, we compare and contrast the use of such status boards in two disparate settings: a US emergency department, and a UK pediatric ward, and note striking similarities in their form and usage, despite the large differences in setting.     

A Critique of the ANSI Standard on Role-Based Access Control

In 2004, the American National Standards Institute approved the Role-Based Access Control standard to fulfill "a need among government and industry purchasers of information technology products for a consistent and uniform definition of role based access control (RBAC) features". Such uniform definitions give IT product vendors and customers a common and unambiguous terminology for RBAC features, which can lead to wider adoption of RBAC and increased productivity. However, the current ANSI RBAC Standard has several limitations, design flaws, and technical errors that, it unaddressed, could lead to confusions among IT product vendors and customers and to RBAC implementations with different semantics, thus defeating the standard's purpose.     

A note on the variance of rank-based selection strategies for genetic algorithms and genetic programming

This paper evaluates different forms of rank-based selection that are used with genetic algorithms and genetic programming. Many types of rank based selection have exactly the same expected value in terms of the sampling rate allocated to each member of the population. However, the variance associated with that sampling rate can vary depending on how selection is implemented. We examine two forms of tournament selection and compare these to linear rank-based selection using an explicit formula. Because selective pressure has a direct impact on population diversity, we also examine the interaction between selective pressure and different mutation strategies.     

Computing Minimal Multi-Homogeneous Bezout Numbers Is Hard

The multi-homogeneous Bezout number is a bound for the number of solutions of a system of multi-homogeneous polynomial equations, in a suitable product of projective spaces. Given an arbitrary, not necessarily multi-homogeneous, system, one can ask for the optimal multi-homogenization that would minimize the Bezout number. In this paper it is proved that the problem of computing, or even estimating, the optimal multi-homogeneous Bezout number is actually NP-hard. In terms of approximation theory for combinatorial optimization, the problem of computing the best multi-homogeneous structure does not belong to APX, unless P = NP. Moreover, polynomial-time algorithms for estimating the minimal multi-homogeneous Bezout number up to a fixed factor cannot exist even in a randomized setting, unless BPP ⫆ NP.