Archives for 2003

Today I read a paper titled “Aging, double helix and small world property in genetic algorithms”

The abstract is:
Over a quarter of century after the invention of genetic algorithms and miriads of their modifications, as well as successful implementations, we are still lacking many essential details of thorough analysis of it’s inner working.

One of such fundamental questions is: how many generations do we need to solve the optimization problem? This paper tries to answer this question, albeit in a fuzzy way, making use of the double helix concept.

As a byproduct we gain better understanding of the ways, in which the genetic algorithm may be fine tuned.

Today I read a paper titled “On-Line File Caching”

The abstract is:
In the on-line file-caching problem problem, the input is a sequence of requests for files, given on-line (one at a time).

Each file has a non-negative size and a non-negative retrieval cost.

The problem is to decide which files to keep in a fixed-size cache so as to minimize the sum of the retrieval costs for files that are not in the cache when requested.

The problem arises in web caching by browsers and by proxies.

This paper describes a natural generalization of LRU called Landlord and gives an analysis showing that it has an optimal performance guarantee (among deterministic on-line algorithms).

The paper also gives an analysis of the algorithm in a so-called “loosely” competitive model, showing that on a “typical” cache size, either the performance guarantee is O(1) or the total retrieval cost is insignificant.

Today I read a paper titled “The Self-Organizing Symbiotic Agent”

The abstract is:
In [N.

A.

Baas, Emergence, Hierarchies, and Hyper-structures, in C.G.

Langton ed., Artificial Life III, Addison Wesley, 1994.] a general framework for the study of Emergence and hyper-structure was presented.

This approach is mostly concerned with the description of such systems.

In this paper we will try to bring forth a different aspect of this model we feel will be useful in the engineering of agent based solutions, namely the symbiotic approach.

In this approach a self-organizing method of dividing the more complex “main-problem” to a hyper-structure of “sub-problems” with the aim of reducing complexity is desired.

A description of the general problem will be given along with some instances of related work.

This paper is intended to serve as an introductory challenge for general solutions to the described problem.

Today I read a paper titled “Solitaire Clobber”

The abstract is:
Clobber is a new two-player board game.

In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white and black moves.

We show that a checkerboard configuration on a single row (or single column) can be reduced to about n/4 stones.

For boards with at least two rows and two columns, we show that a checkerboard configuration can be reduced to a single stone if and only if the number of stones is not a multiple of three, and otherwise it can be reduced to two stones.

We also show that in general it is NP-complete to decide whether an arbitrary Clobber configuration can be reduced to a single stone..

Today I read a paper titled “Construction of an algorithm in parallel for the Fast Fourier Transform”

The abstract is:
It has been designed,built and executed a code for the Fast Fourier Transform (FFT),compiled and executed in a cluster of 2^n computers under the operating system MacOS and using the routines MacMPI.

As practical application,the code has been used to obtain the transformed from an astronomic imagen,to execute a filter on its and with a transformed inverse to recover the image with the variates given by the filter.The computers arrangement are installed in the Observatorio Astronomico National in Colombia under the name OAN Cluster and in this has been executed several applications.

Today I read a paper titled “The Lazy Bureaucrat Scheduling Problem”

The abstract is:
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks.

A typical worker’s objective is to minimize the amount of work he does (he is “lazy”), or more generally, to schedule as inefficiently (in some sense) as possible.

The worker is subject to the constraint that he must be busy when there is work that he can do; we make this notion precise both in the preemptive and nonpreemptive settings.

The resulting class of “perverse” scheduling problems, which we denote “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules.

Today I read a paper titled “Genetic Algorithms for Extension Search in Default Logic”

The abstract is:
A default theory can be characterized by its sets of plausible conclusions, called its extensions.

But, due to the theoretical complexity of Default Logic (Sigma_2p-complete), the problem of finding such an extension is very difficult if one wants to deal with non trivial knowledge bases.

Based on the principle of natural selection, Genetic Algorithms have been quite successfully applied to combinatorial problems and seem useful for problems with huge search spaces and when no tractable algorithm is available.

The purpose of this paper is to show that techniques issued from Genetic Algorithms can be used in order to build an efficient default reasoning system.

After providing a formal description of the components required for an extension search based on Genetic Algorithms principles, we exhibit some experimental results.

Today I read a paper titled “One-Dimensional Peg Solitaire”

The abstract is:
We solve the problem of one-dimensional peg solitaire.

In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that a linear-time algorithm exists for reducing any configuration to the minimum number of pegs..

Today I read a paper titled “Reducing Randomness via Irrational Numbers”

The abstract is:
We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero.

The methodology evaluates the polynomial at efficiently computable approximations of suitable irrational points.

In contrast to the classical technique of DeMillo, Lipton, Schwartz, and Zippel, this methodology can decrease the error probability by increasing the precision of the approximations instead of using more random bits.

Consequently, randomized algorithms that use the classical technique can generally be improved using the new methodology.

To demonstrate the methodology, we discuss two nontrivial applications.

The first is to decide whether a graph has a perfect matching in parallel.

Our new NC algorithm uses fewer random bits while doing less work than the previously best NC algorithm by Chari, Rohatgi, and Srinivasan.

The second application is to test the equality of two multisets of integers.

Our new algorithm improves upon the previously best algorithms by Blum and Kannan and can speed up their checking algorithm for sorting programs on a large range of inputs.

Today I read a paper titled “Robustness of Regional Matching Scheme over Global Matching Scheme”

The abstract is:
The paper has established and verified the theory prevailing widely among image and pattern recognition specialists that the bottom-up indirect regional matching process is the more stable and the more robust than the global matching process against concentrated types of noise represented by clutter, outlier or occlusion in the imagery.

We have demonstrated this by analyzing the effect of concentrated noise on a typical decision making process of a simplified two candidate voting model where our theorem establishes the lower bounds to a critical breakdown point of election (or decision) result by the bottom-up matching process are greater than the exact bound of the global matching process implying that the former regional process is capable of accommodating a higher level of noise than the latter global process before the result of decision overturns.

We present a convincing experimental verification supporting not only the theory by a white-black flag recognition problem in the presence of localized noise but also the validity of the conjecture by a facial recognition problem that the theorem remains valid for other decision making processes involving an important dimension-reducing transform such as principal component analysis or a Gabor transform.