Arrow Research search

Author name cluster

Dvir Shabtay

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
2 author rows

Possible papers

2

AAAI Conference 2021 Conference Paper

Equitable Scheduling on a Single Machine

  • Klaus Heeger
  • Dan Hermelin
  • George B. Mertzios
  • Hendrik Molter
  • Rolf Niedermeier
  • Dvir Shabtay

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least k ≤ m days. This corresponds to an equitable schedule where each client is guaranteed a minimal level of service throughout the period of m days. We provide a thorough analysis of the computational complexity of three main variants of this problem, identifying both efficient algorithms and worst-case intractability results.

PDF Details

SODA Conference 2019 Conference Paper

SETH-Based Lower Bounds for Subset Sum and Bicriteria Path

  • Amir Abboud
  • Karl Bringmann
  • Danny Hermelin
  • Dvir Shabtay

S ubset S um and k -SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. An important open problem in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k -SAT to S ubset S um on dense instances, proving that Bellman's 1962 pseudo-polynomial O* ( T )-time algorithm for S ubset S um on n numbers and target T cannot be improved to time T 1– ε · 2 o ( n ) for any ε > 0, unless the Strong Exponential Time Hypothesis (SETH) fails. As a corollary, we prove a “Direct-OR” theorem for S ubset S um under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of N given instances of S ubset S um is a YES instance requires time ( NT ) 1– o (1). As an application of this corollary, we prove a tight SETH-based lower bound for the classical B icriteria s, t -PATH problem, which is extensively studied in Operations Research. We separate its complexity from that of S ubset S um: On graphs with m edges and edge lengths bounded by L, we show that the O ( Lm ) pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to Õ ( L + m ), in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).

Details
v2026.09.13