Publications associées à The weighted averages algorithm revisited

Publications associées (43)

The Cost of Consistency: Submodular Maximization with Constant Recourse

In this work, we study online submodular maximization and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible approximation ratio that is attainable when the algorithm is allowe ...

ACM2025

Near-optimal hierarchical matrix approximation from matrix-vector products

Ulf David Persson

We describe a randomized algorithm for producing a near-optimal hierarchical off-diagonal low-rank (HODLR) approximation to an n × n matrix A, accessible only though matrix-vector products with A and AT. We prove that, for the rank-k HODLR approximation pr ...

Society for Industrial and Applied Mathematics2025

On the conjugate symmetry and sparsity of the harmonic decomposition of parametric surfaces with the randomised Kaczmarz method

Katrin Beyer

This limitation is circumvented by using scalable and non–memory–intensive harmonic expansions. In this paper, the projection of parametric surfaces onto disk and spherical harmonics bases is investigated, and three novel computationally efficient algorith ...

2024

Energy-Aware Decentralized Learning with Intermittent Model Training

Anne-Marie Kermarrec, Rafael Pereira Pires, Rishi Sharma, Marinus Abraham de Vos, Akash Balasaheb Dhasade

SKIPTRAIN is a novel Decentralized Learning (DL) algorithm, which minimizes energy consumption in decentralized learning by strategically skipping some training rounds and substituting them with synchronization rounds. These trainingsilent periods, besides ...

IEEE2024

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

Yingying Ren

We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...

Association for Computing Machinery2024

COMPUTING FUNCTIONS OF SYMMETRIC HIERARCHICALLY SEMISEPARABLE MATRICES

Daniel Kressner

The aim of this work is to develop a fast algorithm for approximating the matrix function f(A) of a square matrix A that is symmetric and has hierarchically semiseparable (HSS) structure. Appearing in a wide variety of applications, often in the context of ...

2024

A ride time-oriented scheduling algorithm for dial-a-ride problems

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Pergamon-Elsevier Science Ltd2024

Adaptive projected variational quantum dynamics

Giuseppe Carleo, Stefano Barison, David Linteau

We propose an adaptive quantum algorithm to prepare accurate variational time evolved wave functions. The method is based on the projected variational quantum dynamics (pVQD) algorithm, that performs a global optimization with linear scaling in the number ...

Amer Physical Soc2024

Gibbs sampling the posterior of neural networks

Lenka Zdeborová, Emanuele Troiani, Giovanni Piccioli

In this paper, we study sampling from a posterior derived from a neural network. We propose a new probabilistic model consisting of adding noise at every pre- and post-activation in the network, arguing that the resulting posterior can be sampled using an ...

Iop Publishing Ltd2024

Distributed Shadow Dynamic Consensus Optimization Framework for Power Market with Parameterization Bidding Strategy of GENCOs

Liying Yu, Sidi-Rachid Cherkaoui

This paper presents a distributed shadow dynamic consensus (DSDC) framework to address the generation company (GENCO) strategic bidding problem in the independent system operator (ISO) operation. First, each sub-group is defined according to the communicat ...

IEEE2023

Maximum Independent Set: Self-Training through Dynamic Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

2023

Retraction-based numerical methods for continuation, interpolation and time integration on manifolds

Axel Elie Joseph Séguin

The goal of this thesis is the development and the analysis of numerical methods for problems where the unknown is a curve on a smooth manifold. In particular, the thesis is structured around the three following problems: homotopy continuation, curve inter ...

EPFL2023

Online Network Source Optimization with Graph-Kernel MAB

Pascal Frossard

We propose Grab-UCB, a graph-kernelmulti-arms bandit algorithm to learn online the optimal source placement in large scale networks, such that the reward obtained from a priori unknown network processes is maximized. The uncertainty calls for online learni ...

Springer International Publishing Ag2023

HyperLogLog: Exponentially Bad in Adversarial Settings

Mathilde Aliénor Raynal

Computing the count of distinct elements in large data sets is a common task but naive approaches are memory-expensive. The HyperLogLog (HLL) algorithm (Flajolet et al., 2007) estimates a data set's cardinality while using significantly less memory than a ...

IEEE COMPUTER SOC2022

Bayesian reconstruction of memories stored in neural networks from their connectivity

Lenka Zdeborová, Florent Gérard Krzakala

The advent of comprehensive synaptic wiring diagrams of large neural circuits has created the field of connectomics and given rise to a number of open research questions. One such question is whether it is possible to reconstruct the information stored in ...

2023

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

Mahmoud S. M. Shaqfa

As historical stone masonry structures are vulnerable and prone to damage in earthquakes, investigating their structural integrity is important to reduce injuries and casualties while preserving their historical value. Stone masonry is a composite material ...

EPFL2022

An automatized method to determine latencies of motor-evoked potentials under physiological and pathophysiological conditions

Friedhelm Christoph Hummel, Takuya Morishita, Pierre Theopistos Vassiliadis, Andéol Geoffroy Cadic-Melchior, Claudia Bigoni

Background. Latencies of motor evoked potentials (MEPs) can provide insights into the motor neuronal pathways activated by transcranial magnetic stimulation. Notwithstanding its clinical relevance, accurate, unbiased methods to automatize latency detection ...

IOP Publishing Ltd2022

Phenomenological theory of variational quantum ground-state preparation

Ivano Tavernelli, Giuseppe Carleo

The variational approach is a cornerstone of computational physics, considering both conventional and quantum computing computational platforms. The variational quantum eigensolver algorithm aims to prepare the ground state of a Hamiltonian exploiting para ...

Amer Physical Soc2023

Formula Normalizations in Verification

Viktor Kuncak, Simon Guilloud, Dragana Milovancevic, Mario Bucev

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

2023