Displaying similar documents to “Block Factorization of Hankel Matrices and Euclidean Algorithm”

Computing and proving with pivots

Frédéric Meunier (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

A simple idea used in many combinatorial algorithms is the idea of . Originally, it comes from the method proposed by Gauss in the 19th century for solving systems of linear equations. This method had been extended in 1947 by Dantzig for the famous simplex algorithm used for solving linear programs. From since, a pivoting algorithm is a method exploring subsets of a ground set and going from one subset to a new one ′ by deleting an element inside and adding an element outside : ′ =  ...

Universality in the bulk of the spectrum for complex sample covariance matrices

Sandrine Péché (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider complex sample covariance matrices = (1/)* where is a × random matrix with i.i.d. entries , 1 ≤ ≤ , 1 ≤ ≤ , with distribution . Under some regularity and decay assumptions on , we prove universality of some local eigenvalue statistics in the bulk of the spectrum in the limit where → ∞ and lim→∞ / = for any real number ∈ (0, ∞).

Analysis of a near-metric TSP approximation algorithm

Sacha Krug (2013)

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

Similarity:

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the -metric traveling salesman problem ( -TSP), , the TSP restricted to graphs satisfying the -triangle inequality ({}) ≤ (({}) + ({})), for some cost function and any three vertices . The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3 /2 and is the best known algorithm for the -TSP, for 1 ≤  ≤ 2....

Interpolants d'Hermite obtenus par subdivision

Jean-Louis Merrien (2010)

ESAIM: Mathematical Modelling and Numerical Analysis

Similarity:

We propose a two point subdivision scheme with parameters to draw curves that satisfy Hermite conditions at both ends of . We build three functions and on dyadic numbers and, using infinite products of matrices, we prove that, under assumptions on the parameters, these functions can be extended by continuity on , with and .

A note on constructing infinite binary words with polynomial subword complexity

Francine Blanchet-Sadri, Bob Chen, Sinziana Munteanu (2013)

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

Similarity:

Most of the constructions of infinite words having polynomial subword complexity are quite complicated, , sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words over a binary alphabet  {  }  with polynomial subword complexity . Assuming contains an infinite number of ’s, our method is based on the gap function which gives the distances between consecutive ’s. It is known that...

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...

Hereditary properties of words

József Balogh, Béla Bollobás (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Let be a hereditary property of words, , an infinite class of finite words such that every subword (block) of a word belonging to is also in . Extending the classical Morse-Hedlund theorem, we show that either contains at least words of length for every  or, for some , it contains at most words of length for every . More importantly, we prove the following quantitative extension of this result: if has words of length then, for every , it contains at most ⌈( + 1)/2⌉⌈( + 1)/2⌈...

Pointwise constrained radially increasing minimizers in the quasi-scalar calculus of variations

Luís Balsa Bicho, António Ornelas (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

We prove of vector minimizers () =  (||) to multiple integrals ∫ ((), |()|)  on a  ⊂ ℝ, among the Sobolev functions (·) in + (, ℝ), using a  : ℝ×ℝ → [0,∞] with (·) and . Besides such basic hypotheses, (·,·) is assumed to satisfy also...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine...