BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Dvir Shabtay

Dvir Shabtay contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete MathematicsComputational Complexity

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2025arXiv

Approximation Algorithms for Fair Repetitive Scheduling

We consider a recently introduced fair repetitive scheduling problem involving a set of clients, each asking for their associated job to be daily scheduled on a single machine across a finite planning horizon. The goal is to determine a job processing permutation for each day, aiming to minimize the maximum total completion time experienced by any client. This problem is known to be NP-hard for quite restrictive settings, with previous work offering exact solution methods for highly-structured special cases. In this paper, we focus on the design of approximation algorithms with provable performance guarantees. Our main contributions can be briefly summarized as follows: (i) When job processing times are day-dependent, we devise a polynomial-time LP-based $2$-approximation, as well as a polynomial-time approximation scheme for a constant number of days. (ii) With day-invariant processing times, we obtain a surprisingly simple $(\frac{1+\sqrt{2}}{2}+ε)$-approximation in polynomial time. This setting is also shown to admit a quasi-polynomial-time approximation scheme for an arbitrary number of days. The key technical component driving our approximation schemes is a novel batching technique, where jobs are conceptually grouped into batches, subsequently leading either to a low-dimensional dynamic program or to a compact configuration LP. Concurrently, while developing our constant-factor approximations, we propose a host of lower-bounding mechanisms that may be of broader interest.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

Fairness in Repetitive Scheduling

Recent research found that fairness plays a key role in customer satisfaction. Therefore, many manufacturing and services industries have become aware of the need to treat customers fairly. Still, there is a huge lack of models that enable industries to make operational decisions fairly, such as a fair scheduling of the customers' jobs. Our main aim in this research is to provide a unified framework to enable schedulers making fair decisions in repetitive scheduling environments. For doing so, we consider a set of repetitive scheduling problems involving a set of $n$ clients. In each out of $q$ consecutive operational periods (e.g. days), each one of the customers submits a job for processing by an operational system. The scheduler's aim is to provide a schedule for each of the $q$ periods such that the quality of service (QoS) received by each of the clients will meet a certain predefined threshold. The QoS of a client may take several different forms, e.g., the number of days that the customer receives its job later than a given due-date, the number of times the customer receive his preferred time slot for service, or the sum of waiting times for service. We analyze the single machine variant of the problem for several different definitions of QoS, and classify the complexity of the corresponding problems using the theories of classical and parameterized complexity. We also study the price of fairness, i.e., the loss in the system's efficiency that results from the need to provide fair solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Hardness of Interval Scheduling on Unrelated Machines

We provide new (parameterized) computational hardness results for Interval Scheduling on Unrelated Machines. It is a classical scheduling problem motivated from just-in-time or lean manufacturing, where the goal is to complete jobs exactly at their deadline. We are given $n$ jobs and $m$ machines. Each job has a deadline, a weight, and a processing time that may be different on each machine. The goal is find a schedule that maximized the total weight of jobs completed exactly at their deadline. Note that this uniquely defines a processing time interval for each job on each machine. Interval Scheduling on Unrelated Machines is closely related to coloring interval graphs and has been thoroughly studied for several decades. However, as pointed out by Mnich and van Bevern [Computers \& Operations Research, 2018], the parameterized complexity for the number $m$ of machines as a parameter remained open. We resolve this by showing that Interval Scheduling on Unrelated Machines is W[1]-hard when parameterized by the number $m$ of machines. To this end, we prove W[1]-hardness with respect to $m$ of the special case where we have parallel machines with eligible machine sets for jobs. This answers Open Problem 8 of Mnich and van Bevern's list of 15 open problems in the parameterized complexity of scheduling [Computers \& Operations Research, 2018]. Furthermore, we resolve the computational complexity status of the unweighted version of Interval Scheduling on Unrelated Machines by proving that it is NP-complete. This answers an open question by Sung and Vlach [Journal of Scheduling, 2005].

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions

