Truly asymptotic lower bounds for online vector bin packing

J\'anos Balogh, Ilan R. Cohen, Leah Epstein, Amos Fiat, Asaf Levin
APPROX 21 Workshop on Approximation Algorithms for Combinatorial Optimization Problems

In this work, we consider online d-dimensional vector bin packing. It is known that no algorithm can have a competitive ratio of O(d/\log^2 d) in the absolute sense, although upper bounds for this problem have always been presented in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure, and since the two measures are different, we focus on the asymptotic measure and prove new lower bounds of the asymptotic competitive ratio. The existing lower bounds prior to this work were known to be smaller than 3, even for very large d. Here, we significantly improved on the best known lower bounds of the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with d \geq 3 dimensions, for every dimension d. To obtain these results, we use several different constructions, one of which is an adaptive construction with a lower bound of \Omega(\sqrt{d}). Our main result is that the lower bound of \Omega(d/\log^2 d) on the competitive ratio holds also in the asymptotic sense. This result holds also against randomized algorithms, and requires a careful adaptation of constructions for online coloring, rather than simple black-box reductions.

Weighted completion time minimization for capacitated parallel machines

Ilan R. Cohen, Izack Cohen, Iyar Zaks
WAOA 21 Workshop on Approximation and Online Algorithms

We consider the weighted completion time minimization problem for capacitated parallel machines, which is a fundamental problem in modern cloud computing environments. We study settings in which the processed jobs may have varying duration, resource requirements and importance (weight). Each server (machine) can process multiple concurrent jobs up to its capacity. Due to the problem’s \mathcal{NP}-hardness, we study heuristic approaches with provable approximation guarantees. We first analyze an algorithm that prioritizes the jobs with the smallest volume-by-weight ratio. We bound its approximation ratio with a decreasing function of the ratio between the highest resource demand of any job to the server’s capacity. Then, we use the algorithm for scheduling jobs with resource demands equal to or smaller than 0.5 of the server’s capacity in conjunction with the classic weighted shortest processing time algorithm for jobs with resource demands higher than 0.5. We thus create a hybrid, constant approximation algorithm for two or more machines. We also develop a constant approximation algorithm for the case with a single machine. This research is the first, to the best of our knowledge, to propose a polynomial-time algorithm with a constant approximation ratio for minimizing the weighted sum of job completion times for capacitated parallel machines.

Contention Resolution, Matrix Scaling and Fair Allocation

Nikhil Bansal, Ilan R. Cohen
WAOA 21 Workshop on Approximation and Online Algorithms

A contention resolution (CR) scheme is a basic algorithmic primitive, that deals with how to allocate items among a random set S of competing players, while maintaining various properties. We consider the most basic setting where a single item must be allocated to some player in S. Here, in a seminal work, Feige and Vondrak (2006) designed a fair CR scheme when the set S is chosen from a product distribution. We explore whether such fair schemes exist for arbitrary non-product distributions on sets of players S, and whether they admit simple algorithmic primitives. Moreover, can we go beyond fair allocation and design such schemes for all possible achievable allocations.

We show that for any arbitrary distribution on sets of players S, and for any achievable allocation, there exist several natural CR schemes that can be succinctly described, are simple to implement and can be efficiently computed to any desired accuracy. We also characterize the space of achievable allocations for any distribution, give algorithms for computing an optimum fair allocation for arbitrary distributions, and describe other natural fair CR schemes for product distributions. These results are based on matrix scaling and various convex programming relaxations.

Online Two-Dimensional Load Balancing

Ilan R. Cohen, Sungjin Im, Debmalya Panigrahi
ICALP 20 International Colloquium on Automata, Languages, and Programming

