Publications associées à Asymptotically optimal algorithm

An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity

This paper develops a new storage-optimal algorithm that provably solves almost all semidefinite programs (SDPs). This method is particularly effective for weakly constrained SDPs under appropriate regularity conditions. The key idea is to formulate an app ...

2021

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2020

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

Boi Faltings, Panayiotis Danassis

The next technological revolution will be interwoven to the proliferation of intelligent systems. As we bridge the gap between physical and cyber worlds, we will give rise to large-scale, multi-agent based technologies. A key challenge that cities of the f ...

IOS PRESS2020

High Performance Computing for gravitational lens modeling: Single vs double precision on GPUs and CPUs

Jean-Paul Richard Kneib, Markus Rexroth, Christoph Ernst René Schäfer

Strong gravitational lensing is a powerful probe of cosmology and the dark matter distribution. Efficient lensing software is already a necessity to fully use its potential and the performance demands will only increase with the upcoming generation of tele ...

ELSEVIER2020

Non-Exponential Variations for Classical Results in First Passage Percolation

Jacques Saliba

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges. We start by describing the asymptotic behavior of the diameter and the f ...

EPFL2020

Bound and Conquer: Improving Triangulation by Enforcing Consistency

Martin Vetterli, Adam James Scholefield, Alireza Ghasemi

We study the accuracy of triangulation in multi-camera systems with respect to the number of cameras. We show that, under certain conditions, the optimal achievable reconstruction error decays quadratically as more cameras are added to the system. Furtherm ...

2019

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Boi Faltings, Aris Filos Ratsikas, Panayiotis Danassis

We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on th ...

2019

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delt ...

IEEE COMPUTER SOC2019

Dependence properties of spatial rainfall extremes and areal reduction factors

Anthony Christopher Davison, Sebastian Engelke

Areal reduction factors (ARFs) transform an estimate of extreme rainfall at a point to an estimate of extreme rainfall over a spatial domain, and are commonly used in flood risk estimation. For applications such as the design of large infrastructure, dam s ...

2018

A design method for distributed luenberger observers

Colin Neil Jones, Francisco Fernandes Castro Rego

The paper addresses the problem of designing distributed observers for discrete linear time-invariant (LTI) systems with distributed sensor nodes subjected to bounded measurement noise. A solution is proposed in terms of a distributed LTI Luenberger observ ...

IEEE2018