Author name cluster

Ziyad Benomar

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

NeurIPS Conference 2025 Conference Paper

Non-Clairvoyant Scheduling with Progress Bars

Ziyad Benomar
Romain Cosson
Alexander Lindermayr
Jens Schlöter

In non-clairvoyant scheduling, the goal is to minimize the total job completion time without prior knowledge of individual job processing times. This classical online optimization problem has recently gained attention through the framework of learning-augmented algorithms. We introduce a natural setting in which the scheduler receives continuous feedback in the form of progress bars—estimates of the fraction of each job completed over time. We design new algorithms for both adversarial and stochastic progress bars and prove strong competitive bounds. Our results in the adversarial case surprisingly induce improved guarantees for learning-augmented scheduling with job size predictions. We also introduce a general method for combining scheduling algorithms, yielding further insights in scheduling with predictions. Finally, we propose a stochastic model of progress bars as a more optimistic alternative to conventional worst-case models, and present an asymptotically optimal scheduling algorithm in this setting.

PDF Details

ICML Conference 2025 Conference Paper

Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search

Ziyad Benomar
Lorenzo Croissant
Vianney Perchet
Spyros Angelopoulos 0001

One-max search is a classic problem in online decision-making, in which a trader acts on a sequence of revealed prices and accepts one of them irrevocably to maximise its profit. The problem has been studied both in probabilistic and in worst-case settings, notably through competitive analysis, and more recently in learning-augmented settings in which the trader has access to a prediction on the sequence. However, existing approaches either lack smoothness, or do not achieve optimal worst-case guarantees: they do not attain the best possible trade-off between the consistency and the robustness of the algorithm. We close this gap by presenting the first algorithm that simultaneously achieves both of these important objectives. Furthermore, we show how to leverage the obtained smoothness to provide an analysis of one-max search in stochastic learning-augmented settings which capture randomness in both the observed prices and the prediction.

Details

NeurIPS Conference 2024 Conference Paper

Addressing Bias in Online Selection with Limited Budget of Comparisons

Ziyad Benomar
Evgenii Chzhen
Nicolas Schreuder
Vianney Perchet

Consider a hiring process with candidates coming from different universities. It is easy to order candidates with the same background, yet it can be challenging to compare them otherwise. The latter case requires additional costly assessments, leading to a potentially high total cost for the hiring organization. Given an assigned budget, what would be an optimal strategy to select the most qualified candidate? We model the above problem as a multicolor secretary problem, allowing comparisons between candidates from distinct groups at a fixed cost. Our study explores how the allocated budget enhances the success probability of online selection algorithms.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Learning-Augmented Priority Queues

Ziyad Benomar
Christian Coester

Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is to efficiently support the insertion of new elements with assigned priorities and the extraction of the highest priority element. In this study, we investigate the design of priority queues within the learning-augmented framework, where algorithms use potentially inaccurate predictions to enhance their worst-case performance. We examine three prediction models spanning different use cases, and we show how the predictions can be leveraged to enhance the performance of priority queue operations. Moreover, we demonstrate the optimality of our solution and discuss some possible applications.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Lookback Prophet Inequalities

Ziyad Benomar
Dorian Baudry
Vianney Perchet

Prophet inequalities are fundamental optimal stopping problems, where a decision-maker observes sequentially items with values sampled independently from known distributions, and must decide at each new observation to either stop and gain the current value or reject it irrevocably and move to the next step. This model is often too pessimistic and does not adequately represent real-world online selection processes. Potentially, rejectesd items can be revisited and a fraction of their value can be recovered. To analyze this problem, we consider general decay functions $D_1, D_2, \ldots$, quantifying the value to be recovered from a rejected item, depending on how far it has been observed in the past. We analyze how lookback improves, or not, the competitive ratio in prophet inequalities in different order models. We show that, under mild monotonicity assumptions on the decay functions, the problem can be reduced to the case where all the decay functions are equal to the same function $x \mapsto \gamma x$, where $\gamma = \inf_{x>0} \inf_{j \geq 1} D_j(x)/x$. Consequently, we focus on this setting and refine the analyses of the competitive ratios, with upper and lower bounds expressed as increasing functions of $\gamma$.

PDF Details DOI

ICML Conference 2024 Conference Paper

Non-clairvoyant Scheduling with Partial Predictions

Ziyad Benomar
Vianney Perchet

The non-clairvoyant scheduling problem has gained new interest within learning-augmented algorithms, where the decision-maker is equipped with predictions without any quality guarantees. In practical settings, access to predictions may be reduced to specific instances, due to cost or data limitations. Our investigation focuses on scenarios where predictions for only $B$ job sizes out of $n$ are available to the algorithm. We first establish near-optimal lower bounds and algorithms in the case of perfect predictions. Subsequently, we present a learning-augmented algorithm satisfying the robustness, consistency, and smoothness criteria, and revealing a novel tradeoff between consistency and smoothness inherent in the scenario with a restricted number of predictions.

Details

NeurIPS Conference 2023 Conference Paper

Advice Querying under Budget Constraint for Online Algorithms

Ziyad Benomar
Vianney Perchet

Several problems have been extensively studied in the learning-augmented setting, where the algorithm has access to some, possibly incorrect, predictions. However, it is assumed in most works that the predictions are provided to the algorithm as input, with no constraint on their size. In this paper, we consider algorithms with access to a limited number of predictions, that they can request at any time during their execution. We study three classical problems in competitive analysis, the ski rental problem, the secretary problem, and the non-clairvoyant job scheduling. We address the question of when to query predictions and how to use them.

PDF Details

AAMAS Conference 2022 Conference Paper

Agent-based Modeling and Simulation for Malware Spreading in D2D Networks

Ziyad Benomar
Chaima Ghribi
Elie Cali
Alexander Hinsen
Benedikt Jahnel

This paper presents a new multi-agent model for simulating malware propagation in device-to-device (D2D) 5G networks. This model allows to understand and analyze mobile malware-spreading dynamics in such highly dynamical networks. Additionally, we present a theoretical study to validate and benchmark our proposed approach for some basic scenarios that are less complicated to model mathematically and also to highlight the key parameters of the model. Our simulations identify critical thresholds for "no propagation" and for "maximum malware propagation" and make predictions on the malware-spread velocity as well as deviceinfection rates. To the best of our knowledge, this paper is the first study applying agent-based simulations for malware propagation in D2D.

PDF