Publications related to A (2+ε)-Approximation Algorithm for Metric 𝑘-Median

Related publications (6)

Robust Training and Verification of Deep Neural Networks

According to the proposed Artificial Intelligence Act by the European Comission (expected to pass at the end of 2023), the class of High-Risk AI Systems (Title III) comprises several important applications of Deep Learning like autonomous driving vehicles ...

EPFL2023

Decision-making algorithms for learning and adaptation with application to COVID-19 data

Ali H. Sayed

This work focuses on the development of a new family of decision-making algorithms for adaptation and learning, which are specifically tailored to decision problems and are constructed by building up on first principles from decision theory. A key observat ...

ELSEVIER2022

Sublinear Algorithms for Spectral Graph Clustering

Aidasadat Mousavifar

This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become prohibitively expensive. Processing modern datasets requir ...

EPFL2021

Probabilistic and temporal failure detectors for solving distributed problems

Rachid Guerraoui

Failure detectors (FD)s are celebrated for their modularity in solving distributed problems. Algorithms are constructed using FD building blocks. Synchrony assumptions to implement FDs are studied separately and are typically expressed as eventual guarante ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2021

Local Approximation of the Maximum Cut in Regular Graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints

Volkan Cevher, Ahmet Alacaoglu, Fabian Ricardo Latorre Gomez, Armin Eftekhari, Mehmet Fatih Sahin

We propose a practical inexact augmented Lagrangian method (iALM) for nonconvex problems with nonlinear constraints. We characterize the total computational complexity of our method subject to a verifiable geometric condition, which is closely related to t ...

2019