KLONOWSKI, Marek; PAJAK, Dominik

doi:10.1109/IPDPS.2012.98

Metadatos

Licencia de uso del documento

KLONOWSKI, Marek
Institute of Mathematics and Computer Science [Wroclaw] [IMCS]

PAJAK, Dominik
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]

Idioma

Communication dans un congrès

Este ítem está publicado en

IPDPS - 26th IEEE International Parallel and Distributed Processing Symposium, 2012-05-21, Shanghai. 2012-05-21p. 1057-1067

IEEE

Resumen en inglés

In this paper we introduce and analyse the λ-Alert problem: in a single hop radio network a subset of stations is activated. The aim of the protocol is to decide if the number of activated stations is greater or equal to λ. This problem is similar to the k-Selection problem. It can also be seen as an extension of the standard Alert problem. In our paper we consider the λ-Alert problem in various settings. We describe characteristics of oblivious and adaptive deterministic algorithms for the model with and without collision detection. We also show some results for randomized algorithms. In particular, we present a very efficient Las Vegas- type algorithm which is immune to an adversary.< Leer menos

Metadatos

Compartir este ítem

Licencia de uso del documento

Sin título

Idioma

Este ítem está publicado en

Resumen en inglés

URI

DOI

Orígen

Centros de investigación