Baruch Schieber

Baruch Schieber
Are you Baruch Schieber?

Claim your profile, edit publications, add additional information:

Contact Details

Baruch Schieber

Pubs By Year

Pub Categories

Computer Science - Data Structures and Algorithms (3)
Computer Science - Distributed; Parallel; and Cluster Computing (1)
Computer Science - Discrete Mathematics (1)

Publications Authored By Baruch Schieber

We present a combinatorial algorithm that improves the best known approximation ratio for monotone submodular maximization under a knapsack and a matroid constraint to $\frac{1 -e^{-2}}{2}$. This classic problem is known to be hard to approximate within factor better than $1 - 1/e$. We show that the algorithm can be extended to yield a ratio of $\frac{1 - e^{-(k+1)}}{k+1}$ for the problem with a single knapsack and the intersection of $k$ matroid constraints, for any fixed $k > 1$. Read More

Motivated by the cloud computing paradigm, and by key optimization problems in all-optical networks, we study two variants of the classic job interval scheduling problem, where a reusable resource is allocated to competing job intervals in a flexible manner. Each job, $J_i$, requires the use of up to $r_{max}(i)$ units of the resource, with a profit of $p_i \geq 1$ accrued for each allocated unit. The goal is to feasibly schedule a subset of the jobs so as to maximize the total profit. Read More

The problem of counting occurrences of query graphs in a large data graph, known as subgraph counting, is fundamental to several domains such as genomics and social network analysis. Many important special cases (e.g. Read More