Creating and sharing knowledge for telecommunications

Randomized Approximate Scheduling in Multi Hop Networks

on 13-12-2010

... Throughput optimal routing algorithms, first purposed by Tassiulas and Ephremides in 1992, rely in solving a maximization problem that, in general and depending on the particular interference model and degrees of freedom, is in NP-complete.

Two non-optimal scheduling algorithms with provable performance bounds will be explored and a simple randomization technique is introduced such that the average performance of both techniques is improved.

More Information..

Tree Search and Quantum Computation

on 26-11-2010

... Luís Tarrataca (IST-UTL).

November 26, 2010, Friday, 15h.
Location: Room P4.35, Post-Graduation Building, IST.

Abstract: Traditional tree search algorithms supply a blueprint for modeling problem solving behaviour. A diverse spectrum of problems can be formulated in terms of tree search. Quantum computation, namely Grover’s algorithm, has aroused a great deal of interest since it allows for a quadratic speedup to be obtained in search procedures. In this work we consider the impact of incorporating classical search concepts alongside Grover’s algorithm into a hybrid quantum search system. Some of the crucial points examined include: (1) the reverberations of contemplating the use of non-constant branching factors; (2) determining the consequences of incorporating an heuristic perspective into a quantum tree search model. Joint work with Andreas Wichert. More Information..