The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We discuss a technique (named “the container method”) for enumeration problems. It was applied for obtaining upper bounds and asymptotically sharp estimates for the number of independent sets, codes, antichains in posets, sum-free sets, monotone boolean functions and so on. The container method works even the appropriate recurrent equalities are absent and the traditional generating function method...
By using heuristic analysis proposed in [WSA03], we investigate the dynamical behavior of greedy local search algorithms for satisfiability (SAT) problems. We observe that the difference between hard and easy instances is relatively small while there are enough places to be improved locally, and that the difference becomes crucial when all such places are processed. We also show that a tabu search...
We consider a cascade model of N different processors performing a distributed parallel simulation. The main goal of the study is to show that the long-time dynamics of the system have a cluster behaviour. To attack this problem we combine two methods: stochastic comparison and Foster–Lyapunov functions.
In the paper a totally polynomial algorithm for construction of the set of irreducible partial covers for the major part of set cover problems is considered.
Multiobjective (or multicriteria) optimization is a research area with rich history and under heavy investigation within Operations Research and Economics in the last 60 years [1,2]. Its object of study is to investigate solutions to combinatorial optimization problems that are evaluated under several objective functions – typically defined on multidimensional attribute (cost) vectors. In multiobjective...
We study the generation of finite probabilistic distributions by discrete transformations. By discrete transformation of distributions we mean the distribution of a random variable which is a function of the values of independent random variables with initial distributions. We propose an algorithm which allows to determine in polynomial time whether a given distribution is generated by a given set...
A main problem of “Follow the Perturbed Leader” strategies for online decision problems is that regret bounds are typically proven against oblivious adversary. In partial observation cases, it was not clear how to obtain performance guarantees against adaptive adversary, without worsening the bounds. We propose a conceptually simple argument to resolve this problem. Using this, a regret bound of ...
Two dimensional cutting and packing problems have applications in many manufacturing and job allocation problems. In particular, in VLSI floor planning problems and stock cutting problems, many simulated annealing and genetic algorithms based methods have been proposed in the last ten years. These researches have mainly been focused on finding efficient data structures for representing packing results...
The development and testing of software-based systems is an essential activity for the automotive industry. 50-70 software-based systems with different complexities and developed by various suppliers are installed in today’s premium vehicles, communicating with each other via different bus systems. The integration and testing of systems of this complexity is a very challenging task. The aim of testing...
The well-known ant colony optimization meta-heuristic is applied to design a new command to line-of-sight guidance law. In this regard, the lately developed continuous ant colony system is used to optimize the parameters of a pre-constructed fuzzy sliding mode controller. The performance of the resulting guidance law is evaluated at different engagement scenarios.
Previously it was shown by the author that it is possible to reduce obtaining of lower bounds on the complexity of Boolean functions for branching programs without restriction to obtaining of lower bounds on the complexity of minorants of the considered function for branching programs with restriction on the number of occurrences of a variable in a path (read-k-times branching programs). Theorems...
Two general-purpose metaheuristic algorithms for solving multiobjective stochastic combinatorial optimization problems are introduced: SP-ACO (based on the Ant Colony Optimization paradigm) which combines the previously developed algorithms S-ACO and P-ACO, and SPSA, which extends Pareto Simulated Annealing to the stochastic case. Both approaches are tested on random instances of a TSP with time windows...
We consider temporal aspects of self-replication and evolvability – in particular, the massively asynchronous parallel and distributed nature of living systems. Formal views of self-reproduction and time are surveyed, and a general asynchronization construction for automata networks is presented. Evolution and evolvability are distinguished, and the evolvability characteristics of natural and artificial...
Modular exponentiation is to compute xE for positive integers x, E, and N. It is an essential operation for various public-key cryptographic algorithms such as RSA, ElGamal and DSA, and it is crucial to develop fast modular exponentiation methods for efficient implementation of the above algorithms. To accelerate modular exponentiation, one can either speed up each...
In this paper, a Stochastic Dynamic Facility Location Problem (SDFLP) is formulated. In the first part, an exact solution method based on stochastic dynamic programming is given. It is only usable for small instances. In the second part a Monte Carlo based method for solving larger instances is applied, which is derived from the Sample Average Approximation (SAA) method.
We present a survey of the communication point of view for a complexity lower bounds proof technique for classical (deterministic, nondeterministic and randomized) and quantum models of branching programs.
The present paper deals with the problem of analyzing the value of a random Boolean expression. The expressions are constructed of Boolean operations and constants chosen independently at random with given probabilities. The dependence between the expression value probability and the constants’ probabilities is investigated for different sets of operations. The asymptotic behavior of this dependence...
In this paper, we present a new model of a cell formation problem (CFP) for a multi-period planning horizon where the product mix and demand are different in each period, but they are deterministic. As a consequence, the formed cells in the current period may be not optimal for the next period. This evolution results from reformulation of part families, manufacturing cells, and reconfiguration of...
Evolutionary Algorithms (EAs), biological inspired searching techniques, represent a research domain where theoretical proofs are still missing. Due to the lack of theoretical foundations, an extensive experimental work developed many variations of the basic model. Remarkable tendencies such as variable control parameters or parallel populations try to overcome the stagnation observed at the end of...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.