In this paper, we consider the problem of assigning 2-dimensional vector jobs to identical machines online so to minimize the maximum load on any dimension of any machine. For arbitrary number of dimensions d, this problem is known as vector scheduling, and recent research has established the optimal competitive ratio as O((log d)/(log log d)) (Im et al. FOCS 2015, Azar et al. SODA 2018). But, these results do not shed light on the situation for small number of dimensions, particularly for d = 2 which is of practical interest. In this case, a trivial analysis shows that the classic list scheduling greedy algorithm has a competitive ratio of 3. We show the following improvements over this baseline in this paper: - We give an improved, and tight, analysis of the list scheduling algorithm establishing a competitive ratio of 8/3 for two dimensions. - If the value of opt is known, we improve the competitive ratio to 9/4 using a variant of the classic best fit algorithm for two dimensions. - For any fixed number of dimensions, we design an algorithm that is provably the best possible against a fractional optimum solution. This algorithm provides a proof of concept that we can simulate the optimal algorithm online up to the integrality gap of the natural LP relaxation of the problem.

Tight Bounds for Online Edge Coloring

Ilan R. Cohen, Binghui Peng, David Wajc
FOCS 19 IEEE Symposium on Foundations of Computer Science

Vizing’s celebrated theorem asserts that any graph of maximum degree Δ admits an edge coloring using at most Δ + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2Δ − 1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with Δ = O(logn), and they conjectured the existence of online algorithms using Δ(1 + o(1)) colors for Δ = ω(logn). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS’03 and Bahmani et al., SODA’10).

We resolve the above conjecture for adversarial vertex arrivals in bipartite graphs, for which we present a (1 + o(1))Δ-edge-coloring algorithm for Δ = ω(logn) known a priori. Surprisingly, if Δ is not known ahead of time, we show that no $\big(\frac{e}{e-1} - \Omega(1) \big) \Delta$-edge-coloring algorithm exists. We then provide an optimal, $\big(\frac{e}{e-1}+o(1)\big)\Delta$-edge-coloring algorithm for unknown Δ = ω(logn). Key to our results, and of possible independent interest, is a novel fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.

Stochastic Graph Exploration

Aris Anagnostopoulos, Ilan R. Cohen, Stefano Leonardi, Jakub Łącki
ICALP 19 International Colloquium on Automata, Languages, and Programming

Exploring large-scale networks is a time consuming and expensive task which is usually operated in a complex and uncertain environment. A crucial aspect of network exploration is the development of suitable strategies that decide which nodes and edges to probe at each stage of the process.

To model this process, we introduce the stochastic graph exploration problem. The input is an undirected graph G = (V, E) with a source vertex s, stochastic edge costs drawn from a distribution πe, e ∈ E, and rewards on vertices of maximum value R. The goal is to find a set F of edges of total cost at most B such that the subgraph of G induced by F is connected, contains s, and maximizes the total reward. This problem generalizes the stochastic knapsack problem and other stochastic probing problems recently studied.

Our focus is on the development of efficient nonadaptive strategies that are competitive against the optimal adaptive strategy. A major challenge is the fact that the problem has an Ω(n) adaptivity gap even on a tree of n vertices. This is in sharp contrast with O(1) adaptivity gap of the stochastic knapsack problem, which is a special case of our problem. We circumvent this negative result by showing that O(lognR) resource augmentation suffices to obtain O(1) approximation on trees and O(lognR) approximation on general graphs. To achieve this result, we reduce stochastic graph exploration to a memoryless process—the minesweeper problem—which assigns to every edge a probability that the process terminates when the edge is probed. For this problem, interesting in its own, we present an optimal polynomial time algorithm on trees and an O(lognR) approximation for general graphs.

We study also the problem in which the maximum cost of an edge is a logarithmic fraction of the budget. We show that under this condition, there exist polynomial-time oblivious strategies that use 1 + ε budget, whose adaptivity gaps on trees and general graphs are 1 + ε and 8 + ε, respectively. Finally, we provide additional results on the structure and the complexity of nonadaptive and adaptive strategies.

Dynamic Pricing of Servers on Trees

Ilan R. Cohen, Alon Eden, Amos Fiat, Lukasz Jez
APPROX 19 Workshop on Approximation Algorithms for Combinatorial Optimization Problems

