Author name cluster

Marek Eliás 0001

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.

15 papers

1 author row

ICLR Conference 2025 Conference Paper

Approximation algorithms for combinatorial optimization with predictions

Antonios Antoniadis 0001
Marek Eliás 0001
Adam Polak 0001
Moritz Venzin

We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a generic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple (near-)linear-time algorithms for, e.g., Vertex Cover, Steiner Tree, Minimum Weight Perfect Matching, Knapsack, and Maximum Clique. Our algorithms produce an optimal solution when provided with perfect predictions and their approximation ratio smoothly degrades with increasing prediction error. With small enough prediction error we achieve approximation guarantees that are beyond the reach without predictions in given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds; we demonstrate this on the Steiner Tree problem. We conclude with an empirical evaluation of our approach.

ICML Conference 2025 Conference Paper

Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors

Matei Gabriel Cosa
Marek Eliás 0001

Combining algorithms is one of the key techniques in learning-augmented algorithms. We consider the following problem: We are given $\ell$ heuristics for Metrical Task Systems (MTS), where each might be tailored to a different type of input instances. While processing an input instance received online, we are allowed to query the action of only one of the heuristics at each time step. Our goal is to achieve performance comparable to the best of the given heuristics. The main difficulty of our setting comes from the fact that the cost paid by a heuristic at time $t$ cannot be estimated unless the same heuristic was also queried at time $t-1$. This is related to Bandit Learning against memory bounded adversaries (Arora et al. , 2012). We show how to achieve regret of $O(\text{OPT}^{2/3})$ and prove a tight lower bound based on the construction of Dekel et al. (2013).

SODA Conference 2025 Conference Paper

Stronger adversaries grow cheaper forests: online node-weighted Steiner problems

Sander Borst
Marek Eliás 0001
Moritz Venzin

We propose a O (log k log n )-competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous bound of O (log 2 k log n ) by Hajiaghayi et al. [2017]. In fact, our result extends to the more general prize-collecting setting, improving over previous works by a poly-logarithmic factor. Our key technical contribution is a randomized online algorithm for set cover and non-metric facility location in a new adversarial model which we call semi-adaptive adversaries. As a by-product of our techniques, we obtain the first deterministic O (log | C | log | F |)-competitive algorithm for non-metric facility location.

ICLR Conference 2024 Conference Paper

Algorithms for Caching and MTS with reduced number of predictions

Karim Abdel Sadek
Marek Eliás 0001

ML-augmented algorithms utilize predictions to achieve performance beyond their worst-case bounds. Producing these predictions might be a costly operation – this motivated Im et al. [2022] to introduce the study of algorithms which use predictions parsimoniously. We design parsimonious algorithms for caching and MTS with action predictions, proposed by Antoniadis et al. [2023], focusing on the parameters of consistency (performance with perfect predictions) and smoothness (dependence of their performance on prediction error). Our algorithm for caching is 1-consistent, robust, and its smoothness deteriorates with decreasing number of available predictions. We propose an algorithm for general MTS whose consistency and smoothness both scale linearly with the decreasing number of predictions. Without restriction on the number of available predictions, both algorithms match the earlier guarantees achieved by Antoniadis et al. [2023].

UAI Conference 2024 Conference Paper

Bandits with Knapsacks and Predictions

Davide Drago
Andrea Celli
Marek Eliás 0001

We study the Bandits with Knapsacks problem with the aim of designing a learning-augmented online learning algorithm upholding better regret guarantees than the state-of-the-art primal-dual algorithms with worst-case guarantees, under both stochastic and adversarial inputs. In the adversarial case, we obtain better competitive ratios when the input predictions are accurate, while also maintaining worst-case guarantees for imprecise predictions. We introduce two algorithms tailored for the full and bandit feedback settings, respectively. Both algorithms integrate a static prediction with a worst-case no-$\alpha$-regret algorithm. This yields an optimized competitive ratio of $(\pi + (1 -\pi)/\alpha)^{-1}$ in scenarios where the prediction is perfect, and a competitive ratio of $\alpha/(1 - \pi)$ in the case of highly imprecise predictions, where $\pi \in (0, 1)$ is chosen by the learner and $\alpha$ is Slater’s parameter. We complement this analysis by studying the stochastic setting under full feedback. We provide an algorithm which guarantees a pseudo-regret of $\widetilde{O}(\sqrt{T})$ with poor predictions, and 0 pseudo-regret with perfect predictions. We also characterize the smoothness of the algorithm.

ICML Conference 2023 Conference Paper

Mixing Predictions for Online Metric Algorithms

Antonios Antoniadis 0001
Christian Coester
Marek Eliás 0001
Adam Polak 0001
Bertrand Simon 0001

