Publications related to Robust Maximization of Non-Submodular Objectives

Related publications (30)

Approximation Algorithms for Allocation and Network Design

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

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

Assessing real-world gait with digital technology? Validation, insights and recommendations from the Mobilise-D consortium

Kamiar Aminian, Anisoara Ionescu, Abolfazl Soltani

Background: Although digital mobility outcomes (DMOs) can be readily calculated from real-world data collected with wearable devices and ad-hoc algorithms, technical validation is still required. The aim of this paper is to comparatively assess and validat ...

BioMed Central2023

Data-Driven Control and Optimization under Noisy and Uncertain Conditions

Baiwei Guo

Control systems operating in real-world environments often face disturbances arising from measurement noise and model mismatch. These factors can significantly impact the perfor- mance and safety of the system. In this thesis, we aim to leverage data to de ...

EPFL2023

Stable parameterization of continuous and piecewise-linear functions

Michaël Unser, Alexis Marie Frederic Goujon, Joaquim Gonçalves Garcia Barreto Campos

Rectified-linear-unit (ReLU) neural networks, which play a prominent role in deep learning, generate continuous and piecewise-linear (CPWL) functions. While they provide a powerful parametric representation, the mapping between the parameter and function s ...

2023

Fairness and Explainability in Clustering Problems

Xinrui Jia

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

EPFL2023

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

An Accelerated First-Order Method for Non-convex Optimization on Manifolds

Christopher Arnold Criscitiello, Nicolas Boumal

We describe the first gradient methods on Riemannian manifolds to achieve accelerated rates in the non-convex case. Under Lipschitz assumptions on the Riemannian gradient and Hessian of the cost function, these methods find approximate first-order critical ...

SPRINGER2022

Tensor-Based Numerical Method For Stochastic Homogenization

Quentin Olivier Martin Ayoul--Guilmard

This paper addresses the complexity reduction of stochastic homogenization of a class of random materials for a stationary diffusion equation. A cost-efficient approximation of the correctors is obtained using a method designed to exploit quasi-periodicity ...

SIAM PUBLICATIONS2022

Derivative voltammetry: a simple tool to probe reaction selectivity in photoelectrochemical cells

Kevin Sivula, Florent Alexandre Boudoire, Nukorn Plainpan

We demonstrate the use of the derivative voltammogram method to predict the selectivity of the photo-driven oxidation of 5-hydroxymethylfurfural (HMF) on a WO3 photoanode as a function of applied potential using only information obtained from the linear sw ...

2022

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

Adam Teodor Polak

We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of w workers and a multiset T ⊆ [t] of |T| = w tasks, a memoryless worker-task assignment function is any function ϕ that assigns the workers ...

Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik2022

A Noise-Resistant Mixed-Discrete Particle Swarm Optimization Algorithm for the Automatic Design of Robotic Controllers

Alcherio Martinoli, Cyrill Silvan Baumann

The automatic design of well-performing robotic controllers is still an unsolved problem due to the inherently large parameter space and noisy, often hard-to-define performance metrics, especially when sequential tasks need to be accomplished. Distal contr ...

2022

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

Daniel Kuhn, Wolfram Wiesemann

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

Nothing New Under the Sun: Novelty Constructs and Measures in Social Studies

Davide Bavato

The concept of novelty is central to questions of creativity, innovation, and discovery. Despite the prominence in scientific inquiry and everyday discourse, there is a chronic ambiguity over its meaning and a surprising variety of empirical measures, whic ...

Emerald Publishing Limited2022

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Ola Nils Anders Svensson, Moran Feldman

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...

2021

Computational Design of Weingarten Surfaces

Mark Pauly, Davide Pellis

In this paper we study Weingarten surfaces and explore their potential for fabrication-aware design in freeform architecture. Weingarten surfaces are characterized by a functional relation between their principal curvatures that implicitly defines approxim ...

2021

A comment on performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

Maryam Kamgarpour, Baiwei Guo

We provide a counterexample to the performance guarantee obtained in the paper "Il'ev, V., Linker, N., 2006. Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid", which was published in Volume 171 of the Eur ...

ELSEVIER2021

Deterministic error bounds for kernel-based learning techniques under bounded noise

Colin Neil Jones, Emilio Maddalena, Paul Scharnhorst

We consider the problem of reconstructing a function from a finite set of noise-corrupted samples. Two kernel algorithms are analyzed, namely kernel ridge regression and epsilon-support vector regression. By assuming the ground-truth function belongs to th ...

2021

A New Channel-Base Lightning Current Formula With Analytically Adjustable Parameters

Farhad Rachidi-Haeri

The article provides a new channel-based current function, which aims at faithfully reproducing the salient parameters of lightning currents. All the model parameters can be set in a fully analytical way, guaranteeing the possibility of changing them (acco ...

2021

Local Vulnerabilities and Global Robustness of Coupled Dynamical Systems on Complex Networks

Melvyn Sandy Tyloo

Coupled dynamical systems are omnipresent in everyday life. In general, interactions between individual elements composing the system are captured by complex networks. The latter greatly impact the way coupled systems are functioning and evolving in time. ...

EPFL2020