In this paper we consider the k-server problem where events are generated by selfish agents, known as the selfish k-server problem. In this setting, there is a set of k servers located in some metric space. Selfish agents arrive in an online fashion, each has a request located on some point in the metric space, and seeks to serve his request with the server of minimum distance to the request. If agents choose to serve their request with the nearest server, this mimics the greedy algorithm which has an unbounded competitive ratio. We propose an algorithm that associates a surcharge with each server independently of the agent to arrive (and therefore, yields a truthful online mechanism). An agent chooses to serve his request with the server that minimizes the distance to the request plus the associated surcharge to the server. This paper extends , which gave an optimal k-competitive dynamic pricing scheme for the selfish k-server problem on the line. We give a k-competitive dynamic pricing algorithm for the selfish k-server problem on tree metric spaces, which matches the optimal online (non truthful) algorithm. We show that an α-competitive dynamic pricing scheme exists on the tree if and only if there exists α-competitive online algorithm on the tree that is lazy, local, and monotone. Given this characterization, the main technical difficulty is coming up with such an online algorithm.

Randomized Algorithms for Online Vector Load Balancing

Yossi Azar, Ilan R. Cohen, Debmalya Panigrahi
SODA 18 ACM-SIAM Symposium on Discrete Algorithms
We study randomized algorithms for the online vector bin packing and vector scheduling problems. For vector bin packing, we achieve a competitive ratio of O(d1/B), where d is the number of dimensions and B the size of a bin. This improves the previous bound of d1/(B-1) by a polynomial factor, and is tight up to logarithmic factors. For vector scheduling, we show a lower bound of W((log d)/(log log d)) on the competitive ratio of randomized algorithms, which is the first result for randomized algorithms and is asymptotically tight. Finally, we analyze the widely used ``power of two choices¢ algorithm for vector scheduling, and show that its competitive ratio is O(log log n + (log d)/(log log d)), which is optimal up to the additive O(log log n) term that also appears in the scalar version of this algorithm.

Randomized Online Matching in Regular Graphs

Ilan R. Cohen, David Wajc
SODA 18 ACM-SIAM Symposium on Discrete Algorithms
In this paper we study the classic online matching problem, introduced in the seminal work of Karp, Vazirani and Vazirani (STOC 1990), in regular graphs. For such graphs, an optimal deterministic algorithm as well as efficient algorithms under stochastic input assumptions were known. In this work, we present a novel randomized algorithm with competitive ratio tending to one on this family of graphs, under adversarial arrival order. Our main contribution is a novel algorithm which achieves competitive ratio 1-O(sqrt(log d)/ sqrt(d)) in expectation on d-regular graphs. In contrast, we show that all previously-studied online algorithms have competitive ratio strictly bounded away from one. Moreover, we show the convergence rate of our algorithm’s competitive ratio to one is nearly tight, as no algorithm achieves competitive ratio better than 1-O(1/sqrt(d)). Finally, we show that our algorithm yields a similar competitive ratio with high probability, as well as guaranteeing each vertex a probability of being matched tending to one.

Online Algorithms for Packing and Covering Problems with Convex Objectives

Yossi Azar, Ilan R. Cohen, Debmalya Panigrahi (Joint submission with two other groups)
FOCS 17 IEEE Symposium on Foundations of Computer Science
We study the online convex covering problem and online convex packing problem. The (offline) convex covering problem is modeled by the following convex program:
minx Î Rn+ f(x) s.t. A x ³ 1
where f : Rn+ ® R+ is a monotone and convex cost function, and A is an m X n matrix with non-negative entries. Each row of the constraint matrix A corresponds to a covering constraint. In the online problem, each row of A comes online and the algorithm must maintain a feasible assignment x and may only increase x over time. The (offline) convex packing problem is modeled by the following convex program:
maxy Î Rm+ åj = 1m yj - g(AT y)
where g : Rn+ ® R+ is a monotone and convex cost function. It is the Fenchel dual program of convex covering when g is the convex conjugate of f. In the online problem, each variable yj arrives online and the algorithm must decide the value of yj on its arrival.

Online Lower Bounds via Duality

