32 citations · 43 across the 13 of their papers we have counts for
16 papers
Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness
Anish Hebbar, Ravi Kumar, Roie Levin +3
Suppose an online algorithm is given an unbiased -sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study…
Stochastic Caching via Subset Entropy
Ravi Kumar, Roie Levin, Joseph +2
A classic approach to beyond worst-case algorithm design is to impose stochastic assumptions on the input. However, a limiting feature of stochastic analyses is that, by the min-ma…
Incremental Dominating Set
Ilan Doron Arad, Jonathan Gal, Seffi Naor
Dominating Set is a fundamental problem in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or adjacent to a selected…
Approximations and Hardness of Packing Partially Ordered Items
Ilan Doron-Arad, Guy Kortsarz, Joseph Naor +2
Motivated by applications in production planning and storage allocation in hierarchical databases, we initiate the study of covering partially ordered items (CPO). Given a capacity…
Competitive Algorithms for Block-Aware Caching
Christian Coester, Roie Levin, Joseph +2
We study the block-aware caching problem, a generalization of classic caching in which fetching (or evicting) pages from the same block incurs the same cost as fetching (or evictin…
Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)
Niv Buchbinder, Joseph, Naor +1
For numerous online bipartite matching problems, such as edge-weighted matching and matching under two-sided vertex arrivals, the state-of-the-art fractional algorithms outperform…
General Knapsack Problems in a Dynamic Setting
Yaron Fairstein, Ariel Kulik, Joseph +2
The world is dynamic and changes over time, thus any optimization problem used to model real life problems must address this dynamic nature, taking into account the cost of changes…
Online -Taxi via Double Coverage and Time-Reverse Primal-Dual
Niv Buchbinder, Christian Coester, Joseph +1
We consider the online -taxi problem, a generalization of the -server problem, in which servers are located in a metric space. A sequence of requests is revealed one by o…
Online Virtual Machine Allocation with Predictions
Niv Buchbinder, Yaron Fairstein, Konstantina Mellou +3
The cloud computing industry has grown rapidly over the last decade, and with this growth there is a significant increase in demand for compute resources. Demand is manifested in t…
An Almost Optimal Approximation Algorithm for Monotone Submodular Multiple Knapsack
Yaron Fairstein, Ariel Kulik, Joseph +3
We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint. The input is a set of items, each has a non-negative weight, and a…
Tight Bounds for Online Weighted Tree Augmentation
Joseph, Naor, Seeun William Umboh +1
The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an -vertex…
$O(\mbox{depth})$-Competitive Algorithm for Online Multi-level Aggregation
Niv Buchbinder, Moran Feldman, Joseph Naor +1
We consider a multi-level aggregation problem in a weighted rooted tree, studied recently by Bienkowski et al. (2015). In this problem requests arrive over time at the nodes of the…
Truthful Online Scheduling with Commitments
Yossi Azar, Inna Kalp-Shaltiel, Brendan Lucier +4
We study online mechanisms for preemptive scheduling with deadlines, with the goal of maximizing the total value of completed jobs. This problem is fundamental to deadline-aware cl…
Online Packing and Covering Framework with Convex Objectives
Niv Buchbinder, Shahar Chen, Anupam Gupta +3
We consider online fractional covering problems with a convex objective, where the covering constraints arrive over time. Formally, we want to solve $\min\,\{f(x) \mid Ax\ge \mathb…
Near-Optimum Online Ad Allocation for Targeted Advertising
Joseph, Naor, David Wajc
Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than $(…
Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
Niv Buchbinder, Joseph, Naor +2
Consider the following online version of the submodular maximization problem under a matroid constraint: We are given a set of elements over which a matroid is defined. The goal is…