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

Page 1 Next

Displaying 1 – 20 of 37

Showing per page

Scheduling in the presence of processor networks : complexity and approximation

Vincent Boudet, Johanne Cohen, Rodolphe Giroudeau, Jean-Claude König (2012)

RAIRO - Operations Research

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...

Scheduling in the presence of processor networks : complexity and approximation

Vincent Boudet, Johanne Cohen, Rodolphe Giroudeau, Jean-Claude König (2012)

RAIRO - Operations Research

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...

Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.

Thomas Lickteig, Klaus Meer (1997)

Revista Matemática de la Universidad Complutense de Madrid

We study matrix calculations such as diagonalization of quadratic forms under the aspect of additive complexity and relate these complexities to the complexity of matrix multiplication. While in Bürgisser et al. (1991) for multiplicative complexity the customary thick path existence argument was sufficient, here for additive complexity we need the more delicate finess of the real spectrum (cf. Bochnak et al. (1987), Becker (1986), Knebusch and Scheiderer (1989)) to obtain a complexity relativization....

Signed bits and fast exponentiation

Wieb Bosma (2001)

Journal de théorie des nombres de Bordeaux

An exact analysis is given of the benefits of using the non-adjacent form representation for integers (rather than the binary representation), when computing powers of elements in a group in which inverting is easy. By counting the number of multiplications for a random exponent requiring a given number of bits in its binary representation, we arrive at a precise version of the known asymptotic result that on average one in three signed bits in the non-adjacent form is non-zero. This shows that...

Similarity relations and cover automata

Jean-Marc Champarnaud, Franck Guingne, Georges Hansel (2005)

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

Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained as immediate...

Similarity relations and cover automata

Jean-Marc Champarnaud, Franck Guingne, Georges Hansel (2010)

RAIRO - Theoretical Informatics and Applications

Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained as immediate...

Simulation and design of extraction and separation fluidic devices

Bijan Mohammadi, Juan G. Santiago (2001)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

We present the combination of a state control and shape design approaches for the optimization of micro-fluidic channels used for sample extraction and separation of chemical species existing in a buffer solution. The aim is to improve the extraction and identification capacities of electroosmotic micro-fluidic devices by avoiding dispersion of the extracted advected band.

Simulation and design of extraction and separation fluidic devices

Bijan Mohammadi, Juan G. Santiago (2010)

ESAIM: Mathematical Modelling and Numerical Analysis

We present the combination of a state control and shape design approaches for the optimization of micro-fluidic channels used for sample extraction and separation of chemical species existing in a buffer solution. The aim is to improve the extraction and identification capacities of electroosmotic micro-fluidic devices by avoiding dispersion of the extracted advected band.

Solving conics over function fields

Mark van Hoeij, John Cremona (2006)

Journal de Théorie des Nombres de Bordeaux

Let F be a field whose characteristic is not  2 and K = F ( t ) . We give a simple algorithm to find, given a , b , c ∈ K * , a nontrivial solution in  K (if it exists) to the equation a X 2 + b Y 2 + c Z 2 = 0 . The algorithm requires, in certain cases, the solution of a similar equation with coefficients in F ; hence we obtain a recursive algorithm for solving diagonal conics over ℚ ( t 1 , ⋯ , t n ) (using existing algorithms for such equations over  ℚ ) and over 𝔽 q ( t 1 , ⋯ , t n ) .

Solving maximum independent set by asynchronous distributed hopfield-type neural networks

Giuliano Grossi, Massimo Marchi, Roberto Posenato (2006)

RAIRO - Theoretical Informatics and Applications

We propose a heuristic for solving the maximum independent set problem for a set of processors in a network with arbitrary topology. We assume an asynchronous model of computation and we use modified Hopfield neural networks to find high quality solutions. We analyze the algorithm in terms of the number of rounds necessary to find admissible solutions both in the worst case (theoretical analysis) and in the average case (experimental Analysis). We show that our heuristic is better than the...

Solving word equations

Habib Abdulrab (1990)

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

Currently displaying 1 – 20 of 37

Page 1 Next