Yossi Azar, Ilan R. Cohen, Alan Roytman
SODA 17 ACM-SIAM Symposium on Discrete Algorithms
In this paper, we exploit linear programming duality in the online setting, where input arrives on the fly, from the unique perspective of designing lower bounds (i.e., hardness results) on the competitive ratio. In particular, we provide a systematic method (as opposed to ad hoc case analysis that is typically done) for obtaining online deterministic and randomized lower bounds on the competitive ratio for a wide variety of problems. We show the usefulness of our approach by providing new, tight hardness results for three diverse online problems: the Vector Bin Packing problem, Ad-auctions (and various online matching problems), and the Capital Investment problem. Our methods are sufficiently general that they can also be used to reconstruct existing lower bounds. Our approach is in stark contrast to previous works, which exploit linear programming duality to obtain positive results, often via the useful primal-dual scheme. We design a general recipe with the opposite aim of obtaining negative results via duality. The general idea behind our approach is to construct a parameterized family of primal linear programs based on a candidate collection of input sequences for proving the lower bound, where the objective function corresponds to optimizing the competitive ratio. Solving the parameterized family of primal linear programs optimally would yield a valid lower bound, but is a challenging task and limits the tools that can be applied, since analysis must be done precisely and exact optimality needs to be proved. To this end, we consider the corresponding parameterized family of dual linear programs and provide feasible solutions, where the objective function yields a lower bound on the competitive ratio. This opens up additional doors for analysis, including some of the techniques we employ (e.g., continuous analysis, differential equations, etc.), as we need not be so careful about exact optimality. We are confident that our methods can be successfully applied to produce many more lower bounds for a wide array of online problems.

Packing Small Vectors

Yossi Azar, Ilan R. Cohen, Amos Fiat, Alan Roytman
SODA 16 ACM-SIAM Symposium on Discrete Algorithms
Online d-dimensional vector packing models many settings such as minimizing resources in data centers where jobs have multiple resource requirements (CPU, Memory, etc.). However, no online d-dimensional vector packing algorithm can achieve a competitive ratio better than d. Fortunately, in many natural applications, vectors are relatively small, and thus the lower bound does not hold. For sufficiently small vectors, an O(log d)-competitive algorithm was known. We improve this to a constant competitive ratio, arbitrarily close to e » 2.718, given that vectors are sufficiently small. We give improved results for the two dimensional case. For arbitrarily small vectors, the first fit algorithm for two dimensional vector packing is no better than 2-competitive. We present a natural family of first fit variants, and for optimized parameters get a competitive ratio » 1.48 for sufficiently small vectors. We improve upon the 1.48 competitive ratio -- not via a first fit variant -- and give a competitive ratio arbitrarily close to 4/3 for packing small, two dimensional vectors. We show that no algorithm can achieve better than a 4/3 competitive ratio for two dimensional vectors, even if one allows the algorithm to split vectors among arbitrarily many bins.

Serving in the Dark should be done Non-Uniformly

Yossi Azar, Ilan R. Cohen
ICALP 15 The International Colloquium on Automata, Languages, and Programming
We study the following balls and bins stochastic game between a player and an adversary: there are B bins and a sequence of ball arrival and extraction events. In an arrival event a ball is stored in an empty bin chosen by the adversary and discarded if no bin is empty. In an extraction event, an algorithm selects a bin, clears it, and gains its content. We are interested in analyzing the gain of an algorithm which serves in the dark without any feedback at all, i.e., does not see the sequence, the content of the bins, and even the content of the cleared bins (i.e. an oblivious algorithm). We compare that gain to the gain of an optimal, open eyes, strategy that gets the same online sequence. We name this gain ratio the "loss of serving in the dark". The randomized algorithm that was previously analyzed is choosing a bin independently and uniformly at random, which resulted in a competitive ratio of about 1.69. We show that although no information is ever provided to the algorithm, using non-uniform probability distribution reduces the competitive ratio. Specifically, we design a 1.55-competitive algorithm and establish a lower bound of 1.5. We also prove a lower bound of 2 against any deterministic algorithm. This matches the performance of the round robin 2-competitive strategy. Finally, we present an application relating to a prompt mechanism for bounded capacity auctions.

Pricing Online Decisions: Beyond Auctions

