Publications associées à Algorithmic paradigm

Cluster-and-Conquer: When Randomness Meets Graph Locality

K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by tr ...

IEEE COMPUTER SOC2021

A fast spectral divide-and-conquer method for banded matrices

Daniel Kressner, Ana Susnjara

Based on the spectral divide-and-conquer algorithm by Nakatsukasa and Higham [SIAM J. Sci. Comput., 35(3):A1325-A1349, 2013], we propose a new algorithm for computing all the eigenvalues and eigenvectors of a symmetric banded matrix with small bandwidth, w ...

WILEY2021

Data reduction for mixed integer linear programming in complex energy systems

François Maréchal, Luc Girardin, Julia Granacher, Luise Middelhauve, Natalija Ljubic

The task of optimally designing and scheduling energy systems with a high share of renewable energies is complex and computationally demanding. A widespread method for tackling this task is to apply mixed integer linear programming (MILP). Even though the ...

2021

Pareto-like sequential sampling heuristic for global optimisation

Katrin Beyer, Mahmoud S. M. Shaqfa

In this paper, we propose a simple global optimisation algorithm inspired by Pareto’s principle. This algorithm samples most of its solutions within prominent search domains and is equipped with a self-adaptive mechanism to control the dynamic tightening o ...

2021

Detection of Bad PMU Data using Machine Learning Techniques

Alexandra Cameron Karpilow, Sidi-Rachid Cherkaoui

This project presents a pre-State Estimation method for the detection of Bad Data (BD) in Phasor Measurement Units (PMUs) using correlation analysis and a Neural Network Classifier. Presented in this paper is the algorithm design, the steps for generating ...

IEEE2020

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

Mirrored Langevin Dynamics

Volkan Cevher, Paul Thierry Yves Rolland, Ya-Ping Hsieh, Ali Kavis

We consider the problem of sampling from constrained distributions, which has posed significant challenges to both non-asymptotic analysis and algorithmic design. We propose a unified framework, which is inspired by the classical mirror descent, to derive ...

2018

Noise-Resistant Particle Swarm Optimization for the Learning of Robust Obstacle Avoidance Controllers using a Depth Camera

Alcherio Martinoli, Inaki Navarro Oiza, Ezequiel Leonardo Di Mario

The Ranger robot was designed to interact with children in order to motivate them to tidy up their room. Its mechanical configuration, together with the limited field of view of its depth camera, make the learning of obstacle avoidance behaviors a hard pro ...

Ieee2016

A Low-Power Correlator for Wakeup Receivers with Algorithm Pruning through Early Termination

Andreas Peter Burg, Adam Shmuel Teman, Reza Ghanaatian Jahromi, Jeremy Hugues-Felix Constantin

A low-complexity, low-power digital correlator for wakeup receivers is presented. With the proposed algorithm, unnecessary computational cycles are dynamically pruned from the correlation using an early threshold check. For the algorithm, we provide a rigo ...

Ieee2016

An Algorithmic Framework for Mumford-Shah Regularization of Inverse Problems in Imaging

Martin Kurt Storath

The Mumford-Shah model is a very powerful variational approach for edge preserving regularization of image reconstruction processes. However, it is algorithmically challenging because one has to deal with a non-smooth and non-convex functional. In this pap ...

Iop Publishing Ltd2015

Anisotropic Interpolation of Sparse Generalized Image Samples

Michaël Unser, Aurélien Bourquard

Practical image-acquisition systems are often modeled as a continuous-domain prefilter followed by an ideal sampler, where generalized samples are obtained after convolution with the impulse response of the device. In this paper, our goal is to interpolate ...

Ieee-Inst Electrical Electronics Engineers Inc2013

Simultaneous Point Matching and 3D Deformable Surface Reconstruction

Pascal Fua, Appu Shaji, Aydin Varol

It has been shown that the 3D shape of a deformable surface in an image can be recovered by establishing correspondences between that image and a reference one in which the shape is known. These matches can then be used to set-up a convex optimization prob ...

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2010

Linking Pose and Motion

Pascal Fua, Andrea Fossati

Algorithms designed to estimate 3D pose in video sequences enforce temporal consistency but typically overlook an important source of information: The 3D pose of an object, be it rigid or articulated, has a direct influence on its direction of travel. In t ...

2008

New dynamic programming algorithms for the resource constrained shortest path problem

Matteo Salani

The resource constrained elementary shortest path problem (RCESPP) arises as a pricing subproblem in branch-and-price algorithms for vehicle-routing problems with additional constraints. We address the optimization of the RCESPP and we present and compare ...

2008

Global Solution of Dynamic Optimization and Mixed-Integer Dynamic Optimization

Benoît Chachuat

An overview of global methods for dynamic optimization and mixed-integer dynamic optimization (MIDO) is presented, with emphasis placed on the control parametrization approach. These methods consist of extending existing continuous and mixed-integer global ...

2006

Time-complexity bounds on agreement problems

Partha Dutta

In many distributed systems, designing an application that maintains consistency and availability despite failure of processes, involves solving some form of agreement. Not surprisingly, providing efficient agreement algorithms is critical for improving th ...

EPFL2005

Soft real-time analysis of asynchronous agreement algorithms using Petri nets

Nicoleta Sergent

A distributed algorithm comprises a collection of sequential-code entities, which are spread over different computers connected to a network. The process of designing a distributed algorithm is influenced by the assumptions we make on the computational env ...

EPFL1998