Displaying similar documents to “Census algorithms for chinese remainder pseudorank”

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

Rudolf Grübel (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

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 in question. Here we consider a variant where this element is the median of a sample of size from . 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.

Consistency checking within local search applied to the frequency assignment with polarization problem

Michel Vasquez, Audrey Dupont, Djamal Habet (2010)

RAIRO - Operations Research

Similarity:

We present a hybrid approach for the Frequency Assignment Problem with Polarization. This problem, viewed as Max-CSP, is treated as a sequence of decision problems, like. The proposed approach combines the Arc-Consistency techniques with a performed heuristic. The resulting algorithm gives some high quality solutions and has proved its robustness on instances with approximately a thousand variables and nearly ten thousand constraints.

A note on dual approximation algorithms for class constrained bin packing problems

Eduardo C. Xavier, Flàvio Keidi Miyazawa (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity , and items of different classes, each item with class and size . The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be...

New algorithms for coupled tasks scheduling – a survey

Jacek Blazewicz, Grzegorz Pawlak, Michal Tanas, Wojciech Wojciechowicz (2012)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various...

A sparse dynamic programming algorithm for alignment with non-overlapping inversions

Alair Pereira do Lago, Ilya Muchnik, Casimir Kulikowski (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions...

On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications

Evripidis Bampis, R. Giroudeau, J.-C. König (2010)

RAIRO - Operations Research

Similarity:

We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than (unless ). This result is an extension of the result of Hoogeveen  [CITE] who proved that there is no polynomial time -approximation algorithm with...

On the structure of (−)-integers

Wolfgang Steiner (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

The (−)-integers are natural generalisations of the -integers, and thus of the integers, for negative real bases. When is the analogue of a Parry number, we describe the structure of the set of (−)-integers by a fixed point of an anti-morphism.

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2010)

RAIRO - Operations Research

Similarity:

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem  which only differ on a linear transformation of their objective functions. This...

A note on a two dimensional knapsack problem with unloading constraints

Jefferson Luiz Moisés da Silveira, Eduardo Candido Xavier, Flávio Keidi Miyazawa (2013)

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

Similarity:

In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin , and a list of rectangular items, each item with a class value in {1,...,}. The problem is to pack a subset of into , maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item , items with higher class values can not block . We present a (4 + )-approximation algorithm when the bin is a square. We also present (3 + )-approximation...

Adaptive non-asymptotic confidence balls in density estimation

Matthieu Lerasle (2012)

ESAIM: Probability and Statistics

Similarity:

We build confidence balls for the common density of a real valued sample . We use resampling methods to estimate the projection of onto finite dimensional linear spaces and a model selection procedure to choose an optimal approximation space. The covering property is ensured for all  ≥ 2 and the balls are adaptive over a collection of linear spaces.

Fast approximation of minimum multicast congestion – Implementation VERSUS Theory

Andreas Baltz, Anand Srivastav (2010)

RAIRO - Operations Research

Similarity:

The problem of minimizing the maximum edge congestion in a multicast communication network generalizes the well-known -hard multicommodity flow problem. We give the presently best theoretical approximation results as well as efficient implementations. In particular we show that for a network with edges and multicast requests, an OPT + exp(1)ln)-approximation can be computed in lnln) time, where  bounds the time for computing an -approximate minimum Steiner tree. Moreover, we present...