Concept

Comparaison asymptotique

Publications associées (72)

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

Direct data-driven H2 − H∞ loop-shaping

Alireza Karimi

In this paper, a direct data-driven approach is proposed to tune fixed-order controllers for unknown stable LTI plants in a mixed-sensitivity loop-shaping problem. The method requires a single set of input-output samples and it is based on simple convex op ...

2011

Lower Bounds on the Area Requirements of Series-Parallel Graphs

Fabrizio Frati

We show that there exist series-parallel graphs requiring Omega(n2(root log n)) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K-2,K-n, one side ...

2011

The complexity of robust atomic storage

Rachid Guerraoui, Marko Vukolic

We study the time-complexity of robust atomic read/write storage from fault-prone storage components in asynchronous message-passing systems. Robustness here means wait-free tolerating the largest possible number t of Byzantine storage component failures ( ...

ACM Press2011

Optimal selection of customers for a last-minute offer

Thomas Rothvoss

We analyze a short-term revenue optimization problem that involves the optimal targeting of customers for a promotion in which a finite number of perishable items are sold on a last-minute offer. The goal is to select the subset of customers to whom the of ...

Informs2010

A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks

Thomas Rothvoss

We present a new approximation algorithm for rate-monotonic multiprocessor scheduling of periodic tasks with implicit deadlines. We prove that for an arbitrary parameter k it yields solutions with at most (3/2 + 1/k)*OPT+9k many processors, thus it gives a ...

Springer2010

On growth and torsion of groups

We give a subexponential upper bound and a superpolynomial lower bound on the growth function of the Fabrykowski-Gupta group. ...

2009

A representation formula for the voltage perturbations caused by diametrically small conductivity inhomogeneities. Proof of uniform validity

Hoài-Minh Nguyên

We revisit the asymptotic formulas originally derived in [D.J. Cedio-Fengya, S. Moskow, M.S. Vogelius, Identification of conductivity imperfections of small diameter by boundary measurements. Continuous dependence and computational reconstruction, Inverse ...

2009

Chasing the Weakest System Model for Implementing Omega and Consensus

Martin Hutle

Aguilera et al. and Malkhi et al. presented two system models, which are weaker than all previously proposed models where the eventual leader election oracle Omega can be implemented, and thus, consensus can also be solved. The former model assumes unicast ...

2009

Extended Navigability of Small World Networks: Exact Results and New Insights

Paolo De Los Rios, Cécile Caretta Cartozo

Navigability of networks, that is, the ability to find any given destination vertex starting from any other vertex, is crucial to their usefulness. In 2000 Kleinberg showed that optimal navigability could be achieved in small world networks provided that a ...

American Physical Society2009

Indifference Pricing for Power Utilities

Semyon Malamud

We study utility indiﬀerence pricing of claim streams with intertem- poral consumption and power (CRRA) utilities. We derive explicit for- mulas for the derivatives of the utility indiﬀerence price with respect to claims and wealth. The simple structure of ...

2009