Concept

Division d'un polynôme

Publications associées (70)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

New Algorithms for Approximate Nash Equilibria in Bimatrix Games

We consider the problem of computing additively approximate Nash equilibria in noncooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. We first provide a simpler algorithm, that achie ...

2010

2D-TUCKER Is PPAD-Complete

Tucker's lemma states that if we triangulate the unit disc centered at the origin and color the vertices with {1, 1,2, 2} in an antipodal way (if vertical bar z vertical bar = 1, then the sum of the colors of z and -z is zero), then there must be an edge F ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

Approximate BDD Minimization by Weighted A*

Reduced ordered Binary Decision Diagrams (BDDs) are a data structure for efficient representation and manipulation of Boolean functions. They are frequently used in logic synthesis. The size of BDDs depends on a chosen variable ordering, i.e. the size may ...

Institute of Electrical and Electronics Engineers2009

Computational Performance of a Parallelized Three-Dimensional High-Order Spectral Element Toolbox

Michel Deville, Nicolas Fietier, Vincent Keller, Roland Bouffanais, Jonas Marcel Lätt, Christoph Bosshard, Sohrab Jairo Kehtari, Christian Clémençon

In this paper, a comprehensive performance review of all MPI-based high-order three-dimensional spectral element method C++ toolbox is presented. The focus is put on the performance evaluation of aspects with a particular emphasis on the parallel efficienc ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

Finite-element preconditioning of G-NI spectral methods

Alfio Quarteroni

Several old and new finite-element preconditioners for nodal-based spectral discretizations of −laplace(u) = f in the domain

\Omega = (-1, 1)^d

(d = 2 or 3), with Dirichlet or Neumann boundary conditions, are considered and compared in terms of bothcondi ...

2009

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Vaibhav Rajan, Krister Swenson

The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inv ...

Springer2009

Annihilating polynomials of excellent quadratic forms

If phi is an excellent form, then it is possible to use the dimensions of the higher complements of phi to obtain an annihilating polynomial of phi of low degree. The main result of this paper is the construction of such a polynomial with the help of metho ...

Birkhäuser-Verlag, Springer2008

Stability and Delay Bounds in Heterogeneous Networks of Aggregate Schedulers

Jean-Yves Le Boudec, Gianluca Rizzo

Aggregate scheduling is one of the most promising solutions to the issue of scalability in networks, like DiffServ networks and high speed switches, where hard QoS guarantees are required. For networks of FIFO aggregate schedulers, the main existing suffic ...

2008

Finding Hamiltonian circuits in quasi-adjoint graphs

Dominique de Werra, Benjamin Leroy-Beaulieu

This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothernnic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718-7291. This paper pr ...

2008

The stable set polytope of quasi-line graphs

Friedrich Eisenbrand, Gautier Stauffer

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even n ...

2008

Finite-element preconditioning of G-NI spectral methods

Alfio Quarteroni

Several old and new finite-element preconditioners for nodal-based spectral discretizations of −laplace(u) = f in the domain

\Omega = (-1, 1)^d

(d = 2 or 3), with Dirichlet or Neumann boundary conditions, are considered and compared in terms of bothcondi ...

2009