The $1 \mid \mid Σw_j U_j$ problem asks to determine -- given $n$ jobs each with its own processing time, weight, and due date -- the minimum weighted number of tardy jobs in any single machine non-preemptive schedule for these jobs. This is a classical scheduling problem that generalizes both Knapsack, and Subset Sum. The best known pseudo-polynomial algorithm for $1 \mid \mid Σw_j U_j$, due to Lawler and Moore [Management Science'69], dates back to the late 60s and has a running time of $O(d_{\max}n)$, where $n$ is the number of jobs and $d_{\max}$ is their maximal due date. A recent lower bound by Cygan \emph{et al.}~[ICALP'19] for Knapsack shows that $1 \mid \mid Σw_j U_j$ cannot be solved in $\widetilde{O}((n+d_{\max})^{2-\varepsilon})$ time, for any $\varepsilon > 0$, under a plausible conjecture. This still leaves a gap between the best known lower bound and upper bound for the problem. In this paper we design a new simple algorithm for $1 \mid \mid Σw_j U_j$ that uses $(\max,+)$-convolutions as its main tool, and outperforms the Lawler and Moore algorithm under several parameter ranges. In particular, depending on the specific method of computing $(\max,+)$-convolutions, its running time can be bounded by - $\widetilde{O}(n+d_{\#}d_{\max}^2)$. - $\widetilde{O}(d_{\#}n +d^2_{\#}d_{\max}w_{\max})$. - $\widetilde{O}(d_{\#}n +d_{\#}d_{\max}p_{\max})$. - $\widetilde{O}(n^2 +d_{\max}w^2_{\max})$. - $\widetilde{O}(n^2 + d_{\#}(d_{\max}w_{\max})^{1.5})$. Here, $d_{\#}$ denotes the number of \emph{different} due dates in the instance, $p_{\max}$ denotes the maximum processing time of any job, and $w_{\max}$ denotes the maximum weight of any job.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

SETH-Based Lower Bounds for Subset Sum and Bicriteria Path

Subset-Sum 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. One of the most intriguing open problems 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 Subset-Sum on dense instances, proving that Bellman's 1962 pseudo-polynomial $O^{*}(T)$-time algorithm for Subset-Sum on $n$ numbers and target $T$ cannot be improved to time $T^{1-\varepsilon}\cdot 2^{o(n)}$ for any $\varepsilon>0$, unless the Strong Exponential Time Hypothesis (SETH) fails. This is one of the strongest known connections between any two of the core problems of fine-grained complexity. As a corollary, we prove a "Direct-OR" theorem for Subset-Sum 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 Subset-Sum is a YES instance requires time $(N T)^{1-o(1)}$. As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t-Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset-Sum: 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 $\tilde{O}(L+m)$, in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster Minimization of Tardy Processing Time on a Single Machine

This paper is concerned with the $1||\sum p_jU_j$ problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental scheduling problem, but also a very important problem from a theoretical point of view as it generalizes the Subset Sum problem and is closely related to the 0/1-Knapsack problem. The problem is well-known to be NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time algorithms. The fastest known pseudo-polynomial time algorithm for the problem is the famous Lawler and Moore algorithm which runs in $O(P \cdot n)$ time, where $P$ is the total processing time of all $n$ jobs in the input. This algorithm has been developed in the late 60s, and has yet to be improved to date. In this paper we develop two new algorithms for $1||\sum p_jU_j$, each improving on Lawler and Moore's algorithm in a different scenario. Both algorithms rely on basic primitive operations between sets of integers and vectors of integers for the speedup in their running times. The second algorithm relies on fast polynomial multiplication as its main engine, while for the first algorithm we define a new "skewed" version of $(\max,\min)$-convolution which is interesting in its own right.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Scheduling Lower Bounds via AND Subset Sum

Given $N$ instances $(X_1,t_1),\ldots,(X_N,t_N)$ of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each set of integers $X_i$ has a subset that sums up to the target integer $t_i$. We prove that this problem cannot be solved in time $\tilde{O}((N \cdot t_{max})^{1-ε})$, for $t_{max}=\max_i t_i$ and any $ε> 0$, assuming the $\forall \exists$ Strong Exponential Time Hypothesis ($\forall \exists$-SETH). We then use this result to exclude $\tilde{O}(n+P_{max} \cdot n^{1-ε})$-time algorithms for several scheduling problems on $n$ jobs with maximum processing time $P_{max}$, based on $\forall \exists$-SETH. These include classical problems such as $1||\sum w_jU_j$, the problem of minimizing the total weight of tardy jobs on a single machine, and $P_2||\sum U_j$, the problem of minimizing the number of tardy jobs on two identical parallel machines.

0 citations0 reviewsNo code linkedOpen access