All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 3 Next

Displaying 41 – 60 of 76

Showing per page

On the complexity of the Shapley-Scarf economy with several types of goods

Katarína Cechlárová (2009)

Kybernetika

In the Shapley-Scarf economy each agent is endowed with one unit of an indivisible good (house) and wants to exchange it for another, possibly the most preferred one among the houses in the market. In this economy, core is always nonempty and a core allocation can be found by the famous Top Trading Cycles algorithm. Recently, a modification of this economy, containing Q >= 2 types of goods (say, houses and cars for Q=2) has been introduced. We show that if the number of agents is 2, a complete...

On the computational complexity of centers locating in a graph

Ján Plesník (1980)

Aplikace matematiky

It is shown that the problem of finding a minimum k -basis, the n -center problem, and the p -median problem are N P -complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal m -center problem is also N P -complete.

On the conjecture relating minimax and minimean complexity norms

Peter Růžička, Juraj Wiedermann (1979)

Aplikace matematiky

Using counterexample it has been shown that an algorithm which is minimax optimal and over all minimax optimal algorithms is minimean optimal and has a uniform behaviour need not to be minimean optimal.

On the median-of-k version of Hoare's selection algorithm

Rudolf Grübel (2010)

RAIRO - Theoretical Informatics and Applications

In Hoare's (1961) original version of the algorithm   the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.

On the number of iterations required by Von Neumann addition

Rudolf Grübel, Anke Reimers (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.

On the number of iterations required by Von Neumann addition

Rudolf Grübel, Anke Reimers (2010)

RAIRO - Theoretical Informatics and Applications

We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.

On the parallel complexity of the alternating Hamiltonian cycle problem

E. Bampis, Y. Manoussakis, I. Milis (2010)

RAIRO - Operations Research

Given a graph with colored edges, a Hamiltonian cycle is called alternating if its successive edges differ in color. The problem of finding such a cycle, even for 2-edge-colored graphs, is trivially NP-complete, while it is known to be polynomial for 2-edge-colored complete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We give a new characterization for such a graph admitting an alternating Hamiltonian cycle which allows...

Currently displaying 41 – 60 of 76