Concept

Best, worst and average case

Related publications (115)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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

Jamming in granular media

Michel Tsukahara

This thesis studies the phenomenon of jamming in granular media, such as when a salt shaker gets clogged. We use modern instrumentation, like X-ray synchrotron tomography, to look inside real jamming experiments. High performance computers allow simulating ...

EPFL2009

The Complexity of Obstruction-Free Implementations

Rachid Guerraoui, Hagit Albo Attiya

Obstruction-free implementations of concurrent ob jects are optimized for the common case where there is no step contention, and were recently advocated as a solution to the costs associated with synchronization without locks. In this paper, we study this ...

2009

Learning Rotational Features for Filament Detection

Pascal Fua, François Fleuret, Germán González Serrano

State-of-the-art approaches for detecting filament-like structures in noisy images rely on filters optimized for signals of a particular shape, such as an ideal edge or ridge. While these approaches are optimal when the image conforms to these ideal shapes ...

2009

The Wireless Synchronization Problem

Rachid Guerraoui, Seth Gilbert

In this paper, we study the wireless synchronization prob- lem which requires devices activated at different times on a congested single-hop radio network to synchronize their round numbering. We assume a collection of n synchronous devices with access to ...

2009

Preventing versus Curing: Avoiding Conflicts in Transactional Memories

Rachid Guerraoui, Aleksandar Dragojevic, Vasu Singh

Transactional memories are typically speculative and rely on contention managers to cure conflicts. This paper explores a complementary approach that prevents conflicts by scheduling transactions according to predictions on their access sets. We first expl ...

2009

Abstractions for asynchronous distributed computing with malicious players

Marko Vukolic

In modern distributed systems, failures are the norm rather than the exception. In many cases, these failures are not benign. Settings such as the Internet might incur malicious (also called Byzantine or arbitrary) behavior and asynchrony. As a result, and ...

EPFL2008

Towards a Theory of Robust Localization against Malicious Beacon Nodes

Murtuza Jadliwala

Localization in the presence of malicious beacon nodes is an important problem in wireless networks. Although significant progress has been made on this problem, some fundamental theoretical questions still remain unanswered: in the presence of malicious b ...

IEEE Computer Society2008

Average case analysis of sparse recovery with Thresholding: New bounds based on average dictionary coherence

Pierre Vandergheynst, Mohammad Golbabaee

This paper analyzes the performance of the simple thresholding algorithm for sparse signal representations. In particular, in order to be more realistic we introduce a new probabilistic signal model which assumes randomness for both the amplitude and also ...

2008