Joseph (Seffi) Naor
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Joseph (Seffi) Naor has a total of 49 co-authors. Here are the top co-authors by number of shared publications:
- Niv Buchbinder
Department of Statistics and Operations Research School of Mathematical Sciences Tel Aviv University Israel
9 shared publications - Ariel Orda
Viterbi Department of Electrical and Computer Engineering Technion — Israel Institute of Technology Haifa Israel
3 shared publications - Moran Feldman
Department of Computer Science University of Haifa
3 shared publications - Roy Schwartz
Technion Israel Institute of Technology, Technion City
3 shared publications - Anupam Gupta
Computer Science Department Carnegie Mellon University Pittsburgh PA
2 shared publications - Hadas Shachnai
Computer Science Department, Technion, Haifa, Israel
2 shared publications
Latest Publications
- 22 January 2025
- Published by Springer Nature
- p. 166-180
Approximations and Hardness of Covering and Packing Partially Ordered Items
- 22 January 2025
- Published by Springer Nature
- p. 166-180
Approximations and Hardness of Covering and Packing Partially Ordered Items
- Open Access
- 13 May 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 499-527
Online k-taxi via Double Coverage and time-reverse primal-dual
We consider the online k-taxi problem, a generalization of the k-server problem, in which k servers are located in a metric space. A sequence of requests is revealed one by one, where each request is a pair of two points, representing the start and destination of a travel request by a passenger. The goal is to serve all requests while minimizing the distance traveled without carrying a passenger. We show that the classic Double Coverage algorithm has competitive ratio $$2^k-1$$ on HSTs, matching a recent lower bound for deterministic algorithms. For bounded depth HSTs, the competitive ratio turns out to be much better and we obtain tight bounds. When the depth is $$d\ll k$$ , these bounds are approximately $$k^d/d!$$ . By standard embedding results, we obtain a randomized algorithm for arbitrary n-point metrics with (polynomial) competitive ratio $$O(k^c\Delta ^{1/c}\log _{\Delta } n)$$ , where $$\Delta $$ is the aspect ratio and $$c\ge 1$$ is an arbitrary positive integer constant. The previous known bound was $$O(2^k\log n)$$ . For general (weighted) tree metrics, we prove the competitive ratio of Double Coverage to be $$\Theta (k^d)$$ for any fixed depth d, and in contrast to HSTs it is not bounded by $$2^k-1$$ . We obtain our results by a dual fitting analysis where the dual solution is constructed step-by-step backwards in time. Unlike the forward-time approach typical of online primal-dual analyses, this allows us to combine information from both the past and the future when assigning dual variables. We believe this method can also be useful for other problems. Using this technique, we also provide a dual fitting proof of the k-competitiveness of Double Coverage for the k-server problem on trees.- 13 May 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 499-527
Open AccessOnline k-taxi via Double Coverage and time-reverse primal-dual
We consider the online k-taxi problem, a generalization of the k-server problem, in which k servers are located in a metric space. A sequence of requests is revealed one by one, where each request is a pair of two points, representing the start and destination of a travel request by a passenger. The goal is to serve all requests while minimizing the distance traveled without carrying a passenger. We show that the classic Double Coverage algorithm has competitive ratio $$2^k-1$$ on HSTs, matching a recent lower bound for deterministic algorithms. For bounded depth HSTs, the competitive ratio turns out to be much better and we obtain tight bounds. When the depth is $$d\ll k$$ , these bounds are approximately $$k^d/d!$$ . By standard embedding results, we obtain a randomized algorithm for arbitrary n-point metrics with (polynomial) competitive ratio $$O(k^c\Delta ^{1/c}\log _{\Delta } n)$$ , where $$\Delta $$ is the aspect ratio and $$c\ge 1$$ is an arbitrary positive integer constant. The previous known bound was $$O(2^k\log n)$$ . For general (weighted) tree metrics, we prove the competitive ratio of Double Coverage to be $$\Theta (k^d)$$ for any fixed depth d, and in contrast to HSTs it is not bounded by $$2^k-1$$ . We obtain our results by a dual fitting analysis where the dual solution is constructed step-by-step backwards in time. Unlike the forward-time approach typical of online primal-dual analyses, this allows us to combine information from both the past and the future when assigning dual variables. We believe this method can also be useful for other problems. Using this technique, we also provide a dual fitting proof of the k-competitiveness of Double Coverage for the k-server problem on trees. - 30 November 2021
- Published by Springer Nature in Algorithmica
- Vol. 84 (2) , 304-324
Tight Bounds for Online Weighted Tree Augmentation
- 30 November 2021
- Published by Springer Nature in Algorithmica
- Vol. 84 (2) , 304-324
Tight Bounds for Online Weighted Tree Augmentation
- Open Access
$O(\mbox{depth})$-Competitive Algorithm for Online Multi-level Aggregation
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 tree, and each request specifies a deadline. A request is served by sending it to the root before its deadline at a cost equal to the weight of the path from the node in which it resides to the root. However, requests from different nodes can be aggregated, and served together, so as to save on cost. The cost of serving an aggregated set of requests is equal to the weight of the subtree spanning the nodes in which the requests reside. Thus, the problem is to find a competitive online aggregation algorithm that minimizes the total cost of the aggregated requests. This problem arises naturally in many scenarios, including multicasting, supply-chain management and sensor networks. It is also related to the well studied TCP-acknowledgement problem and the online joint replenishment problem. We present an online $O(D)$-competitive algorithm for the problem, where $D$ is the depth, or number of levels, of the aggregation tree. This result improves upon the $D^2 2^D$-competitive algorithm obtained recently by Bienkowski et al. (2015).Open Access$O(\mbox{depth})$-Competitive Algorithm for Online Multi-level Aggregation
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 tree, and each request specifies a deadline. A request is served by sending it to the root before its deadline at a cost equal to the weight of the path from the node in which it resides to the root. However, requests from different nodes can be aggregated, and served together, so as to save on cost. The cost of serving an aggregated set of requests is equal to the weight of the subtree spanning the nodes in which the requests reside. Thus, the problem is to find a competitive online aggregation algorithm that minimizes the total cost of the aggregated requests. This problem arises naturally in many scenarios, including multicasting, supply-chain management and sensor networks. It is also related to the well studied TCP-acknowledgement problem and the online joint replenishment problem. We present an online $O(D)$-competitive algorithm for the problem, where $D$ is the depth, or number of levels, of the aggregation tree. This result improves upon the $D^2 2^D$-competitive algorithm obtained recently by Bienkowski et al. (2015). - 1 May 2016
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 41 (2) , 612-625
Unified Algorithms for Online Learning and Competitive Analysis
Online learning and competitive analysis are two widely studied frameworks for online decision-making settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals, and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm, which, by parameter tuning, interpolates between optimal regret for learning from experts (in online learning) and optimal competitive ratio for the metrical task systems problem (MTS) (in competitive analysis), improving upon previous results. The algorithm also allows us to obtain new regret bounds against “drifting” experts, which might be of independent interest. Moreover, our approach allows us to go beyond experts/MTS, obtaining similar unifying results for structured action sets and “combinatorial experts,” whenever the setting has a certain matroid structure.
- 1 May 2016
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 41 (2) , 612-625
Unified Algorithms for Online Learning and Competitive Analysis
Online learning and competitive analysis are two widely studied frameworks for online decision-making settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals, and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm, which, by parameter tuning, interpolates between optimal regret for learning from experts (in online learning) and optimal competitive ratio for the metrical task systems problem (MTS) (in competitive analysis), improving upon previous results. The algorithm also allows us to obtain new regret bounds against “drifting” experts, which might be of independent interest. Moreover, our approach allows us to go beyond experts/MTS, obtaining similar unifying results for structured action sets and “combinatorial experts,” whenever the setting has a certain matroid structure.
- 17 March 2016
- Published by Springer Nature in Journal of Scheduling
- Vol. 20 (4) , 337-353
Non-preemptive buffer management for latency sensitive packets
- 17 March 2016
- Published by Springer Nature in Journal of Scheduling
- Vol. 20 (4) , 337-353
Non-preemptive buffer management for latency sensitive packets
- 23 January 2014
- Published by Springer Nature in Journal of Scheduling
- Vol. 17 (4) , 385-398
Frequency capping in online advertising
- 23 January 2014
- Published by Springer Nature in Journal of Scheduling
- Vol. 17 (4) , 385-398
Frequency capping in online advertising
- 18 December 2013
- Published by Society for Industrial & Applied Mathematics (SIAM)
Non-Uniform Graph Partitioning
- 18 December 2013
- Published by Society for Industrial & Applied Mathematics (SIAM)
Non-Uniform Graph Partitioning
- 2 April 2013
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Systems Journal
- Vol. 8 (2) , 450-460
Smart Grid Network Optimization: Data-Quality-Aware Volume Reduction
The power industry is in the early stages of a fundamental change, driving the integration of energy, communications, and information technologies into one intelligent utility network, known as the smart grid. This paper investigates data traffic management in smart grid networks, in which huge volumes of data produced by advanced meters cannot be fully delivered to utility data centers due to limited bandwidth. To develop a solution for optimizing traffic flow, we exploit a particular characteristic of this network-power-related applications can benefit from different levels of data quality along the path to the final destination. We thus handle congestion by performing intelligent quality-aware volume reduction of the flows within the network. Our optimization problem is that of computing for each flow the amount of volume reductions in different locations, so as to maximize overall revenue. We address both an off-line scenario, in which all flows are known beforehand, and an online framework, in which new flows can be generated during system operation. For the off-line case, we propose an efficient, near-optimal solution, while for the online case, we derive almost tight polylogarithmic upper and lower bounds on the competitive ratio. We also consider a more restricted dynamic setting, for which we demonstrate how to compute an optimal solution. This paper initiates a rigorous treatment of cross-layer traffic management in the smart grid.
- 2 April 2013
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Systems Journal
- Vol. 8 (2) , 450-460
Smart Grid Network Optimization: Data-Quality-Aware Volume Reduction
The power industry is in the early stages of a fundamental change, driving the integration of energy, communications, and information technologies into one intelligent utility network, known as the smart grid. This paper investigates data traffic management in smart grid networks, in which huge volumes of data produced by advanced meters cannot be fully delivered to utility data centers due to limited bandwidth. To develop a solution for optimizing traffic flow, we exploit a particular characteristic of this network-power-related applications can benefit from different levels of data quality along the path to the final destination. We thus handle congestion by performing intelligent quality-aware volume reduction of the flows within the network. Our optimization problem is that of computing for each flow the amount of volume reductions in different locations, so as to maximize overall revenue. We address both an off-line scenario, in which all flows are known beforehand, and an online framework, in which new flows can be generated during system operation. For the off-line case, we propose an efficient, near-optimal solution, while for the online case, we derive almost tight polylogarithmic upper and lower bounds on the competitive ratio. We also consider a more restricted dynamic setting, for which we demonstrate how to compute an optimal solution. This paper initiates a rigorous treatment of cross-layer traffic management in the smart grid.
- 8 February 2013
- Published by Springer Nature in Theory of Computing Systems
- Vol. 54 (3) , 388-406
A Truthful Mechanism for Value-Based Scheduling in Cloud Computing
- 8 February 2013
- Published by Springer Nature in Theory of Computing Systems
- Vol. 54 (3) , 388-406
A Truthful Mechanism for Value-Based Scheduling in Cloud Computing