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

Danny Hermelin

Danny Hermelin contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete MathematicsComputational Complexitycond-mat.dis-nncond-mat.stat-mechmath.COquant-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
7topics
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

11 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
preprint2024arXiv

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard

We consider the $1||\sum w_J U_j$ problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental problems in scheduling theory, with several different applications both in theory and practice. We prove that $1||\sum w_J U_j$ is W[1]-hard with respect to the number $p_{\#}$ of different processing times in the input, as well as with respect to the number $w_{\#}$ of different weights in the input. This, along with previous work, provides a complete picture for $1||\sum w_J U_j$ from the perspective of parameterized complexity, as well as almost tight complexity bounds for the problem under the Exponential Time Hypothesis (ETH).

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

A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass

Finding the ground state of an Ising-spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms for solving them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms that run in polynomial time, and provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising-spin glass problem on a graph that provide different approximation guarantees were introduced albeit without implementation. Also recently, D-wave company constructed a physical realization of an adiabatic quantum computer, and enabled researchers to access it. D-wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its chimera graph -- a graph with bounded degree. In this work, we compare the performance of a recently developed approximation algorithm for solving the Ising spin glass problem on graphs of bounded degree against the D-wave computer. We also compared a heuristic tailored specifically to handle the fixed D-wave chimera graph. D-wave computer was able to find better approximations to all the random instances we studied. Furthermore the convergence times of D-wave were also significantly better. These results indicate the merit of D-wave computer under certain specific instances. More broadly, our method is relevant to other performance comparison studies. We suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also to approximation algorithms with polynomial run-time scaling and a provable guarantee on performance.

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

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

We present a data structure that in a dynamic graph of treedepth at most $d$, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time $2^{{\cal O}(d^2)}$, which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvořák et al. [ESA 2014], who for the same problem achieved update time $f(d)$ for some non-elementary (i.e. tower-exponential) function $f$. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth $d$ from doubly-exponential in $d$ to $d^{{\cal O}(d)}$. As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs. More precisely, for a fixed parameter $k$ and a dynamic graph $G$, modified over time by edge insertions and deletions, our data structures maintain answers to the following queries: - Does $G$ contain a simple path on $k$ vertices? - Does $G$ contain a simple cycle on at least $k$ vertices? In the first case, the data structure achieves amortized update time $2^{{\cal O}(k^2)}$. In the second case, the amortized update time is $2^{{\cal O}(k^4)} + {\cal O}(k \log n)$. In both cases we assume access to a dictionary on the edges of $G$.

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
preprint2018arXiv

The Clever Shopper Problem

We investigate a variant of the so-called "Internet Shopping Problem" introduced by Blazewicz et al. (2010), where a customer wants to buy a list of products at the lowest possible total cost from shops which offer discounts when purchases exceed a certain threshold. Although the problem is NP-hard, we provide exact algorithms for several cases, e.g. when each shop sells only two items, and an FPT algorithm for the number of items, or for the number of shops when all prices are equal. We complement each result with hardness proofs in order to draw a tight boundary between tractable and intractable cases. Finally, we give an approximation algorithm and hardness results for the problem of maximising the sum of discounts.

0 citations0 reviewsNo code linkedOpen access