A major technique in learning-augmented online algorithms is combining multiple algorithms or predictors. Since the performance of each predictor may vary over time, it is desirable to use not the single best predictor as a benchmark, but rather a dynamic combination which follows different predictors at different times. We design algorithms that combine predictions and are competitive against such dynamic combinations for a wide class of online problems, namely, metrical task systems. Against the best (in hindsight) unconstrained combination of $\ell$ predictors, we obtain a competitive ratio of $O(\ell^2)$, and show that this is best possible. However, for a benchmark with slightly constrained number of switches between different predictors, we can get a $(1+\epsilon)$-competitive algorithm. Moreover, our algorithms can be adapted to access predictors in a bandit-like fashion, querying only one predictor at a time. An unexpected implication of one of our lower bounds is a new structural insight about covering formulations for the $k$-server problem.

ICML Conference 2023 Conference Paper

Paging with Succinct Predictions

Antonios Antoniadis 0001
Joan Boyar
Marek Eliás 0001
Lene M. Favrholdt
Ruben Hoeksma
Kim S. Larsen
Adam Polak 0001
Bertrand Simon 0001

Paging is a prototypical problem in the area of online algorithms. It has also played a central role in the development of learning-augmented algorithms. Previous work on learning-augmented paging has investigated predictions on (i) when the current page will be requested again (reoccurrence predictions), (ii) the current state of the cache in an optimal algorithm (state predictions), (iii) all requests until the current page gets requested again, and (iv) the relative order in which pages are requested. We study learning-augmented paging from the new perspective of requiring the least possible amount of predicted information. More specifically, the predictions obtained alongside each page request are limited to one bit only. We develop algorithms satisfy all three desirable properties of learning-augmented algorithms – that is, they are consistent, robust and smooth – despite being limited to a one-bit prediction per request. We also present lower bounds establishing that our algorithms are essentially best possible.

ICML Conference 2021 Conference Paper

Differentially Private Correlation Clustering

Mark Bun
Marek Eliás 0001
Janardhan Kulkarni

Correlation clustering is a widely used technique in unsupervised machine learning. Motivated by applications where individual privacy is a concern, we initiate the study of differentially private correlation clustering. We propose an algorithm that achieves subquadratic additive error compared to the optimal cost. In contrast, straightforward adaptations of existing non-private algorithms all lead to a trivial quadratic error. Finally, we give a lower bound showing that any pure differentially private algorithm for correlation clustering requires additive error $\Omega$(n).

SODA Conference 2020 Conference Paper

Differentially Private Release of Synthetic Graphs

Marek Eliás 0001
Michael Kapralov
Janardhan Kulkarni
Yin Tat Lee

We propose a ( ϵ, δ )-differentially private mechanism that, given an input graph G with n vertices and m edges, in polynomial time generates a synthetic graph G’ approximating all cuts of the input graph up to an additive error of. This is the first construction of differentially private cut approximator that allows additive error o ( m ) for all m > n log C n. The best known previous results gave additive O ( n 3/2 ) error and hence only retained information about the cut structure on very dense graphs. Thus, we are making a notable progress on a promiment problem in differential privacy. We also present lower bounds showing that our utility/privacy trade-off is essentially the best possible if one seeks to get purely additive cut approximations.

ICML Conference 2020 Conference Paper

Online metric algorithms with untrusted predictions

Antonios Antoniadis 0001
Christian Coester
Marek Eliás 0001
Adam Polak 0001
Bertrand Simon 0001

Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only to benefit from good predictions but also to achieve a decent performance when the predictions are inadequate. In this paper, we propose a prediction setup for arbitrary metrical task systems (MTS) (e. g. , caching, k-server and convex body chasing) and online matching on the line. We utilize results from the theory of online algorithms to show how to make the setup robust. Specifically for caching, we present an algorithm whose performance, as a function of the prediction error, is exponentially better than what is achievable for general MTS. Finally, we present an empirical evaluation of our methods on real world datasets, which suggests practicality.

SODA Conference 2018 Conference Paper

Competitive Algorithms for Generalized k -Server in Uniform Metrics

Nikhil Bansal 0001
Marek Eliás 0001
Grigorios Koumoutsos
Jesper Nederlof

The generalized k -server problem is a far-reaching extension of the k -server problem with several applications. Here, each server s i lies in its own metric space M i. A request is a k -tuple r = ( r 1, r 2, …, r k ) and to serve it, we need to move some server s i to the point r i ∊ M i, and the goal is to minimize the total distance traveled by the servers. Despite much work, no f ( k )-competitive algorithm is known for the problem for k > 2 servers, even for special cases such as uniform metrics and lines. Here, we consider the problem in uniform metrics and give the first f ( k )-competitive algorithms for general k. In particular, we obtain deterministic and randomized algorithms with competitive ratio k · 2 k and O ( k 3 log k ) respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2 k – 1. We also give a 2 2 O ( k ) -competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.

