Publication

APPROXIMATING k-MEDIAN VIA PSEUDO-APPROXIMATION

Publications associées (28)

Assessing the value of kinetic results from biochemical methane potential tests: Reproducibility from a large inter-laboratory study

Kinetic information extracted from biochemical methane potential (BMP) tests is often reported but its value is unclear. Inter-laboratory reproducibility provides a useful indication of its value. Here we extracted estimates of the first-order rate constan ...

2022

On Approximations of Data-Driven Chance Constrained Programs over Wasserstein Balls

Daniel Kuhn, Wolfram Wiesemann, Zhi Chen

Distributionally robust chance constrained programs minimize a deterministic cost function subject to the satisfaction of one or more safety conditions with high probability, given that the probability distribution of the uncertain problem parameters affec ...

2023

Discrete Optimal Transport with Independent Marginals is #P-Hard

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

2023

Efficient geometric integrators for the linear and nonlinear time-dependent Schrödinger equation

Julien Roulet

Many physical and chemical reactions are driven by nonadiabatic processes, which imply the breakdown of the celebrated Born-Oppenheimer approximation. To understand these processes, experimentalists employ spectroscopic techniques. However, the obtained re ...

EPFL2022

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

Dynamic Personalized Ranking

Jérémie Rappaz

Personalized ranking methods are at the core of many systems that learn to produce recommendations from user feedbacks. Their primary objective is to identify relevant items from very large vocabularies and to assist users in discovering new content. These ...

EPFL2022

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...

ASSOC COMPUTING MACHINERY2021

Fair colorful k-center clustering

Ola Nils Anders Svensson, Xinrui Jia

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho aro ...

SPRINGER HEIDELBERG2022