Complexité dans le pire des cas

Science formelle
Informatique théorique
Theory of computation
Théorie de la complexité (i...

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (29)

Practicality and time complexity of a sparsified RNA folding algorithm

Philipp Bucher, Slavica Dimitrieva Janeva

Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n^3). Recently, it has been claimed that RNA folding can be achie ...

2012

Prediction of Multipactor Breakdown for Multicarrier Applications: The Quasi-Stationary Method

Michael Mattes

A new prediction algorithm for multipactor breakdown determination in multicarrier signals is presented. This new algorithm assumes a quasi-stationary (QS) model based on the nonstationary theory for single-carrier signals. It determines the worst case, i. ...

Institute of Electrical and Electronics Engineers2012

A Game Theoretic Approach to Expander-based Compressive Sensing

Volkan Cevher, Sina Jafarpour

We consider the following expander-based compressive sensing (e-CS) problem: Given Φ ∈ ℝM×N (M

IEEE2011

Fast Computation of Small Cuts via Cycle Space Sampling

David Pritchard

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space iden ...

2011

Silence-Based Communication

Christina Fragouli

Communication complexity---the minimum amount of communication required---of computing a function of data held by several parties is studied. A communication model where silence is used to convey information is introduced. For this model the worst-case and ...

2010

Pruned Continuous Haar Transform of 2D Polygonal Patterns with Application to VLSI Layouts

Paul Hurley, Robin Scheibler, Amina Chebira

We introduce an algorithm for the efﬁcient computation of the continuous Haar transform of 2D patterns that can be described by polygons. These patterns are ubiquitous in VLSI processes where they are used to describe design and mask layouts. There speed i ...

2010

Influence of the mechanical limitations of a traction system on energy storage design

Philippe Barrade

An innovative subway without supply rail is presented. This article deals with the sizing of the required on-board energy between two stations in the worst case. The influence of the mechanical limitations is studied: acceleration, jerk and torque limitati ...

Elsevier2010

Real-time input-constrained MPC using fast gradient methods

Colin Neil Jones

Linear quadratic model predictive control (MPC) with input constraints leads to an optimization problem that has to be solved at every instant in time. Although there exists computational complexity analysis for current online optimization methods dedicate ...

IEEE2009

An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling

Thomas Rothvoss

We introduce the "First Fit Matching Periods" algorithm for static-priority multiprocessor scheduling of periodic tasks with implicit deadlines and show that it yields asymptotically optimal processor assignments if utilization values are chosen uniformly ...

Springer2009

Page 2 sur 2