Concept

Best, worst and average case

Publications associées (32)

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

Price discrimination with robust beliefs

Thomas Alois Weber, Jun Han

This paper considers the problem of second-degree price discrimination when the type distribution is unknown or imperfectly specified by means of an ambiguity set. As robustness measure we use a performance index, equivalent to relative regret, which quant ...

2023

Efficient and Accurate Handling of Periodic Flows in Time-Sensitive Networks

Jean-Yves Le Boudec, Seyed Mohammadhossein Tabatabaee

Total Flow Analysis (TFA) is a method for the worst-case analysis of time-sensitive networks. It uses service curve characterizations of the network nodes and arrival curves of flows at their sources; for tractability, the latter are often taken to be line ...

2023

Beyond worst-case analysis, with or without predictions

Andreas Maggiori

In this thesis we design online combinatorial optimization algorithms for beyond worst-case analysis settings.In the first part, we discuss the online matching problem and prove that, in the edge arrival model, no online algorithm can achieve a competitive ...

EPFL2023

Revisiting adversarial training for the worst-performing class

Volkan Cevher, Grigorios Chrysos, Thomas Michaelsen Pethick

Despite progress in adversarial training (AT), there is a substantial gap between the topperforming and worst-performing classes in many datasets. For example, on CIFAR10, the accuracies for the best and worst classes are 74% and 23%, respectively. We argu ...

2023

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Vincent Gramoli, Seth Gilbert, Manuel José Ribeiro Vidigueira

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most f < n/3 failures, any solution t ...

2023

A combination technique for optimal control problems constrained by random PDEs

Fabio Nobile, Tommaso Vanzan

We present a combination technique based on mixed differences of both spatial approximations and quadrature formulae for the stochastic variables to solve efficiently a class of Optimal Control Problems (OCPs) constrained by random partial differential equ ...

EPFL2022

Label-Free C-Reactive Protein Si Nanowire FET Sensor Arrays With Super-Nernstian Back-Gate Operation

Mihai Adrian Ionescu, Yann Christophe Sprunger, Luca Capua, Felix Risch, Ron Gill, Aristea Grammoustianou

We present a CMOS-compatible double gate and label-free C-reactive protein (CRP) sensor, based on silicon on insulator (SOI) silicon nanowires arrays. We exploit a reference subtracted detection method and a super-Nernstian internal amplification given by ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds

Adam Teodor Polak, Marek Elias

We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between power-saving states of different energy consumption and wake-up costs. We d ...

2021

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Friedrich Eisenbrand, Moritz Andreas Venzin, Jana Tabea Cslovjecsek

We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search