Ilan R. Cohen, Alon Eden, Amos Fiat, Lukasz Jez
SODA 15 ACM-SIAM Symposium on Discrete Algorithms
We consider dynamic pricing schemes in online settings where selfish agents generate online events. Previous work on online mechanisms has dealt almost entirely with the goal of maximizing social welfare or revenue in an auction settings. This paper deals with quite general settings and minimizing social costs. We show that appropriately computed posted prices allow one to achieve essentially the same performance as the best online algorithm. This holds in a wide variety of settings. Unlike online algorithms that learn about the event, and then make enforceable decisions, prices are posted without knowing the future events or even the current event, and are thus inherently dominant strategy incentive compatible. In particular we show that one can give efficient posted price mechanisms for metrical task systems, some instances of the $k$-server problem, and metrical matching problems. We give both deterministic and randomized algorithms. Such posted price mechanisms decrease the social cost dramatically over selfish behavior where no decision incurs a charge. One alluring application of this is reducing the social cost of free parking exponentially.

Tight Bounds for Online Vector Bin Packing

Yossi Azar, Ilan R. Cohen, Seny Kamara, Bruce Shepherd
STOC 13 ACM Symposium on the Theory of Computing
In the d-dimensional bin packing problem (VBP), one is given vectors x1,x2, ¼ ,xn Î Rd and the goal is to find a partition into a minimum number of feasible sets: {1,2 ¼ ,n} = Èis Bi. A set Bi is feasible if åj Î Bi xj £ 1, where 1 denotes the all 1¢s vector. For online VBP, it has been outstanding for almost 20 years to clarify the gap between the best lower bound W(1) on the competitive ratio versus the best upper bound of O(d). We settle this by describing a W(d1-e ) lower bound. We also give strong lower bounds (of W(d(1)/(B)-e ) ) if the bin size B Î Z+ is allowed to grow. Finally, we discuss almost-matching upper bound results for general values of B; we show an upper bound whose exponent is additively ``shifted by 1" from the lower bound exponent.

The Loss of Serving in The Dark

Yossi Azar, Ilan R. Cohen, Iftach Gamzu
STOC 13 ACM Symposium on the Theory of Computing
We study the following balls and bins stochastic process: There is a buffer with B bins, and there is a stream of balls X = á X1, X2, ¼ ,XT ñ such that Xi is the number of balls that arrive before time i but after time i-1. Once a ball arrives, it is stored in one of the unoccupied bins. If all the bins are occupied then the ball is thrown away. In each time step, we select a bin uniformly at random, clear it, and gain its content. Once the stream of balls ends, all the remaining balls in the buffer are cleared and added to our gain. We are interested in analyzing the expected gain of this randomized process with respect to that of an optimal gain-maximizing strategy, which gets the same online stream of balls, and clears a ball from a bin, if exists, at any step. We name this gain ratio the loss of serving in the dark. In this paper, we determine the exact loss of serving in the dark. We prove that the expected gain of the randomized process is worse by a factor of r + e from that of the optimal gain-maximizing strategy for any e > 0, where r = maxa > 1 a ea /((a-1)ea + e - 1) » 1.69996 and B = W (1/e3). We also demonstrate that this bound is essentially tight as there are specific ball streams for which the above-mentioned gain ratio tends to r. Our stochastic process occurs naturally in many applications. We present a prompt and truthful mechanism for bounded capacity auctions, and an application relating to packets scheduling.

Education & Academic Positions

Bar Ilan University

2020 - Present

Faculty Member

Jether Energy

2019 - 2020


CWI, Amsterdam

2018 - 2019

Postdoctoral Fellow

Carnegie Mellon University &
University of Pittsburgh

2017 - 2018

Postdoctoral Fellow

Simons Institute and I-CORE

2016 - 2017

Postdoctoral Fellow

Tel Aviv University

2011 - 2016

Ph.D. in Computer Science

Tel Aviv University

2008 - 2010

M.Sc. in Computer Science


2001 - 2004

B.Sc. in Computer Science



Fulbright Post-doctoral Scholar Fellowship


Jorge Deutsch Prize for excellence in PhD studies


The Gutwirth foundation scholarships



Teaching Assistant in Algorithms at Tel Aviv University


Programming Skills

C++, C#, Java, Matlab

Advanced Skills