SODA Conference 2018 Conference Paper

Nested Convex Bodies are Chaseable

Nikhil Bansal 0001
Martin Böhm 0001
Marek Eliás 0001
Grigorios Koumoutsos
Seeun William Umboh

In the Convex Body Chasing problem, we are given an initial point v 0 ∊ ℝ d and an online sequence of n convex bodies F 1, …, F n. When we receive F i, we are required to move inside F i. Our goal is to minimize the total distance traveled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open. We consider the setting in which the convex bodies are nested: F i ⊃ … ⊃ F n. The nested setting is closely related to extending the online LP framework of Buchbinder and Naor (ESA 2005) to arbitrary linear constraints. Moreover, this setting retains much of the difficulty of the general setting and captures an essential obstacle in resolving Friedman and Linial's conjecture. In this work, we give a f ( d )-competitive algorithm for chasing nested convex bodies in ℝ d.

SODA Conference 2017 Conference Paper

The ( h, k )-Server Problem on Bounded Depth Trees

Nikhil Bansal 0001
Marek Eliás 0001
Lukasz Jez
Grigorios Koumoutsos

We study the k -server problem in the resource augmentation setting i. e. , when the performance of the online algorithm with k servers is compared to the offline optimal solution with H ≤ k servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic k -server algorithms are roughly (1 + 1/∊)-competitive when k = (1 + ∊)h, for any ∊ > 0. Surprisingly however, no o(h)- competitive algorithm is known even for HSTs of depth 2 and even when k/h is arbitrarily large. We obtain several new results for the problem. First we show that the known k -server algorithms do not work even on very simple metrics. In particular, the Double Coverage algorithm has competitive ratio O (h) irrespective of the value of k, even for depth-2 HSTs. Similarly the Work Function Algorithm, that is believed to be optimal for all metric spaces when k = h, has competitive ratio O (h) on depth-3 HSTs even if k = 2h. Our main result is a new algorithm that is O (1)-competitive for constant depth trees, whenever k = (1 + ∊)h for any ∊ > 0. Finally, we give a general lower bound that any deterministic online algorithm has competitive ratio at least 2. 4 even for depth-2 HSTs and when k/h is arbitrarily large. This gives a surprising qualitative separation between uniform metrics and depth-2 HSTs for the ( h, k )-server problem, and gives the strongest known lower bound for the problem on general metrics.

FOCS Conference 2017 Conference Paper

Weighted k-Server Bounds via Combinatorial Dichotomies

Nikhil Bansal 0001
Marek Eliás 0001
Grigorios Koumoutsos

The weighted k-server problem is a natural generalization of the k-server problem where each server has a different weight. We consider the problem on uniform metrics, which corresponds to a natural generalization of paging. Our main result is a doubly exponential lower bound on the competitive ratio of any deterministic online algorithm, that essentially matches the known upper bounds for the problem and closes a large and long-standing gap. The lower bound is based on relating the weighted k-server problem to a certain combinatorial problem and proving a Ramsey-theoretic lower bound for it. This combinatorial connection also reveals several structural properties of low cost feasible solutions to serve a sequence of requests. We use this to show that the generalized Work Function Algorithm achieves an almost optimum competitive ratio, and to obtain new refined upper bounds on the competitive ratio for the case of d different weight classes.

SODA Conference 2016 Conference Paper

Improved Approximation for Vector Bin Packing

Nikhil Bansal 0001
Marek Eliás 0001
Arindam Khan 0001

We study the d -dimensional vector bin packing problem, a well-studied generalization of bin packing arising in resource allocation and scheduling problems. Here we are given a set of d -dimensional vectors v 1, …, v n in [0, 1] d, and the goal is to pack them into the least number of bins so that for each bin B, the sum of the vectors in it is at most 1 in every dimension, i. e. ,. For the 2-dimensional case we give an asymptotic approximation guarantee of 1 + ln(1. 5) + ∊ ≈ (1. 405 + ∊), improving upon the previous bound of 1 + ln 2 + ∊ ≈ (1. 693 + ∊). We also give an almost tight (1. 5+ ∊) absolute approximation guarantee, improving upon the previous bound of 2 [23]. For the d -dimensional case, we get a guarantee, improving upon the previous (1 + ln d + ∊) guarantee [2]. Here (1 + ln d ) was a natural barrier as rounding-based algorithms can not achieve better than d approximation. We get around this by exploiting various structural properties of (near)-optimal packings, and using multi-objective multi-budget matching based techniques and expanding the Round & Approx framework to go beyond rounding-based algorithms. Along the way we also prove several results that could be of independent interest.