29 citations · 30 across the 5 of their papers we have counts for
4 papers · 1 filter
The Steiner Shortest Path Tree Problem
Omer Asher, Yefim Dinitz, Shlomi Dolev +2
We introduce and study a novel problem of computing a shortest path tree with a minimum number of non-terminals. It can be viewed as an (unweighted) Steiner Shortest Path Tree (SSP…
Optimal Preprocessing for Answering On-Line Product Queries
Noga Alon, Baruch Schieber
We examine the amount of preprocessing needed for answering certain on-line queries as fast as possible. We start with the following basic problem. Suppose we are given a semigroup…
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…
Quick Minimization of Tardy Processing Time on a Single Machine
Baruch Schieber, Pranav Sitaraman
We consider the problem of minimizing the total processing time of tardy jobs on a single machine. This is a classical scheduling problem, first considered by [Lawler and Moore 196…