45 problems

Let $G$ be a general multigraph, let $\chi'(G)$ denote its chromatic index, let $\Delta(G)$ denote its maximum degree, and let $\mathcal{W}(G)$ denote its density parameter. Goldbe…

Let $M$ and $N$ be the numbers of file parts and peers in the dissemination problem, respectively, and let $n$ and $x$ be the parameters defined by the preceding schedule construct…

Sparsest-obstruction conjecture. If

Let $A=(a_i)_{i\in[k]}$ be an integer pinwheel scheduling instance. Its schedulability can be decided by checking whether the finite state-transition graph of $A$ contains a cycle.…

Let a pinwheel scheduling instance $A=(a_i)_{i\in[k]}$ have positive real periods, and define its density by … A schedule must perform each task $i$ at least once in every interval…

Let an instance $A=(a_i)_{i\in[k]}=(a_1,\ldots,a_k)$ consist of positive integer periods, and let its density be … A schedule assigns each task one day at a time while ensuring tha…

Tail-optimality conjecture. In this setting, $\gamma$-CounterBoost is tail optimal among all policies, not only among Contextual CounterBoost policies.

Consider the flow-shop scheduling problem $P \mid a_i \in \{0,1\},\ p_j \in \mathbb{Z} \mid \sum w_j C_j(\alpha)$, where $a_i$ are job arrival times, $p_j$ are processing times,…

One-factorization conjecture. If

Let $\Delta_i$ denote the window width assigned to client $i$ by WOS, and let $\Delta$ denote the common window width assigned by UWOS. WOS–UWOS window-width conjecture. For WOS,…

Monotone-intensity sequencing conjecture. When the NHPP intensity function is monotone, SPT is optimal whenever $\lambda(t)$ is decreasing, and LPT is optimal whenever $\lambda(t)$…

Let $\alpha^*$ be the approximability threshold for Optimisation Poly Scheduling: efficient polynomial-time approximation algorithms with approximation ratio $\alpha$ exist if and…

NP-hardness conjecture. This problem is $\mathcal{NP}$-hard.

Fixed-point conjecture. When $5cgamma$ is close to $1$, the limits $\bar{\bf u}$ and ${\bf \bar v}$ should be approximately equal; consequently, as $5cgamma\to1$ from above, one sh…

FCFS strong tail optimality conjecture. FCFS is strongly tail optimal for class-I job sizes: for every scheduling algorithm $\pi$,

Wierman's conjecture. FCFS is strongly optimal for light-tailed job size distributions. The conjecture concerns the unresolved problem of strong asymptotic tail optimality; FCFS is…

The problem is single-machine scheduling with one non-renewable resource, where each job's resource requirement equals its weight, and the objective is to minimize total weighted c…

Let $I:=\{\alpha_i\}$ be an instance of the Pinwheel Problem, where each integer $\alpha_i\geq 1$, and let … be its density. An instance is schedulable if there exists an infinite…

Consider the single-machine scheduling problem $1|nr=1,p_j=1,w_j=a_j|\sum w_jC_j$, where each job $j$ has unit processing time, weight $w_j$, and non-renewable resource requirement…

In an M/G/1 queue with unknown job sizes, let M-SERPT denote the scheduling policy that prioritizes jobs according to their expected remaining processing time, and let its approxim…

Let $G$ be a discrete bamboo garden trimming instance with bamboos $b_1,\ldots,b_n$ and daily growth rates $h(1)\geq\cdots\geq h(n)$. Let $H^*$ denote the optimal solution value, a…

Let $cpi$ be a scheduling policy and let $cpi_{\rm I}$ denote its informative version; an informative policy prioritizes informative updates and discards non-informative updates wh…

Consider the scheduling policies described above for a single-server queue, including size-based policies such as SJF, preemptive SJF, and SRPT, and let AoI denote age of informati…

Chan's density conjecture. Every vector $v$ with

NP-hardness conjecture. The problem $P|\textit{partition}|\sum_j C_j$ is $\mathcal{NP}$-hard.