%% from ICML 2022: up to eight pages long, followed by unlimited pages for references and an appendix, all in a single file 

%%%%%%%% ICML 2022 EXAMPLE LATEX SUBMISSION FILE %%%%%%%%%%%%%%%%%

\documentclass[nohyperref]{article}

% Recommended, but optional, packages for figures and better typesetting:
\usepackage{microtype}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{booktabs} % for professional tables

% hyperref makes hyperlinks in the resulting PDF.
% If your build breaks (sometimes temporarily if a hyperlink spans a page)
% please comment out the following usepackage line and replace
% \usepackage{icml2022} with \usepackage[nohyperref]{icml2022} above.
\usepackage{hyperref}


% Attempt to make hyperref and algorithmic work together better:
\newcommand{\theHalgorithm}{\arabic{algorithm}}

% Use the following line for the initial blind version submitted for review:
\usepackage{icml2022}

% If accepted, instead use the following line for the camera-ready submission:
% \usepackage[accepted]{icml2022}

% For theorems and such
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsthm}

% if you use cleveref..
\usepackage[capitalize,noabbrev]{cleveref}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% THEOREMS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{observation}[theorem]{Observation}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

% Todonotes is useful during development; simply uncomment the next line
%    and comment out the line below the next line to turn off comments
%\usepackage[disable,textsize=tiny]{todonotes}
\usepackage[textsize=tiny,textwidth=1.6cm]{todonotes}

\newcommand{\alexinline}[1]{\todo[linecolor=orange,backgroundcolor=orange!25,bordercolor=orange,inline]{Alex:~#1}}
\newcommand{\alex}[1]{\todo[linecolor=orange,backgroundcolor=orange!25,bordercolor=orange]{Alex:~#1}}
\newcommand{\nic}[1]{\todo[backgroundcolor=blue!25,bordercolor=blue]{N:~#1}}
\newcommand{\nicinline}[1]{\todo[linecolor=blue,backgroundcolor=blue!25,bordercolor=blue,inline]{Nic:~#1}}
\newcommand{\jens}[1]{\todo[backgroundcolor=green!25,bordercolor=green]{J:~#1}}
\newcommand{\jinline}[1]{\todo[backgroundcolor=green!25,bordercolor=green,inline]{J:~#1}}

\newcommand{\anew}[1]{{\color{orange}#1}}
\newcommand{\nnew}[1]{{\color{blue}#1}}
\newcommand{\jnew}[1]{{\color{green!50!black!50}#1}} % Jens
\newcommand{\red}[1]{\textcolor{red}{#1}}
% alex/ola
\newcommand{\ola}[1]{\todo[linecolor=green,backgroundcolor=green!25,bordercolor=red!60]{Ola:~#1}}

\newcommand{\greennote}[1]{\todo[linecolor=green,backgroundcolor=green!25,bordercolor=green]{#1}}



% my commands
\usepackage{bm}
\usepackage{enumerate}
\usepackage{thm-restate}
\usepackage{xspace}
\usepackage{csquotes}

\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\bigO}{\mathcal{O}} 
\newcommand{\A}{\ensuremath{\mathcal{A}}\xspace}
\newcommand{\hA}{\ensuremath{\bar{\mathcal{A}}}\xspace}
\newcommand{\B}{\ensuremath{\mathcal{B}}\xspace}
\newcommand{\EX}{\mathbb{E}}
\newcommand{\alg}{{\normalfont\textsc{Alg}}}
\newcommand{\opt}{{\normalfont\textsc{Opt}}}
\newcommand{\cA}{\ensuremath{\mathcal{A}}\xspace}
\newcommand{\cB}{\ensuremath{\mathcal{B}}\xspace}
\newcommand{\cS}{\ensuremath{\mathcal{S}}}
\newcommand{\hsigma}{\hat{\sigma}}
\newcommand{\hC}{\bm\hat{C}}
\newcommand{\hc}{{\bm\hat{c}}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\hcI}{\bm\hat{\mathcal{I}}}
\newcommand{\hw}{\bm\hat{w}}
\newcommand{\hW}{\bm\hat{W}}
\newcommand{\hchains}{\bm\hat{\mathcal{C}}}
\newcommand{\bchains}{\bm\bar{\mathcal{C}}}
\newcommand{\chains}{\mathcal{C}}
\newcommand{\optspeed}{\alpha}
\newcommand{\numc}{\omega}
\newcommand{\hpreceq}{\bm\hat{\preceq}}
\newcommand{\dualSa}{\bm\bar{a}}
\newcommand{\dualSb}{\bm\bar{b}}
\newcommand{\dualSc}{\bm\bar{c}}
\newcommand{\dualVa}{a}
\newcommand{\dualVb}{b}
\newcommand{\dualVc}{c}
\newcommand{\df}{dual-fitting\xspace}
\newcommand{\frontjobs}{F}
\newcommand{\average}{a}
\newcommand{\averagep}{\ensuremath{\hat{a}}}

\newcommand{\largestinv}{\mathcal{L}}




% The \icmltitle you define below is probably too long as a header.
% Therefore, a short form for the running title is supplied here:
\icmltitlerunning{Submission and Formatting Instructions for ICML 2022}

\begin{document}

\twocolumn[
\icmltitle{How much Information is Sufficient for Scheduling with Online Precedence Constraints?}
%% Parsimonious Advice for Scheduling with Online Precedence Constraints
%% Minimalistic Advice for Scheduling with Online Precedence Constraints
%How much Information Suffices to Solve Scheduling with Online Precedence Constraints?}


% It is OKAY to include author information, even for blind
% submissions: the style file will automatically remove it for you
% unless you've provided the [accepted] option to the icml2022
% package.

% List of affiliations: The first argument should be a (short)
% identifier you will use later to specify author affiliations
% Academic affiliations should list Department, University, City, Region, Country
% Industry affiliations should list Company, City, Region, Country

% You can specify symbols, otherwise they are numbered in order.
% Ideally, you should not use this facility. Affiliations will be numbered
% in order of appearance and this is the preferred way.
\icmlsetsymbol{equal}{*}

\begin{icmlauthorlist}
\icmlauthor{Firstname1 Lastname1}{equal,yyy}
\icmlauthor{Firstname2 Lastname2}{equal,yyy,comp}
\icmlauthor{Firstname3 Lastname3}{comp}
\icmlauthor{Firstname4 Lastname4}{sch}
\icmlauthor{Firstname5 Lastname5}{yyy}
\icmlauthor{Firstname6 Lastname6}{sch,yyy,comp}
\icmlauthor{Firstname7 Lastname7}{comp}
%\icmlauthor{}{sch}
\icmlauthor{Firstname8 Lastname8}{sch}
\icmlauthor{Firstname8 Lastname8}{yyy,comp}
%\icmlauthor{}{sch}
%\icmlauthor{}{sch}
\end{icmlauthorlist}

\icmlaffiliation{yyy}{Department of XXX, University of YYY, Location, Country}
\icmlaffiliation{comp}{Company Name, Location, Country}
\icmlaffiliation{sch}{School of ZZZ, Institute of WWW, Location, Country}

\icmlcorrespondingauthor{Firstname1 Lastname1}{first1.last1@xxx.edu}
\icmlcorrespondingauthor{Firstname2 Lastname2}{first2.last2@www.uk}

% You may provide any keywords that you
% find helpful for describing your paper; these are used to populate
% the "keywords" metadata in the PDF but will not be shown in the document
\icmlkeywords{Machine Learning, ICML}

\vskip 0.3in
]

% this must go after the closing bracket ] following \twocolumn[ ...

% This command actually creates the footnote in the first column
% listing the affiliations and the copyright notice.
% The command takes one argument, which is text to display at the start of the footnote.
% The \icmlEqualContribution command is standard text for equal contribution.
% Remove it (just {}) if you do not need this facility.

%\printAffiliationsAndNotice{}  % leave blank if no need to mention equal contribution
\printAffiliationsAndNotice{\icmlEqualContribution} % otherwise use the standard text.

Titel mit Aussage wäre stärker als eine Frage; Alternative:\\ Parsimonious/Minimalistic Advice for Scheduling with Online Precedence Constraints

\begin{abstract}


\end{abstract}

%
%\begin{itemize}
%	\item Menge an Ketten $\chains$ und $\chains(t)$ set of alive chains at time $t$
%	\item $C_j$ completion time
%	\item $c$ oder $c_i$ ist eine Kette.
%	\item $\texttt{numc}$ Anzahl Ketten (Macro für $\numc$:= Anzahl der Ketten)
%	\item $W(t)$ Remaining weight
%	\item $W_c(t)$ Remaining weight of chain $c$
%	\item $W_{c_i}(t)$ Remaining weight of chain $c_i$
%	\item $U_t$ Unfinished jobs at time $t$
%	\item Predictions mit Hat: $\hc, \hw, \hC, \hchains, \hpreceq$
%\end{itemize}


\section{Introduction}

Cloud computing is a popular approach to outsource heavy computations to specialized providers~\cite{Hayes08}. Concepts like Function-as-a-Service (FaaS) offer users on demand the execution of complex computations in a specific domain~\cite{LynnRLE17,ShahradBW19}. Such tasks are often decomposed into smaller jobs, which then depend on each other by passing intermediate results. The structure of such tasks heavily relies on the users input and internal dependencies within the users system. It might require diverse jobs to solve different problems with distinct inputs. 
%Further, users could be highly interested in intermediate results, such as approximate solutions, without even expecting such in advance.
From the providers perspective, the goal is thus to schedule jobs with different priorities and interdependencies % between them, 
which become known only when certain jobs are completed and their results can be evaluated. 
From a more abstract perspective, we %are faced with 
face \emph{online precedence constraint scheduling}: new jobs arrive only if certain jobs have been completed but the set of jobs and their dependencies are unknown to the scheduler. As tasks might have different priorities, it is a natural objective %to study is 
to minimize the total (average) weighted completion time of the jobs.
%Practice-relevant are especially 
We focus on \emph{non-clairvoyant} schedulers that do not know a job's processing requirement in advance~\cite{motwani1994nonclairvoyant}, and we allow \emph{preemptive} schedules, i.e., jobs can be interrupted and resumed later.
In this paper, we present and analyze non-clairvoyant algorithms and prove impossibility results for this problem.

Competitive analysis is a widely used technique to assess the performance of online algorithms~\cite{Borodin98}. The \emph{competitive ratio} of an algorithm is the maximum ratio over all instances between its objective value and the objective value of an \emph{offline} optimal solution. In our setting, an offline optimal solution is the best schedule that can be computed with complete information and unbounded running time on the instance. We say that an algorithm is $\rho$-competitive if its competitive ratio is at most $\rho$.
%However, as being a worst-case performance measure, 

It is not hard to see that for our problem, we cannot hope for good worst-case guarantees: consider an instance of $n-1$ initially visible jobs with zero weight such that exactly one of these jobs triggers at its completion the arrival of a job with positive weight.
Since the initial jobs are indistinguishable, in the worst-case, any algorithm completes the positive-weight job last.
An offline optimal solution can distinguish the initially visible jobs and immediately processes the one which triggers the positive-weight job. 
This already shows that no deterministic algorithm can have a better competitive ratio than $\Omega(n)$ for $n$ jobs. Notice, that this strong impossibility result holds even for (seemingly) simple precedence graphs that consist of a collection of chains. Yet, in practice, such topology is highly relevant as, e.g., a sequential computer program executes a path (chain) of instructions that upon execution depends on the evaluation of control flow structures~(cf.~\cite{Allen1970control}).

To overcome such daunting lower bounds, there are closer-to-real-world approaches to go beyond worst-case analysis such as augmenting \emph{algorithms with predictions}~\cite{MitzenmacherV22,MitzenmacherV20}. The intuition is that in many applications, we can learn certain aspects of the uncertainty by considering historical data such as dependencies between jobs for certain computations and inputs. While these predictions might not reflect the current instance, they can contain enough information to design algorithms that break pessimistic worst-case lower bounds. Besides specifying the type of information, this requires a measure for a prediction's quality. This allows parameterized performance guarantees of algorithms w.r.t. the amount of information a prediction contains for the given instance.
Important performance indicators are \emph{consistency}, that is the competitive ratio for best-possible predictions, and \emph{robustness}, that is an upper bound on the competitive ratio for any prediction.

%Although research on learning-augmented algorithms exploded in the past couple of years~\cite{alps}, explaining the choice of a certain prediction model is quite uncommon. 
Despite the immense research interest in learning-augmented algorithms in the past couple of years~\cite{alps}, the choice of prediction models remains often undiscussed.
We present results for various prediction models, and work out their strengths and weaknesses. In particular, we present the first learning-augmented algorithms for scheduling with online precedence constraints.
Our main goal is to answer the following question:
\begin{quote}
    \emph{%How much\nic{How much kann eigentlich raus.} and 
    Which particular information is required to achieve reasonable performance guarantees for scheduling with online precedence constraints?}
\end{quote}
Starting with the two most studied main models, \emph{action} and \emph{full input} predictions, we consider a hierarchy of prediction models based on their entropy in the sense that one can compute a prediction for a weaker model using a prediction from a stronger one, but not vice versa. For each model in the hierarchy, we provide efficient algorithms and lower bounds on the best-possible performance guarantees w.r.t.~these models and w.r.t. topological properties of the structure of the precedence constraints. %But before that, 
%Before stating our results, we precisely define the problem.\nic{Mention in this paragraph also graph topology?}\alex{I tried something}

% \alexinline{Move this somewhere else or split up:}
% Whether a prediction model leads to improved guarantees also depends on the topology of the unknown precedence constraints graph\ola{graph not yet defined}. As explained before, without any predictions, no algorithm can be better than -competitive even if the graph is a set of disjoint chains. For our analysis of different prediction models, we categorize the graphs into three, behaviour-wise distinct structures: chains, trees and general direct acyclic graphs.


% \begin{itemize}
%     \item Precedence-constrained scheduling has many important applications. Solving complex computations involve precedence-constrained non-clairvoyant jobs. However, additional steps of computation may depend on the outcome of a task and can be completely uncertain. Serving customers may result in new tasks for other customers. In general, we cannot assume that we know which jobs succeed another job until that job has been completed. We call this setting online precedence constraints, i.e. we only see succeeding jobs after all predecessors have been completed.
%     \item Independent tasks can be modelled as chains. There could be less important subtasks such as cleanup tasks.
%     \item Notoriously hard problem in both weighted and unweighted variants when using classic worst-case analysis. New models are required.
%     \item In particular, where does the hardness of the uncertainty come from? Which information suffice to design competitive algorithms? Which information may be realistic to predict? 
%     \item First learning-augmented algorithms for precedence constrained scheduling.
%     \item Pattern in precedences can be learned. Similar task sets may arrive on a daily basis. Similar tasks may have similar successors.
%     \item We are interested in prediction models for learning-augmented algorithms. In particular, which consistencies are possible and possibly sensistivity of mispredictions. Robustness is not really important, due to hard lower bounds.
%     \item In previous work in the field of algorithms with predictions prediciton models are fixed without giving particular reasons. We want to give a full picture of realistic prediction models and their strengths and weaknesses. We also want to start research on possible classifations of prediciton models, in particular dynamic vs static and input vs action predictions.
%     \item We consider non-clairvoyant setting, hence preemption is necessary.
%     \item Pure online LB
% \end{itemize}

\subsection{Problem Definition and Prediction Models}

%Our goal is to understand what amount of predicted information is necessary to break the known lower bounds for scheduling with online precedence constraints.

An instance of our problem is composed of a set~$J$ of~$n$ jobs and a precedence graph~$G$, which is an acyclic directed graph (DAG) with node set~$J$. Every job~$j$ has a processing requirement~$p_j \geq 0$ and a weight~$w_j \geq 0$. An edge in~$G$ from job~$j'$ to job~$j$ in~$G$ indicates that~$j$ can only be started if~$j'$ has been completed. If there is a directed path from $j'$ to $j$ in $G$, then we say that~$j$ is a \emph{successor} of~$j'$ and that~$j'$ is a \emph{predecessor} of~$j$. If that path consists of a single edge, we call $j$ and $j'$ a \emph{direct} successor and predecessor, respectively.
For a fixed precedence graph~$G$, we denote by~$\numc$ the \emph{width} of~$G$, which is the length of the longest anti-chain in~$G$.

An algorithm can process a job $j$ at a time $t$ with a rate $L_j^t$, which describes the amount of processing the job receives at time $t$. The completion time~$C_j$ of a job~$j$ is the first time~$t$ which satisfies~$\sum_{t' = 0}^t L_j^{t'} \geq p_j$. We consider a single machine problem, hence require $\sum_{j \in J} L_j^t \leq 1$ at any time $t$.
At any time~$t$ in an algorithm's schedule, let~$\frontjobs_t$ denote the set of unfinished jobs that have no unfinished predecessors in~$G$, i.e., 
\[
    \frontjobs_t = \left\{j \; \mid \; C_j > t \text{ and } \forall j' \text{ s.t. } (j', j) \in E(G) \colon C_{j'} < t  \right\}.
\]
We refer to such jobs as \emph{front jobs}. In the online setting, a job is only revealed to the algorithm once all predecessors have been completed. Thus, at any time~$t$ an algorithm only \emph{sees} jobs $j\in$ $\frontjobs_t$ with weights $w_j$ but {\em not} their processing times $p_j$. Note that the sets~$\frontjobs_t$ heavily depend on an algorithms actions. At the start %of the instance 
time $t=0$, an algorithm sees the initial front jobs~$\frontjobs_0$, and %in particular does not know the total number of jobs in advance. 
until the completion of the last job, it does not know the total number of jobs.
An algorithm can at any time~$t$ only process front jobs, hence we further require that~$L_j^t = 0$ for all~$j \in J \setminus \frontjobs_t$.
The objective function of our problem is equal to~$\sum_{j \in J} w_j C_j$, which we seek to minimize. For a fixed instance we denote the optimal objective value by~$\opt$ and for a fixed algorithm its objective value by~$\alg$.



%In this paper 
We study different topologies of precedence graphs. As special cases of %general 
DAGs, we consider \emph{in-forests} resp.\ \emph{out-forests}, where every node has at most one outgoing resp.\ incoming edge. As further specialization of both, we say that a precedence graph is composed of \emph{chains} if it is an in-forest and a out-forest simultaneously. 
If an in-forest or out-forest has only one connected component, we refer to it as \emph{in-tree} and \emph{out-tree}, respectively.
%Observe that any upper bound for an algorithm restricted to a topology implies the same bound for specialized topologies, and any lower bound on an algorithm for a topology implies the same lower bound for more general topologies.\nic{braucht man diesen Satz eigentlich? Naja, wenn Platz ist.} \alex{Ja stimmt das sollte eigentlich offensichtlich sein.} %\nic{I moved the pro-chain argument to the beginning.}
%In particular, the previously explained~$\Omega(n)$ lower bound on the competitive ratio of any algorithm without additional information already holds on chains.
%Since the control flow of a sequential computer program is a chain that upon execution depends on the evaluation of control flow structures~(cf.~\cite{Allen1970control}), we argue that even the special case of chains has practical relevance.\ola{I think we should elaborate on this. Perhaps from the point of view "three models characterizing the powerfulness of our algorithms?"}\alex{Maybe move this pro-chain argument somewhere earlier, and indead of chains write linear precs or smth?}

We now introduce our prediction models. %, and start with considering 
Two of the most studied prediction models in learning-augmented algorithm design are: 
\begin{itemize}
    \item \emph{Full input predictions:} A prediction on the set of jobs with processing times and weights, and the complete precedence graph. 
    \item \emph{Action predictions:}  A prediction on a full priority order over all jobs that are predicted to be part of the instance (\emph{static actions}) or a prediction on which job to schedule next in the beginning or whenever we finish processing a job (\emph{adaptive actions}). 
\end{itemize}

%\nicinline{Den folgenden Satz verstehe ich nicht. Eigentlich den ganzen Absatz nicht.\\ Vorschlag: Both prediction models require learning a substantial amount of information on the input instance and/or an optimal algorithm. This might be unrealistic and may not even be necessary for an algorithm to perform well. We aim for minimalistic additional information and quantify  its power.}
Both prediction models require learning a substantial amount of information on the input instance and/or an optimal algorithm. This might be unrealistic and may not even be necessary for an algorithm to perform well. We aim for minimalistic additional information and quantify its power.
%Note that in both prediction models, we expect an algorithm which follows them to retrieve an optimal solution if the predictions are accurate.
%Both intuitively require to learn a significant amount of information on the input instance. In particular, for full input predictions, we need to learn the complete instance, including the complete precedence graph. 
%Since this amount of information is most often impossible to obtain, we consider further models that predict less information about the input.

%For any point in time~$t$ during the scheduling of the instance, let~$\frontjobs_t$ denote the set of jobs that are known to the scheduler but not yet completed. We refer to such jobs as \emph{front jobs}.
%Then,~$F_0$ contains the jobs that are initially known, i.e., the jobs without predecessors in the precedence constraint graphs\ola{graph not yet defined.}\alex{Yes, we should introduce precedence graphs before this paragraph.}. For~$t > 0$, the set~$F_t$ depends on what jobs have already been scheduled. 
%To this end, 
Note that even without predictions, an algorithm sees all
jobs in~$\frontjobs_0$. Thus, to break the corresponding lower bounds, we need predictions that go beyond the set~$\frontjobs_0$. To that end, we consider various predictions on the set~$S(v)$ consisting of a front job~$v \in \frontjobs_0$ and all successors of~$v$:
\begin{itemize}
	\item \emph{Weight predictions:} Predictions on the total weight of the successors of each front job, i.e., predictions~$\hW_{S(v)}$ on~$W_{S(v)} = \sum_{u \in S(v)} w_u$ for each~$v \in \frontjobs_0$. 
	\item \emph{Average predictions:} Predictions on the average weight of the successors of each front job, i.e., predictions~$\averagep_{S(v)}$ on~$\average_{S(v)}= \frac{\sum_{u \in S(v)} w_u }{\sum_{u \in S(v)} p_u }$ for each~$v \in \frontjobs_0$. 
	\item \emph{Weight order predictions:} Predictions on the weight order of the front jobs. The \emph{weight order}~$\preceq_0$ over~$\frontjobs_0$ sorts the jobs~$v \in \frontjobs_0$ according to non-increasing~$W_{S(v)}$, i.e.,~$v \preceq_0 u$ implies~$W_{S(v)} \geq W_{S(u)}$. We assume access to a prediction~$\hpreceq_0$ on~$\preceq_0$.
\end{itemize} 
For each of these three models, we distinguish \emph{static} and \emph{adaptive} predictions. Static predictions refer to predictions only on the initial front jobs~$\frontjobs_0$, and adaptive predictions refer to a setting where we receive access to new predictions on the set of front jobs whenever the set changes.

\subsection{Our Results}
\nic{Bei Platzbedarf könnte diese Section kompakter formuliert werden.}

All our results roughly fall into two categories. First, we consider the problem of scheduling with online precedence constraints with access to additional \emph{reliable} information. In particular, we consider all the prediction models of the previous section and design upper and lower bounds for the online problem enhanced with access to the respective additional information. We aim at classifying the power of the different types of information when solving the problem on different topologies. This is still a pure online setting, where we assume all available information to be accurate. 

For the second type of results, we drop the assumption that the additional information is accurate and turn our pure online results into learning-augmented algorithms. To that end, we define suitable error measures for the different prediction models to capture the accuracy of the predictions, and give more fine-grained competitive ratios depending on these measures. 
Since our measures must depend on the given predictions, we need different measures for the different models. To give competitive ratios depending on these measures, they have to capture the impact of the predictions for solving the scheduling problem.
In particular for \enquote{sparse} prediction models, formulating such error measures is challenging.
In addition to designing algorithms with error-dependent competitive ratios, we also show how to extend them to achieve robustness. 

In the following, we give an overview of our results for the two categories. We prove all results for the single machine setting but remark that they extend to identical parallel machines as we show in Appendix~\ref{TODO}. 

\paragraph{Results for reliable additional information} 
\Cref{table:summary} gives an overview over our result for the online setting enhanced with reliable additional information. Recall that lower bounds for strictly more powerful prediction models imply the same bounds for weaker models, e.g., the lower bound of~$\Omega(\sqrt{n})$ for in-forests and adaptive weight predictions translates to the less powerful static weight predictions.


\begin{table}[tb]
	\caption{Summary of bounds on the competitive ratio given reliable information. We denote by~$P$ the total processing time and by~$H_k$ the~$k$th harmonic number.}
	\label{table:summary}
	\begin{center}
		\begin{tabular}{lll}
			\toprule
			Prediction Model & Topology & Bound  \\
			\midrule
			Actions & DAG & $\Theta(1)$ \\
			Input & DAG & $\Theta(1)$ \\
			Adaptive weights & Out-Forests & $\Theta(1)$\\
			Adaptive weights & In-Trees & $\Omega(\sqrt{n})$\\
			Static weights & Out-Trees & $\Omega(n)$ \\
			Static weights & Chains & $\Theta(1)$ \\
			Adaptive weight order & Chains & $\bigO(H_\numc)$ \\
			Adaptive weight order & Out-Forests & $\bigO(H_\numc)$ \\
			Static weight order & Chains & $\bigO(H^2_\numc \sqrt{P})$ \\
			Adaptive averages & Forests & $\Omega(\sqrt{n})$\\
			Adaptive averages & Chains & $\Omega(\sqrt{n})$\\
			No Prediction & Chains & $\Omega(n)$  \\
			\bottomrule
		\end{tabular}
	\end{center}
\end{table}


Our main algorithmic results are a~$4$-competitive algorithm for chains with static weight predictions, a~$4$-competitive algorithm for out-forests with adaptive weight predictions, and an~$H_{\numc}$-competitive algorithm for chains with adaptive weight order predictions, where~$H_k$ denotes the~$k$th harmonic number. 
Observe that for chains,~$\numc$ coincides with the number of chains of the graph. All these results show that the corresponding additional information allows a significant improvement over having no extra information. % the lower bound without access to the information.

To achieve the competitive ratio of~$4$, we show that the well-known Weighted Round Robin algorithm (WRR)~\cite{motwani1994nonclairvoyant,KimC03a} for non-clairvoyant scheduling \emph{without} precedence constraints, which advances jobs proportional to their weight, can be generalized to our setting.
%\ola{We have not said before that we can preempt jobs/ schedule jobs in parallel. Should that be a condition stated fairly in the beginning or does it make our setting sound too restrictive then?}
We handle each chain as a superjob and update their weights when jobs are completed. Due to these dynamics, the original analysis of WRR is not applicable. Instead, we use the \df technique, which has been previously used to analyze a variation of WRR for the setting where precedence constraints exist but are known upfront~\cite{GargGKS19}. Although this information is not given in our model and hence, their analysis is also infeasible, we prove necessary conditions on an algorithm to make the \df work, which are fulfilled even in our setting with limited information. Surprisingly, we show that a weaker linear programming relaxation, which does not consider transitive precedences, is sufficient to prove small constants. In particular, it allows us to use a dual assignment that is a lot simpler than the one used in~\cite{GargGKS19}.

In the more restricted model where only the order of the total chain weights is known, WRR cannot be applied, as the rate computation crucially relies on precise weight values. We observe, however, that WRR's rates at the start of an instance have the same ordering as the known chain order. We show that guessing rates for chains in a way that respects the ordering compromises only a factor of at most~$H_\numc$ in the competitive ratio. Note that the total remaining weights of the chains change when jobs are being completed, and so does their chain ordering. We show that if the weight order is adaptive, we can actually achieve a competitive ratio of~$\bigO(H_\numc)$. Otherwise, we give a worse upper bound, and give evidence that this might be best-possible for this algorithm.

\paragraph{Learning-augmented results} We extend all our algorithmic results (cf.~\Cref{table:summary}) by designing suitable error measures for the different prediction models and proving error-dependent competitive ratios.
Furthermore, we identify and discuss similarities and differences of our measures to already established error measures for different learning-augmented problems. \nic{echt, machen wir das? ;)}\jens{Sollten wir zumindest ;) Können ja später sehen, ob diese Formulierung übertrieben ist..}
We hope that this discussion leads to a better understanding of when certain established error measures can be applied to a problem and prediction model.  

Finally, we show how our error-dependent algorithms can be extended to achieve robustness. 
In particular, we show how existing techniques can be used as a blackbox to give these algorithms a robustness of~$\mathcal{O}(\omega)$ at the loss of only a constant factor in the error-dependent guarantee. %Here,~$\omega(G)$ is the \emph{width} of the precedence constraint graph~$G$ and the width of~$G$ is the length of the largest anti-chain in~$G$.
Note that a robustness~$\mathcal{O}(\omega)$ matches the lower bound for the online problem without access to additional information.








%\alexinline{Diese Section ist schon ein paar Wochen alt und noch nicht so doll.}
%
%We present both, algorithms on the best possible competitive ratio and general lower bounds for these prediction models with respect to the topology of the precedence constraints. An overview over all bounds is provided in \Cref{table:summary}.\alex{we also have to decide if we want the max degree $\Delta$ there or just insert some value.}
%
%
%The most powerful prediction model is the input prediction. Given correct input predictions, it is easy to see that we can compute predictions for all other models. The remaining challenge is to design a meaningful error-dependency. We present a sensible error measure which
%identifies both unexpected and absent weight -- compared to the ground truth -- as the main source of algorithmic mistakes. These error types have been considered previously in~\cite{AzarPT22,XuM22,Bernardini22universal}. We apply this measure to a simple follow-the-prediction algorithm. This is reasonable as robustness is out of reach.\ola{elaborate why is it out-of-reach}
%
%For both, static and adaptive action predictions, a natural error measure based on permutations for the total weight completion time objective without precedence constraints has been introduced in \cite{LindermayrM22}. We generalize their result for a single machine to the setting with precedence constraints and thereby derive an error measure based on permutations between the algorithm's and an optimum's schedule.
%
%Our other algorithmic results concentrate on chain precedence constraints, as more general topologies imply hard lower bounds even when much information is provided.

%\paragraph{Algorithm for total chain weight predictions}
%We present a $4$-competitive, non-clairvoyant algorithm for online chain precedence constraint scheduling assuming the total weight of every chain is given as a prediction. Note that the algorithm is still oblivious to the number of jobs per chain and the distribution of high-weight jobs per chain. This is challenging because an optimal solution clearly handles chains with high front weight differently than chains with high back weight.
%Surprisingly, we show that a generalization of the well-known Weighted Round Robin algorithm (WRR)~\cite{motwani1994nonclairvoyant,KimC03a}, which advances jobs proportional to their weight, is feasible for this task.\ola{We have not said before that we can preempt jobs/ schedule jobs in parallel. Should that be a condition stated fairly in the beginning or does it make our setting sound too restrictive then?} We handle each chain as a superjob and update their weights when jobs are completed. Due to these dynamics, the original analysis of WRR is not applicable. Instead, we use the \df technique, which has been previously used to analyze a variation of WRR for the setting where precedences are known upfront~\cite{GargGKS19}. Although this information is not given in our model and hence, their analysis is also infeasible, we prove necessary conditions on an algorithm to make the \df work, which are fulfilled even in our restricted setting.
%We further extend the analysis and give an error-sensitive performance guarantee w.r.t. to an error function based on under- and overpredicted chain weights.

%\paragraph{Algorithms for chain weight order predictions}
%In the more restricted model where only the order of the total chain weights is known, WRR cannot be applied, as the rate computation crucially relies on precise weight values. We observe, however, that WRR's rates at the start of an instance have the same ordering as the known chain order. We show that guessing rates for chains in a way that respects the ordering compromises only a factor of at most $H_\numc$ in the competitive ratio. Note that the total remaining weights of the chains change when jobs are being completed, and so does their chain ordering. We show that if the weight order is adaptive, we can actually achieve a competitive ratio of $\bigO(H_\numc)$. Otherwise, we give a worse upper bound, and give evidence that it is essentially best-possible for this algorithm.
%For the case of inaccurate predictions, we develop a configurable error measure which describes the pareto-frontier between the maximal distortion factor any two (true) chain weights can admit in the predicted order, and the largest inversion in the predicted order compared to the true order. We prove error-dependencies of our algorithms w.r.t. to all errors in this family.
%
%\paragraph{Extention to out-trees}
%
%\alexinline{TODO}

\subsection{Related Work}

Offline precs sum wjCj

Scheduling jobs with precedence constraints to minimize the sum of (weighted) completion times has been one of the most studied scheduling problems for more than thirty years. The offline problem is known to be NP-hard, even for a single processor~\cite{lawler78,lenstrR78}, and on two machines even when precedence constraints form chains~\cite{duLY91, timkovsky03}. 
%%$ P2 \vert chains;pmtn \vert \sum C_i$ \cite{duLY91} and in the weighted setting even when all jobs have unit processing times~%$ P2 \vert p_i=1;chains;pmtn \vert \sum w_iC_i$~\cite{duLY91,timkovsky03}. 
Several polynomial-time algorithms based on different linear programming formulations achieve an approximation ratio of~$2$ on a single machine, whereas special cases are even solvable optimally; we refer to~\cite{CorreaS05,AmbuhlM09} for comprehensive
overviews.  For scheduling on $m$ parallel identical machines, the best known approximation factor $3-1/m$~\cite{hallSSW97}.


Online precedence constraints \nic{makespan eher weglassen? Nur nennen?}
\begin{itemize}
    \item Related makespan LB \cite{AzarE02}
    \item Related makespan UB \cite{Jaffe80}
    \item Identical makspan LB \cite{Epstein00}
    \item Identical makspan UB \cite{Graham69}
\end{itemize}

Online scheduling with precedence constraints.
\begin{itemize}
    \item Non-clairvoyant: \cite{GargGKS19}
    \item Clairvoyant: \cite{hallSSW97,ChakrabartiPSSSW96,BienkowskiKL21}
\end{itemize}

Learning-augmented algorithms:
\begin{itemize}
    \item scheduling with total completion time: \cite{PurohitSK18,Im0QP21,LindermayrM22,DinitzILMV22portfolios,BampisDKLP22}
    \item action predictions: \cite{AntoniadisCE0S20,BamasMS20,Angelopoulos21,LindermayrMS22,LindermayrM22,EberleLMNS22,Anand0KP22,JinM22}
    \item full input predictions: \cite{PurohitSK18,GollapudiP19,BamasMRS20,WeiZ20,AzarLT21,AzarLT22,AzarPT22,Im0QP21,AntoniadisGS22,Bernardini22universal,ErlebachLMS22,BampisDKLP22,Zhao0Z22}
    \item In-between: e.g. paging stuff, learned duals
\end{itemize}

\section{Robustness via Time-Sharing}

%For our problem, an algorithm can assign at every time~$t$ to every available job~$j \in F_t$ a \emph{rate}~$L_j^t \in [0,1]$. A feasible schedule has to ensure at every time~$t$ that the assigned rates can be actually processed, hence requires~$\sum_{j \in F_t} L_j^t \leq 1$ on a single machine. Positive rates advance jobs by exactly that amount, until the total processing requirement is met. Thus, we denote the completion time~$C_j$ for every job~$j$ as the first time~$t$ which satisfies~$p_j \leq \sum_{t' = 0}^t L_j^{t'}$. For a given schedule, our objective function is equal to~$\sum_{j \in J} w_j C_j$, which we seek to minimize. 

%We only consider \emph{non-clairvoyant} algorithms which are unaware of a jobs processing requirement before it completes. Thus, due to strong lower bounds~\cite{motwani1994nonclairvoyant}, we allow algorithms to preempt jobs and resume them later.\ola{this should come earlier, see above}



In our algorithms, we use the following technique to combine two algorithms for the total weighted completion time objective.

\begin{theorem}[\cite{PurohitSK18,LindermayrM22}]\label{thm:alg-combination}
Given two algorithms with competitive ratios~$\rho_\A$ and~$\rho_\B$ for minimizing the total weighted completion time with online precedence constraints on identical machines, there exists an algorithm for the same problem with a competitive ratio of at most~$\bigO(\min\{\rho_\A, \rho_\B\})$.
\end{theorem}

Note that in \cite{PurohitSK18,LindermayrM22} this statement has an additional monotonicity requirement for both algorithms. We shortly argue in \Cref{app:monotonicity} that this is not necessary on a single machine.



\section{Full Input Predictions}

%We start with full input predictions. It is not hard to see that for any precedence topology, a correct full input prediction implies a $1$-competitive algorithm by just following an optimal solution.\ola{we should state an appropriate offline algorithm here which can compute that}\alex{Hm in general its NP-hard, but we don't care. So just brute force. For chains there are efficient algorithms.} 

Given a full input prediction, any optimal offline algorithm implies a $1$-competitive algorithm by assuming the prediction as actual input. In general, there are only exponential time algorithms as the problem is NP-hard, but for special cases, such as chains or series-parallel graphs, there are polynomial-time algorithms known~\cite{lawler78}.

We focus in this section on a meaningful error measure for incorrect predictions. 
\alexinline{Argue that in non-chains its is not clear how to map things.} 
Therefore, we restrict our attention to the chain topology for defining the \emph{input prediction error $\Lambda$}. The main intuition of this error measure is to capture %charge
 additional cost that any algorithm pays due to both, \emph{absent predicted} weights and \emph{unexpected actual} weights.
%In particular, 
Our error is composed of two sub-errors, which we formally define in \Cref{app:input}. This error measure is in the same spirit as the universal cover error for graph problems in \cite{Bernardini22universal}. Here we give an intuitive description:
\begin{itemize}
    \item $\Gamma_u$ shall measure the cost one has to pay for weights which arrive \emph{unexpected}, i.e. roughly an optimal solution for the instance with weights $\{(w_j - \hw_j)_+\}_j$.
    \item $\Gamma_a$ shall measure the cost one has to pay for weights which stay \emph{absent}, i.e. roughly an optimal solution for the instance with weights $\{(\hw_j - w_j)_+\}_j$.
\end{itemize}

We prove in \Cref{app:input}:

\begin{restatable}{theorem}{thmInputPredErrorDep}
	Given access to an input prediction, there exists an efficient algorithm for minimizing the total weighted completion time of unit-size jobs on a single machine with \nic{Wollen wir $\numc$ reinschreiben?} online chain precedence constraints with a competitive ratio of at most $\bigO(\min \left\{ 1 + \Lambda, \numc \right\})$, where $\Lambda = \Gamma_u + \Gamma_a$.    
\end{restatable}

Note that $\Lambda$ always gives a tighter error %measure 
than %using 
the simple $\ell_1$ norm between $\{w_j\}$ and $\{\hw_j\}$. For that, one can observe that an algorithm which follows $\{\hw_j\}$, %must depend on at least 
has an objective value that diverges from the optimal one by at least %\nic{ist es das was wir sagen wollen? (vorher: "must depend on")} 
$n \cdot \ell_1(\{w_j\}, \{\hw_j\})$. We prove in \Cref{app:input}: % the following bound.

\begin{restatable}{lemma}{inputTighterThanL}
    $\Lambda \leq n \cdot \ell_1(\{w_j\}, \{\hw_j\})$
\end{restatable}
 
The idea of augmenting an algorithm with a prediction on the whole online input has been considered in several works in the field of algorithms with predictions~\cite{PurohitSK18,GollapudiP19,BamasMRS20,WeiZ20,AzarLT21,AzarLT22,AzarPT22,Im0QP21,AntoniadisGS22,Bernardini22universal,ErlebachLMS22,BampisDKLP22,Zhao0Z22}.

\section{Action Predictions}

Similarly to full input predictions, %it is easy to see that 
following an accurate action prediction results in an optimal solution.
To define a unified error measure for erroneous static and adaptive action predictions, let $\hsigma: J \to [n]$ be the order in which a fixed %\nic{"the order in which an alrithm followed the prediction" - was soll das heissen? for any possible set of front jobs, it indicates which job should run?!}
static or adaptive action prediction suggests to process jobs. 
Using this, we can analyze an algorithm which follows a static or adaptive action prediction using the permutation error introduced in \cite{LindermayrM22}.
To this end, let $\sigma: J \to [n]$ be the order of a fixed optimal solution for instance $J$, and $\mathcal{I}(J, \hsigma) = \{ (j', j) \in J^2 \mid \sigma(j') < \sigma(j) \land \hsigma(j') > \hsigma(j) \}$ be the set of inversions between the permutations $\sigma$ and $\hsigma$. 
By referring to the analysis given in \cite{LindermayrM22}, we immediately conclude the following result for online precedence constrained scheduling.

\begin{theorem}
	Given access to static or adaptive action predictions, there exists an efficient algorithm for minimizing the total weighted completion time on a single machine with online chain precedence constraints with a competitive ratio of at most $\bigO(\min \left\{ 1 + \eta, \numc \right\})$, where 
    \[
    \eta = \sum_{(j', j) \in \mathcal{I}(J, \hsigma)} (w_{j'} p_j - w_j p_{j'}).	
    \]
\end{theorem}


Finally, we remark that in several previous learning-augmented works, considered predictions models can be interpreted as static or adaptive action prediction~\cite{AntoniadisCE0S20,BamasMS20,Angelopoulos21,LindermayrMS22,LindermayrM22,EberleLMNS22,Anand0KP22,JinM22}.


\section{Weight value predictions}
%\ola{different types of trees nit yet introduced}
%\subsection{Weight Values}
Recall that (static) weight predictions are predictions $\hW_{S(v)}$ on $W_{S(v)} = \sum_{u \in S(v)} w_u$ for all front jobs $v \in F_0$.
In this section, we first show a lower bound of $\Omega(n)$ on the competitive ratio of algorithms with access to static weight predictions, even if the precedence constraint graph is an in- or out-tree. For adaptive weight predictions and in-trees, we give a lower bound of $\Omega(\sqrt{n})$. 

%For a slightly stronger variant of static weight predictions, we show corresponding lower bounds of $\Omega(n^{\frac{1}{2}})$ and $\Omega(n^{\frac{1}{4}})$, respectively.

On the positive side, we give an $4$-competitive algorithm
for static weight predictions if the precedence constraint graph is a set of disjoint chains. 
We extend this result to an $\mathcal{O}(n)$-robust algorithm with smooth error dependency. For adaptive predictions, we can obtain an improved error dependency.
This latter result also translates to out-forests.

%For out-trees and adaptive weight predictions, we give an $\mathcal{O}(1)$-competitive algorithm. For in-trees, the lower bound of $\Omega(n^{\frac{1}{4}})$ for the slightly stronger prediction variant holds even in the adaptive case.

\subsection{Lower bounds}

The following lower bound for out-trees with static weight predictions can easily be shown by adding a dummy root $r$ to the lower bound instance for online algorithms without access to predictions.
Then, $r$ is the only initial front job and $S(r)$ is just the set of all jobs.
Thus, the static weight prediction for $r$ just predicts the total weight over all jobs, which does not help in the lower bound instance.

\begin{observation}
	\label{obs:lb-trees-static}
Any algorithm with access to static weight predictions has a competitive ratio	of at least $\Omega(n)$, even if the precedence constraint graph is an out-tree.
\end{observation} 

For in-trees, we show the following lower bound for adaptive weight predictions. Note that this is in contrast to out-trees for which we show in~\Cref{sec:weight-order} that a logarithmic competitive ratio is possible.

%Even for a slightly stronger prediction variant, where we have access to predictions on the total weight of any root-leaf path in the precedence constraint graph, we can give a similarly strong lower bounds.\alex{I think this section is confusing, because the following two prediction models were not introduced before. Maybe we should highligh this more, e.g. with a paragraph: Strong lower bounds for stronger prediction models.}

\begin{lemma}
	\label{lb:in-trees}
Any algorithm with access to adaptive weight predictions has a competitive ratio	of at least $\Omega(\sqrt{n})$, even if the precedence constraint graph is an in-tree.
\end{lemma}

\begin{proof}
Consider an in-tree instance with unit-size jobs and root~$r$ of weight~$0$. There are~$\sqrt{n}$ chains of length~$2$ with leaf weights~$0$ and inner weights~$1$ which are connected to~$r$. Further, there are~$n-2\sqrt{n}-1$ leaves with weight 0, which are connected to a node~$v$ with weight~$1$, which itself is a child of~$r$.
Note that the weight prediction for all potential front jobs except $r$ is always $1$. Thus, even the adaptive predictions do not help, and we can assume that the algorithm first processes the children of~$v$, giving a total objective of at least~$(n-2\sqrt{n}-1)^2 + (n-2\sqrt{n}-1)\sqrt{n} = \Omega(n \sqrt{n})$, while processing the other leaves first yields %a solution of cost 
a value of at most~$(2\sqrt{n})^2 + (2\sqrt{n} + n-2\sqrt{n}) = \bigO(n)$.
\end{proof}

In the appendix, we consider a stronger variant of static weight predictions for out-trees that decomposes the weight prediction on the root into weight predictions for each root-leaf path. Even then, no constant or even logarithmic competitive ratio is possible.

%\jnew{For out-trees, even access to stronger static}


%	\jnew{We remark that, if the precedence constraint graph is an out-tree, even for a slightly stronger static prediction variant, where we have access to predictions on the total weight of any root-leaf path in the precedence constraint graph, we can give a similarly strong lower bounds }


%We remark that adaptive weight predictions do not help when solving this lower bound instance. %Thus, the result transfers to such predictions

\subsection{An algorithm for chains and reliable information}

We give an algorithm %for processing chains on a single machine that is constant competitive given 
assuming access to {\em correct} static weight predictions. For chains, the set~$F_0$ of initial front jobs consists exactly of the first jobs of all chains, and the set~$S(v)$ for a front job~$v$ is exactly the set of jobs in the chain~$c$ of~$v$, i.e.,~$S(v)=c$. Thus, for each chain~$c$ in the set of chains~$\chains$, we have access to a prediction~$\hW_c$ on the total weight of the chain~$W_c = \sum_{j \in c} w_j$. For ease of analysis, we write $u \prec v$ for two jobs $u,v$ if $u$ directly precedes $v$.
In this section, we %only consider the case of correct predictions and, therefore, 
assume %access to~$W_c$ 
$\hW_c = W_c$, for all~$c \in \chains$, and in the following section, we extend the algorithm to a robust algorithm with error-dependency.

%To that end, 
We introduce Algorithm~\ref{alg:chain-robin}. %In the algorithm,
We let~$U_t$ refer to the set of unfinished jobs at time~$t$, i.e. $U_t = \bigcup_{v \in F_t} S(v)$. %and~$I_t \subseteq U_t$ refers to the sets of available jobs at time~$t$, \anew{i.e. jobs $j$ with $r_j \leq t \leq C_j$}
%For a set of jobs~$J$, 
Further, we denote by~$w(J')$ the total weight of jobs in a set~$J'$ and we write~$W(t)$ for~$w(U_t)$.

%\nic{Irgendein informeller Satz dazu was der Alg 1 tut?! Eleganter?}\nic{Welche jobs sind denn noch in Schritt 8 übrig? Es gibt keine unfinished ones mehr.}
The algorithm, essentially, executes a classical weighted round robin algorithm where the rate at which the front job of a chain $c$ is executed at time $t$ is proportional to the total weight of unfinished jobs in that chain, $W_c(t)$.
Since this definition is infeasible if there are only zero weight jobs left, we process these in an arbitrary order in the end. We can do this because their completion time does not influence the objective value.

For each~$c \in \chains$, the algorithm in Line~$6$ keeps track of~$W_c(t)$, the total weight of the still uncompleted jobs in~$c$. Clearly,~$W_c(t) = W_c - \sum_{j \in c \setminus U_t} w_j$ and~$W(t) = \sum_c W_c(t)$. Thus, given access to the initial~$W_c$, the algorithm can always recompute~$W_c(t)$ and~$W(t)$.


\begin{algorithm}
\caption{Weighted Round Robin on Chains}\label{alg:chain-robin}
\begin{algorithmic}[1]
\REQUIRE Set of chains $\chains$, initial total weight $W_c$ of every chain $c \in \chains$.
\STATE $t \gets 0$
\STATE $W_c(t) \gets W_c$ for every $c \in \chains$.
\WHILE{$U_t \neq \emptyset$}
\STATE Process every job $j \in F_t$ with rate $L_j^t = \frac{W_c(t)}{\sum_c W_c(t)}$
\STATE $t \gets t + 1$
\STATE If a job $j$ in chain $c$ finished, $W_c(t) \gets W_c(t) - w_j$\label{line:chain-robin-update}
\ENDWHILE
\STATE Schedule remaining jobs in an arbitrary order.
\end{algorithmic}
\end{algorithm}

%\begin{proposition}
%	At every time $t$ and for every chain $c$, $W_c(t)$ is equal to the total weight of unfinished jobs in chain $c$, and $W(t) = \sum_c W_c(t)$.
%\end{proposition}
\begin{theorem}\label{theorem:chain-robin}
    \Cref{alg:chain-robin} is a non-clairvoyant algorithm for the problem of minimizing the total weighted completion time on a single machine with online chain precedence constraints with a competitive ratio of at most $4$, when given access to accurate weight predictions.
\end{theorem}

We prove this theorem using a \df argumentation inspired by an analysis of a similar algorithm for {\em known} precedence constraints~\cite{GargGKS19}. 
% similar to~\cite{GargGKS19}, since our algorithm and offline problem is a special case of theirs.\todo{Should we highlight what is different to~\cite{GargGKS19}? E.g., they assume knowledge of the precedence constraint graph and weights. We give a simpler proof with an improved ratio exploiting the special structure of chains....}
To this end, we fix an instance and denote the objective value of \Cref{alg:chain-robin} by~$\alg$. % and the optimal objective value by~$\opt$.
%We introduce a linear programming relaxation for an optimal solution~$\opt_\optspeed$ which runs at lower speed~$\frac{1}{\optspeed}$, for some~$\optspeed \geq 1$. 
We introduce a linear programming relaxation~\cite{GargGKS19} for our problem on a machine running at lower speed~$\frac{1}{\optspeed}$, for some~$\optspeed \geq 1$. Let~$\opt_\optspeed$ denote the value for an optimal solution for the problem with speed~$\frac{1}{\optspeed}$.
Since the completion time of every job is linear in the machine speed, it is not hard to see that~$\opt_\optspeed \leq \optspeed \cdot \opt$.
The variable~$x_{j,t}$ denotes the fractional assignment of job~$j$ at time~$t$.

\begin{alignat}{3}
    \text{min} \quad &\sum_{j,t} w_{j} \cdot t \cdot \frac{x_{j,t}}{p_j} \tag{$\text{LP}_\optspeed$}\label{lp} \\ 
    \text{s.t.}  \quad & \sum_{i,t} \frac{x_{j,t}}{p_{j}} \geq 1   &&\forall j \notag \\
    & \sum_{j} \optspeed \cdot x_{j,t} \leq 1   &&\forall t \notag \\
    & \sum_{s \leq t} \frac{x_{j,s}}{p_j} \geq \sum_{s \leq t} \frac{x_{j',s}}{p_{j'}} && \quad \forall t, \forall j,j' \text{ s.t. } j \prec j' \notag \\
    & x_{ijt} \geq 0 &&\forall j,t \notag 
\end{alignat}

The dual of~\eqref{lp} can be written as follows. %is equal to the following linear program with variables~$\dualVa_j$,~$\dualVb_{t}$ and~$\dualVc_{t,j \to j'}$.
\begin{alignat}{3}
    \text{max} \quad &\sum_{j} \dualVa_j - \sum_{t} \dualVb_{t} \tag{$\text{DLP}_\optspeed$}\label{dual} \\ 
    \text{s.t.}  \quad &\sum_{s \geq t} \left( \sum_{j': j \prec j'} \dualVc_{s,j \to j'} - \sum_{j': j' \prec j} \dualVc_{s,j' \to j} \right) \notag \\
    &\leq \optspeed \cdot \dualVb_{t} \cdot p_j - \dualVa_j + w_j \cdot t  \; \; \quad \forall j,t \label{constr:dual} \\ 
    &\dualVa_j, \dualVb_{t}, \dualVc_{t,j \to j'}  \geq 0  \quad  \qquad \qquad \forall t, \forall j,j' \text{ s.t. } j \prec j' \notag
\end{alignat}


Let~$\kappa > 1$ be a constant which we fix later. We define an assignment of the variables of~\eqref{dual}:
\begin{itemize}
  \item~$\dualSa_j = \sum_{t = 0}^{C_j} \dualSa_{j,s} = \sum_{t = 0}^{C_j} w_j = w_j C_j$ for every job~$j$,
  \item~$\dualSb_{t} = \frac{1}{\kappa} \cdot W(t)$ for every time~$t$, and
  \item for every time~$t$ and jobs~$j,j'$ s.t.~$j' \prec j$ 
  \[\dualSc_{t, j' \to j} = \begin{cases}
    0 \quad \text{if } j \notin U_t \text{ or } j' \notin U_t \\
    w(S(j)) \text{ otherwise. } %j \in U_t \text{ and } j' \in U_t
  \end{cases}\] 
\end{itemize}

We show in the following that the variables~$(\dualSa_j,\dualSb_{t},\dualSc_{t,j \to j'})$ define a feasible solution for \eqref{dual} and achieve an objective value close to $\alg$. Then weak duality implies \Cref{theorem:chain-robin}. First, consider the objective value. 

%We first show that the objective value of~\eqref{dual} for the variables~$(\dualSa_j,\dualSb_{t},\dualSc_{t,j \to j'})$ is close to~$\alg$ \nnew{and that the }

\begin{lemma}\label{lemma:chain-robin-dual-objective}
  ~$\sum_{j} \dualSa_j - \sum_{t} \dualSb_{t} = (1 - \frac{1}{\kappa}) \alg$.
\end{lemma}

\begin{proof}
By definition,~$\dualSa_j = w_j C_j$, and thus~$\sum_j \dualSa_j = \alg$. Also, since the weight~$w_j$ of a job~$j$ is contained in~$W(t)$ if~$t \leq C_j$, we conclude~$\sum_t \dualSb_{t} = \frac{1}{\kappa}\alg$.
\end{proof}

Second, we show that the duals are feasible for \eqref{dual}.

\begin{lemma}\label{lemma:chain-robin-dual-feasible}
   Assigning~$\dualVa_j = \dualSa_j$,~$\dualVb_{t} = \dualSb_{t}$ and~$\dualVc_{t,j \to j'} = \dualSc_{t,j \to j'}$ is feasible for~\eqref{dual} when~$\optspeed \geq \kappa$.
\end{lemma}

\begin{proof}
  Since our defined variables are non-negative by definition, it suffices to show that this assignment satisfies~\eqref{constr:dual}.
  Fix a job~$j$ and a time~$t \geq 0$. Let~$c$ be~$j$'s chain.
  By observing that~$\dualSa_j - t \cdot w_j \leq \sum_{s \geq t} \dualSa_{j,s}$, it suffices to verify
  \begin{equation}
    \sum_{s \geq t} \left(\dualSa_{j,s} + \sum_{j': j \prec j'} \dualSc_{s,j \to j'} - \sum_{j': j' \prec j} \dualSc_{s,j' \to j} \right) \leq \optspeed \cdot \dualSb_{t} \cdot p_j. \label{eq:dual-red1}
\end{equation}

To this end, we consider the terms of the left side for all times~$s \geq t$ separately. For any $s$ with $s > C_j$, the left side of \eqref{eq:dual-red1} is zero, because $\dualSa_{j,s} = 0$ and $j \notin U_s$. 

Otherwise, that is $s \leq C_j$,
let~$t_j^*$ be the first point in time after $t$ when~$j$ is available, and let~$s \in [0, t_j^*)$. Observe that~$j \in U_s$ and that there must be a job~$j_1 \in U_s$ with~$j_1 \prec j$ in~$c$ (as~$j$ is unavailable), and thus~$\dualSc_{s,j_1 \to j} = w(S(j))$. If there is a job~$j_2$ directly succeeding~$j$ in~$c$, i.e.~$j \prec j_2$, every job~$i_2 \in S(j_2)$ is also contained in $S(j)$, hence~$\dualSc_{s,j \to j_2} - \dualSc_{s,j_1 \to j} = - w_j$. Note that this argument crucially uses the fact that in chains the successor of $j$ is unique, so in particular all direct successors of $j$ induce disjoint sets. If no job succeeds~$j$ in~$c$,~$\sum_{j': j \prec j'} \dualSc_{s,j \to j'} = 0$. We conclude that 
  \[
    \dualSa_{j,s} + \sum_{j': j \prec j'} \dualSc_{s,j \to j'} - \sum_{j': j' \prec j} \dualSc_{s,j' \to j} \leq w_j - w_j = 0. 
  \]

Therefore, proving \eqref{eq:dual-red1} reduces to proving
\begin{equation}
    \sum_{s = t^*_j}^{C_j} \left(w_j + \sum_{j': j \prec j'} \dualSc_{s,j \to j'} - \sum_{j': j' \prec j} \dualSc_{s,j' \to j} \right) \leq \optspeed \cdot \dualSb_{t} \cdot p_j. \label{eq:dual-red2}
\end{equation}

Now, let~$s \in [t_j^*, C_j)$. There cannot be an unfinished job preceding~$j$, thus~$\sum_{j': j' \prec j} \dualSc_{s,j' \to j} = 0$. Observe that if there is a job~$j' \in U_s$ with~$j \prec j'$, the fact that~$j \in U_s$ implies $j' \in U_s$, and thus gives~$\dualSc_{s,j \to j'} = w(S(j')) = W_c(s) - w_j$. This yields
\[ 
	w_j + \sum_{j': j \prec j'} \dualSc_{s,j \to j'} - \sum_{j': j' \prec j} \dualSc_{s,j' \to j} \leq W_c(s).
\]

Thus, the left side of~\eqref{eq:dual-red2} is at most $\sum_{s = t^*_j}^{C_j} W_c(s)$.


The facts that~$W(t_1) \geq W(t_2)$ at any~$t_1 \leq t_2$ and that~$j$ is processed by~$L_{j}^{t'}$ units at any time~$t' \in [t_j^*, C_j]$ imply
\begin{equation}
    \sum_{s = t^*_j}^{C_j} \frac{W_c(s)}{W(t)} \leq \sum_{s = t^*_j}^{C_j} \frac{W_c(s)}{W(s)} = \sum_{s = t^*_j}^{C_j} L_j^s \leq p_j. \label{eq:df-rates}
\end{equation}
We emphasize that this is the first time where we use the definition of the algorithm's rates.
Rearranging this gives 
  \[
    \sum_{s = t^*_j}^{C_j} W_c(s) \leq p_j \cdot W(t) =  p_j \cdot \kappa \cdot \dualSb_t \leq \optspeed \cdot p_j \cdot \dualSb_t,
  \]
  which implies \eqref{eq:dual-red2} and thus proves the statement.
\end{proof}

\begin{proof}[Proof of \Cref{theorem:chain-robin}]
We choose~$\optspeed = \kappa = 2$. Weak duality, \Cref{lemma:chain-robin-dual-feasible} and \Cref{lemma:chain-robin-dual-objective} imply
\begin{equation*} 
    \optspeed \cdot \opt \geq \opt_\optspeed \geq \sum_{j \in J} \dualSa_j - \sum_{t} \dualSb_{t} = \left( 1 - \frac{1}{\kappa} \right) \cdot \alg.
\end{equation*}

Since~$\kappa > 1$, we conclude that~$\alg \leq 4 \cdot \opt$.
% \[
% 	\alg \leq \frac{\optspeed}{1 - \frac{1}{\kappa}} \cdot \opt = 4 \cdot \opt.
% \]
\end{proof}

%By observing that 
Observe that verifying \eqref{eq:df-rates} is the only part which depends on the definition of the algorithm. Hence,~$\kappa = 2$ and~$\optspeed = 2\rho$ in the above proof imply the following generalization.

\begin{corollary}\label{coro:rates-algo}
    If an algorithm for online chain precedence constraints satisfies at every time~$t$ and for every chain~$c$ that~$\frac{W_c(t)}{W(t)} \leq \rho \cdot L_c^t$, where~$L_c^t$ is the processing rate of~$c$ at time~$t$, it is at most~$4\rho$-competitive for minimizing the total weighted completion time.
\end{corollary}

\subsection{A learning-augmented algorithm for chains}
\label{sec:chains-error}

We extend Algorithm~\ref{alg:chain-robin} to achieve robustness and smooth error-dependency in the case of inaccurate predictions, while preserving constant consistency.
To achieve robustness, we first observe that processing $\numc$ chains in parallel with rates of~$1/\numc$ leads to a~$\numc$-robust algorithm.

\begin{proposition}\label{lemma:chain-robust}
	There is an~$\bigO(\numc)$-competitive non-clairvoyant single-machine algorithm for minimizing the total weighted completion time of jobs with online chain precedence constraints, where~$\numc$ is the number of chains.
\end{proposition}

Applying the standard time-sharing technique from \Cref{thm:alg-combination}, we can easily achieve~$\mathcal{O}(1)$-consistency and~$\mathcal{O}(\numc)$-robustness by executing the algorithm of~\Cref{lemma:chain-robust} and Algorithm~\ref{alg:chain-robin} in parallel (cf.~Algorithm~\ref{alg:chain-robin-robust}). %This idea has also been used in~\cite{PurohitSK18} and~\cite{LindermayrM22} to achieve robustness. \alex{refer to preliminaries.}

\begin{algorithm}
	\caption{Learning-augmented WRR on Chains}\label{alg:chain-robin-robust}
	\begin{algorithmic}[1]
		\STATE Execute \Cref{alg:chain-robin} with rate~$\frac{1}{2}$.
		\STATE Execute the algorithm of \Cref{lemma:chain-robust} with rate~$\frac{1}{2}$.
	\end{algorithmic}
\end{algorithm}

The remainder of the section is devoted to showing an error-dependency for Algorithm~\ref{alg:chain-robin-robust}. The main challenges are as follows: we only have access to the potentially wrong predictions~$\hW_c$ for all~$c \in \chains$ and, therefore, we execute~\Cref{alg:chain-robin} using~$\hW_c$ instead of~$W_c$. This means that~$\sum_c \hW_c$ may not be the accurate total weight of the instance and that the recomputation of~$W_c(t)$ in Line~$6$ may be inaccurate. %These two observations are the main challenges when proving an error-dependency.

Consider predictions~$\hW_c$ that are potentially erroneous.
In particular, the weight of a chain $c$ might be \emph{underpredicted},~$\hW_c < W_c$, or \emph{overpredicted},~$\hW_c > W_c$. In the following, we define an error measure which quantifies the quality of weight predictions based on these error types.
% and show a modification of \Cref{alg:chain-robin} to address challenges with erroneous predictions. But first we give some more intuition.

If we execute any algorithm with erroneous weight predictions, two problematic situations can occur. 
First, we know from the lower bound example for pure online algorithms that algorithms with access to weight predictions must to some degree prioritize chains with high predicted weights. Otherwise, they would not achieve an improved ratio on such instances even for correct predictions. This also means that overpredicted chains delay the execution of other chains. An error measure should take such delays into account.
Intuitively, we measure this quantity by defining a subinstance~$\chains_o$ that captures the total excessive predicted weight of each chain with an additional (imaginary) job. This additional job gets a processing requirement equal to the processing time of the corresponding chain because an algorithm can only detect that a chain is overpredicted once the chain is completed. Thus, overpredictions have an impact on the execution during the complete processing of the chain. The first term in our error measure is the optimal solution~$\opt(\chains_o)$ for instance~$\chains_o$.

Second, an underpredicted chain consumes at some point all its predicted weight but is still unfinished. 
For the suffixes of chains after the predicted weight is finished, we do not have any more information than a pure online algorithm. 
Thus, we cannot hope to be better than~$\numc$-competitive for those suffixes.
We will quantify the cost due to these suffixes by~$\numc \cdot \opt(\chains_u)$ for a subinstances~$\chains_u$ defined by those suffixes, normalized by the processing time necessary to arrive at the respective suffix.

In the appendix, we give a formal definition of this error and prove the following theorem. The term $\numc \cdot \opt(\chains_u)/\opt$ is cased by a subinstance for which the predictions do not give us any information and, therefore, do not help us against the lower bound of $\numc$. This is similar to the error dependency proposed in~\cite{BamasMS20} for online set cover.


\begin{restatable}{theorem}{ThmStaticWeightsError}
	\label{thm:ThmStaticWeightsError}
	For minimizing the total weighted completion time of %online 
	jobs with online chain precedence constraints on a single machine, 
	\Cref{alg:chain-robin-robust} with predicted chain weights has a competitive ratio of at most
	\[
		\mathcal{O}(1) \cdot \min\left\{ 1 + \frac{\opt(\chains_o) + \numc \cdot \opt(\chains_u)}{\opt}, \numc \right\}.
	\] 
\end{restatable}
	
\subsection{Adaptive weight predictions for out-forests}
\label{sec:weight-out-trees}

We adjust~\Cref{alg:chain-robin} to out-trees and adaptive weight predictions by processing front jobs $j \in F_t$ with rate $L_j^t = \hW_{S(v)}(t)/(\sum_{v \in F_t} \hW_{S(v)}(t))$ at any point in time $t$.\jens{Hab das hier stark gekürzt und einiges in den Appendix geschoben. Wahrscheinlich immernoch zu lang.}
With~\Cref{obs:lb-trees-static} we already observed that static weight predictions are not sufficient to obtain a constant competitive algorithm for out-trees. The intuitive reason for this is that we, in contrast to chains, cannot simply recompute~$\hW_{S(v)}(t)$ whenever a new front job~$v$ appears. For chains, we were able to do so in Line~$6$ of the algorithm. If we have access to adaptive predictions however, we do not need to recompute~$\hW_{S(v)}(t)$ as we simply receive a new prediction. 
In terms of error dependency, we can use a simpler error than in~\Cref{sec:chains-error} as the measure can now depend on~$\hW_{S(v)}(t)$ for each point in time~$t$ and not just~$t = 0$. %To 
We show the following theorem in the appendix.
Similar to the proof for chains, we exploit that the sets $S(v)$ and $S(u)$ for two front jobs $v$ and $u$ are disjoint for out-forests.

\begin{theorem}
	For minimizing the total weighted completion time on a single machine with online out-tree precedence constraint and adaptive weight predictions, there is a~$\mathcal{O}(\min\left\{\eta, \omega(G) \right\})$-competitive algorithm, where
	\[
	\eta = \max_{t, v \in F_t} \frac{\hW_{S(v)}(t)}{W_{S(v)}(t)} \cdot \max_{t, v \in F_t} \frac{W_{S(v)}(t)}{\hW_{S(v)}(t)}.
	\]
\end{theorem}

For correct predictions, the algorithm is again $4$-competitive.\jens{Add sentence on algorithm dependence}


\section{Weight order predictions}
\label{sec:weight-order}
We consider static and adaptive weight order predictions. Since we have a strong lower bound for in-trees, even for the more powerful adaptive weight predictions (cf.~\Cref{lb:in-trees}), we only consider online chains and out-tree precedence constraints. For out-trees, we only consider adaptive predictions as we have a lower bound for static predictions (cf.~\Cref{obs:lb-trees-static}). We first present our results for chains and afterwards show how to apply them to out-trees.


Previously we assumed access to predictions~$\hat{W}_{c_i}$ on the total weight of all chains~$c_i \in \chains$ and introduced an~$\mathcal{O}(1)$-competitive algorithm for online chain precedence constraints.
Now, we consider the weaker weight order predictions. In the chain topology, these allow us to sort the chains~$c_i$ by non-decreasing total weight, without having access to the actual values. 
To be more precise, we assume access to a predicted order~$\hpreceq_0$ of an order~$\preceq_0$ over the chains such that~$c_i \preceq_0 c_j$ implies~$W_{c_i} \ge W_{c_j}$; recall that~$W_{c_i}$ is the total weight of a chain~$c_i$.
The orders~$\preceq_0$ resp.~$\hpreceq_0$ are \emph{static} in the sense that they do not change while we process jobs.
We use~$\preceq_t$ to indicate an (adaptive) prediction on the \emph{adaptive} order~$\preceq_t$ of chains by the remaining (not yet processed) total weight at time $t$. %, i.e.~$c_i \preceq_t c_j$ implies~$W_{c_i}(t) \ge W_{c_j}$.

Since predicted orders can be inaccurate, we introduce an error measure for order predictions.
A natural function on orders is the \emph{largest inversion}, i.e., the maximum distance between the position of a chain in an order prediction~$\hpreceq_t$ and the true order~$\preceq_t$. 
However, if all chains have almost the same weight, just perturbed by some small constant, this function indicates a large error for the reverse order, although it will arguably perform nearly as good as the true order.
To mitigate this overestimation, we first introduce $\epsilon$-approximate inversions. Formally, for every precision constant $\epsilon > 0$, we define
\[
    \largestinv(\epsilon) = \max_{t, c \in \chains(t)} \left| \left\{ c' \in \chains(t) \bigg| \frac{W_c(t)}{1 + \epsilon} \geq W_{c'}(t) \land c' \hpreceq_t c \right\} \right|.
\]
Note that~$\largestinv(\epsilon) \geq 1$ for every $\epsilon > 0$, because~$\hpreceq_t$ is reflexive.
We define the \emph{$\epsilon$-approximate largest inversion} error as
\[
    \max\{1 + \epsilon, \largestinv(\epsilon)\}.
\]
We will prove performance guarantees depending on this error which hold for any~$\epsilon > 0$.
Therefore, we intuitively get a pareto frontier between the precision $(1+\epsilon)$ and $\largestinv(\epsilon)$, the largest distance of inversions which are worse than the precision.
A configurable error measure with such properties has been successfully applied to learning-augmented algorithms in other areas~\cite{AzarPT22,Bernardini22universal}.

\subsection{Adaptive weight order}
We %start by giving 
introduce Algorithm~\ref{alg:weight-order}, which exploits access to the more powerful adaptive order~$\hpreceq_t$.  
In a sense, the idea of the algorithm is to emulate Algorithm~\ref{alg:chain-robin} for weight predictions. %Since that uses access to 
Instead of having access to the chain weights %in order 
to compute the rates for processing the different chains, Algorithm~\ref{alg:weight-order} uses~$\hpreceq_t$ to approximate the rates.
Recall that~$H_k$ denotes the~$k$th harmonic number.

\begin{algorithm}
	\caption{Adaptive weight order algorithm}\label{alg:weight-order}
	\begin{algorithmic}
		\REQUIRE Time~$t$, alive chains~$\chains(t)$, adaptive order~$\hpreceq_t$
		\STATE For every~$c \in \chains(t)$, let~$i_c$ be the position of~$c$ in~$\hpreceq_t$.
		\STATE Process every chain~$c \in \chains(t)$ with rate~$(H_{\abs{\chains(t)}} \cdot i_c)^{-1}$.
	\end{algorithmic}
\end{algorithm}

\begin{theorem}
	For any $\epsilon > 0$, \Cref{alg:weight-order} has a competitive ratio of at most~$4 H_\numc \cdot \max\{1 + \epsilon, \largestinv(\epsilon)\}$ for minimizing the total weighted completion time on a single machine with online chain precedence constraints, where~$\numc$ is the number of initial 
	chains. 
\end{theorem}

\begin{proof}
	We first observe that the rates of the algorithm are feasible, because~$\sum_{c \in C(t)} \frac{1}{H_{\abs{\chains(t)}} \cdot i_c} = \frac{H_{\abs{\chains(t)}}}{H_{\abs{\chains(t)}}} = 1$. 

	Fix a time~$t$ and an $\epsilon > 0$. For a chain~$c \in \chains(t)$, let~$W_c(t)$ be the true remaining weight of~$c$ in the algorithms schedule at time~$t$, and~$W(t)$ the total unfinished weight at time~$t$. 
	Assume that~$c_1 \hpreceq_t \ldots \hpreceq_t c_{\abs{\chains(t)}}$, and fix a chain~$c_i \in \chains(t)$.
	The algorithm processes~$c_i$ at time~$t$ with rate 
	\[ 
		L_{c_i}^t = \frac{1}{H_{\abs{\chains(t)}} \cdot i} \geq \frac{1}{H_{\numc} \cdot i}.
	\] 
	Note that showing~$\frac{W_{c_i}(t)}{W(t)} \le H_\numc \cdot \max\{1 + \epsilon, \largestinv(\epsilon)\} \cdot L^t_{c_i}$ implies the theorem via~\Cref{coro:rates-algo}.
	Assume otherwise, i.e.,~$\frac{W_{c_i}(t)}{W(t)} > \frac{1}{i} \cdot \max\{1 + \epsilon, \largestinv(\epsilon)\}$. 
    Since all chains are disjoint, 
    \begin{align*}     
        1 &\ge \sum_{k \in [i]} \frac{W_{c_k}(t)}{W(t)} \\
        &\ge \sum_{\substack{k \in [i-1]\\ W_{c_k}(t) > \frac{W_{c_i}(t)}{1+\epsilon} }} \frac{W_{c_k}(t)}{W(t)} + \sum_{\substack{k \in [i]\\ W_{c_k}(t) \leq \frac{W_{c_i}(t)}{1+\epsilon}}} \frac{W_{c_k}(t)}{W(t)}.
    \end{align*}
    Consider the second sum. First, observe that this sum has at most~$\largestinv(\epsilon)$ many terms, including the one for $c_i$, and that each such term is at most $\frac{W_{c_i}(t)}{W(t)}$.
    Then, observe that every term in the first sum is at least~$\frac{W_{c_i}(t)}{(1+\epsilon)W(t)}$.
    Thus, we can further lower bound the sum of the two sums by 
    \begin{align*}     
        &\frac{1}{1 + \epsilon}\sum_{\substack{k \in [i-1]\\ W_{c_k}(t) > \frac{W_{c_i}(t)}{1+\epsilon} }} \frac{W_{c_i}(t)}{W(t)} + \frac{1}{\largestinv(\epsilon)}\sum_{\substack{k \in [i]\\ W_{c_k}(t) \leq \frac{W_{c_i}(t)}{1+\epsilon}}} \frac{W_{c_i}(t)}{W(t)} \\
        &\geq\frac{1}{\max\{1 + \epsilon, \largestinv(\epsilon)\}} \sum_{k \in [i]} \frac{W_{c_i}(t)}{W(t)} > \sum_{k=1}^i \frac{1}{i} = 1,
    \end{align*}
	a contradiction.
    \alex{TODO make this proof look nice. Maybe define sets for sums}
\end{proof}

Using this theorem, we conclude the following corollary.

\begin{corollary}
Given access to the order of the job's weights, there exists a non-clairvoyant weight-oblivious algorithm for the problem of minimizing the total weighted completion time of~$n$ jobs on a single machine with a competitive ratio of at most~$\bigO(\log n)$.
\end{corollary}

Similar to~\Cref{sec:weight-out-trees} for weight predictions, our algorithmic result for chains and adaptive weight order predictions can be adapted to online out-tree precedence constraints.
In the appendix, we show the following theorem.

\begin{theorem}
	For any $\epsilon > 0$, there is an algorithm with a competitive ratio of at most~$4 H_{\omega(G)} \cdot \max\{1 + \epsilon, \largestinv(\epsilon)\}$ for minimizing the total weighted completion time on a single machine with online out-tree precedence constraints, where~$\omega(G)$ is the number of leaves in the tree.\todo{Proof in the appendix}
\end{theorem}

\subsection{Static weight order} If we only have access to~$\hpreceq_0$, a natural approach would be to compute the initial rates as used in Algorithm~\ref{alg:weight-order} and just not update them. However, we show in the appendix, that  this algorithm is at least~$\Omega(\numc \cdot H_\numc)$-competitive.

\begin{restatable}{lemma}{LBStaticWO}
	\label{lem:LemLBStaticWO}
	The variant of Algorithm~\ref{alg:weight-order} that computes the rates using~$\hpreceq_0$ instead of~$\hpreceq_t$ is at least~$\Omega(\numc \cdot H_{\numc})$-competitive, even if~$\hpreceq_0$ equals $\preceq_0$.
\end{restatable}



However, the lower bound instance of the lemma requires~$\numc$ to be \enquote{small} compared to the number of jobs, in case of unit jobs, or to~$P := \sum_j p_j$, otherwise.
We exploit this to prove the following theorem in the appendix.

\begin{restatable}{theorem}{ThmStaticOrder}
		For any $\epsilon > 0$, Algorithm~\ref{alg:weight-order} has a competitive ratio of at most~$\mathcal{O}(H_\numc^2 \sqrt{P} \cdot \max\{1 + \epsilon, \largestinv(\epsilon)\})$ when computing rates with~$\hpreceq_0$ instead of~$\hpreceq_t$ at any time $t$.
		For unit jobs, it is~$\mathcal{O}(H_\numc^2 \sqrt{n} \cdot \max\{1 + \epsilon, \largestinv(\epsilon)\})$-competitive.
\end{restatable}

\section{Average predictions}

Average preds also here: \cite{BoyarFL22} \nic{todo? eher in intro?}

\begin{lemma}
    Any algorithm which has access to the average weight of jobs on each root-leave path is at least $\Omega(k)$-competitive if the degree of the non-complete leave tree is bounded by $k$.
    \end{lemma}
    \begin{proof}
    We construct a leave tree based on the idea of Lemma~\ref{l:lb:chains}. Construct an instance composed of $k-1$ chains of jobs with weight $2$. Insert an additional chain with $n-k-2$ nodes, all nodes but the second having weight $0$. The second node has weight $n-k-1$. Connect the last nodes of each chain with a root having weight zero. 
    
    For an algorithm, all paths look identical as the average weight it always $1$. Therefore, an adversary can ensure that the algorithm processes the long path last, giving an objective value of $(k+1)(n-k-1)$.
    
    An optimal solution finds the heavy weight job initially, giving an objective value of $2(n-k-1)$. This yields a competitive ratio of $\Omega(k)$.
    \end{proof}
    
    \begin{lemma}
    Any algorithm which has access to the average weight of jobs on each root-leave path is at least $\Omega(k)$-competitive if the degree of the non-complete root tree is bounded by $k$.
    \end{lemma}
    \begin{proof}
    Create a chain with $\sqrt{n}/k + 1 + (n-\sqrt{n}-1)$ nodes. The first $\sqrt{n}/k$ nodes have weight one, and all get $k-1$ children with weight one. The $\sqrt{n}/k + 1$th node on the chain gets weight $n-\sqrt{n}$. The remaining $(n-\sqrt{n}-1)$ nodes on the chain all get weight zero.
    
    For an algorithm, all paths look identical as the average weight it always $1$. Therefore, an adversary can ensure that the algorithm processes all jobs possible before scheduling the heavy job. This yields a value of 
    \begin{align*}
    \sum_{i=1}^{\frac{\sqrt{n}}{k}+2+\frac{\sqrt{n}}{k}k} i + (\frac{\sqrt{n}}{k}+2+\frac{\sqrt{n}}{k}k + 1)(n-\sqrt{n}).
    \end{align*}
    
    An optimal solution would first process the path to the heavy job, then the remaining ones of weight $1$ in arbitrary order, and then the ones with weight zero, yielding a value of 
    \begin{align*}
    \sum_{i=1}^{\frac{\sqrt{n}}{k}} i + (\frac{\sqrt{n}}{k} + 1)(n-\sqrt{n}) + \sum_{i=\frac{\sqrt{n}}{k}+2}^{\frac{\sqrt{n}}{k}+2+\frac{\sqrt{n}}{k}k} i.
    \end{align*}
    
    As only the factor in front of $(n-\sqrt{n})$ differ significantly, we get a ratio of $\Omega(k)$.
    \end{proof}


	\begin{lemma}\label{l:lb:chains}
    Any algorithm which has only access to the average weight of jobs on a chain is at least $\Omega(\sqrt{n})$-competitive.
    \end{lemma}
    
    \begin{proof}
    Consider an instance composed of $\sqrt{n} \in \mathbb{N}$ chains of unit jobs, where the first two jobs of the first chain have weights 1 resp. $n - \sqrt{n}$, followed by $n - \sqrt{n} - 1$ zero weight jobs. The other $\sqrt{n}-1$ chains are single jobs with weight $1$. For an algorithm, all chains look identical since the first jobs have weight $1$ and the average of every chain is equal to $1$. Therefore, an adversary can ensure that the algorithm processes the first chain last, giving an objective value of $\sum^{\sqrt{n}}_{i=1} i + (\sqrt{n}+1)(n - \sqrt{n}) = \Omega(n\sqrt{n})$, while a solution which schedules the heavy weight job initially achieves an objective value of at most $1 + 2(n - \sqrt{n}) + \sum^{\sqrt{n} - 1}_{i=1} (3 + i) = \bigO(n)$.
    \end{proof}  	



\bibliography{../literature}
\bibliographystyle{icml2022}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% APPENDIX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\appendix
\onecolumn

\section{Input Predictions}\label{app:input}

Let~$\hchains$ denote the set of predicted chains. We assume that~$\abs{\hchains} = \abs{\chains}$, since the number of chains is known at the beginning of the algorithm.\alex{We can get rid of this} We assume in this section that the instance is composed of unit-sized jobs\ola{we should elaborate why we assume this}, and that predicted and actual chains have the same identities. That means, there exists exactly one predicted chains~$c_i \in \hchains$ for an actual chain~$\hc_i \in \chains$, which an algorithm can match to each other.

This notion requires for every actual job a predicted counterpart, and vice versa. 
Therefore, we define augmentations of~$\chains$ and~$\hchains$ as follows. Let $\chains'$ be composed of all jobs of~$\chains$, and additionally, for every paired chains~$c_i \in \chains$ and~$\hc_i \in \hchains$:
\begin{itemize}
	\item~if~$\abs{\hc_i} > \abs{c_i}$, we add~$\abs{\hc_i} - \abs{c_i}$ jobs~$J_u$ with weight~$0$ to the end of~$c_i$ in~$\chains'$. Note that~$\opt(\chains) = \opt(\chains')$.
	\item~if~$\abs{c_i} > \abs{\hc_i}$, we add~$\abs{c_i} - \abs{\hc_i}$ jobs~$J_a$ with predicted weight~$0$ to the end of~$\hc_i$ in~$\hchains'$. 
\end{itemize}
Note that this way, $\opt(\hchains) = \opt(\hchains')$.

%\begin{itemize}
%	\item~$\chains'$ is composed of all jobs of~$\chains$, and additionally, for every paired chains~$c_i \in \chains$ and~$\hc_i \in \hchains$, if~$\abs{\hc_i} > \abs{c_i}$, we add~$\abs{\hc_i} - \abs{c_i}$ jobs~$J_u$ with weight~$0$ to the end of~$c_i$ in~$\chains'$. Note that~$\opt(\chains) = \opt(\chains')$.
%	\item~$\hchains'$ is composed of all jobs of~$\hchains$, and additionally, for every paired chains~$\hc_i \in \hchains$ and~$c_i \in \chains$, if~$\abs{c_i} > \abs{\hc_i}$, we add~$\abs{c_i} - \abs{\hc_i}$ jobs~$J_a$ with predicted weight~$0$ to the end of~$\hc_i$ in~$\hchains'$. Note that~$\opt(\hchains) = \opt(\hchains')$.
%\end{itemize}

We can now assume for the sake of its analysis that both~$\chains'$ and~$\hchains'$ share the same set of jobs~$J'$. Let~$n' = \abs{J'}$.
We define~$\opt(\{w'_j\}_{j})$ as the objective of an optimal solution for~$J'$ where a job~$j$ has weight~$w'_j$. 
We further define~$\opt(\{w'_j\}_{j}, \{w_j\}_{j})$ as
\[ 
	\max\left\{\sum_{j \in J'} w'_j C^*_j \mid \{C^*_j\}_j \text{ optimal schedule for } \{w_j\}_{j} \right\}.
\]

Given two fixed augmented instances~$\chains'$ and~$\hchains'$, we define the input prediction error~$\Lambda = \Gamma_u + \Gamma_a$:
\begin{itemize}
	\item A job~$j \in J'$ has \emph{unexpected actual} weight if~$w_j > \hw_j$. The prediction error due to all unexpected weights can be expressed as~$\Gamma_u = \opt(\{\max\{\hw_j, w_j\} - w_j \}_{j}, \{w_j\}_{j})$
	\item A job~$j \in J'$ has \emph{absent predicted} weight if~$\hw_j > w_j$. The prediction error due to all absent weights can be expressed as~$\Gamma_a = \opt(\{\max\{w_j, \hw_j\} - \hw_j\}_{j}, \{\hw_j\}_{j})$.
\end{itemize}



\thmInputPredErrorDep*

\begin{proof}
    We analyze the following algorithm:
    \begin{enumerate}[1)]
        \item Efficiently compute an optimal solution based on $\hchains$~\cite{Sidney75}.
        \item Follow the computed solution. The following situations might occur:
        \begin{enumerate}[a)]
            \item A chain finishes earlier than expected. In this case, discard the remaining predicted jobs of this chain in the precomputed schedule. 
            \item A chain continues although there are no more jobs in this chain in the algorithms schedule. In this case, schedule the remaining jobs in a fixed order at the end of the precomputed schedule. 
        \end{enumerate}
    \end{enumerate}
    Let $\alg$ denote the objective value of this algorithm. We first observe that $\alg \leq \opt(\{w_j\}_{j}, \{\hw_j\}_{j})$. To see this, recall that the algorithm first follows an optimal schedule for jobs $J' \setminus J_u$ and then schedules all unexpected jobs $J_u$ at the end due to case b). 
    Since jobs $J_u$ have predicted weight $0$ in $\hchains'$ we can assume that an optimal solution for $\hchains'$ first schedules jobs $J' \setminus J_u$ as our algorithm with the same objective value and makespan as our algorithm, and then schedules jobs $J_u$ in any order. Since $\opt(\{w_j\}_{j}, \{\hw_j\}_{j})$ is an upper bound on the actual objective for any such order, the inequality follows.
    It further holds
    \begin{align*}
    \opt(\{w_j\}_{j}, \{\hw_j\}_{j}) 
    &\leq \opt(\{\max\{w_j, \hw_j\}\}_{j}, \{\hw_j\}_{j}) \\
    &= \opt(\{\hw_j\}_{j}) + \opt(\{\max\{w_j, \hw_j\} - \hw_j\}_{j}, \{\hw_j\}_{j}) \\
    &\leq \opt(\{\hw_j\}_{j}, \{w_j\}_{j}) + \opt(\{\max\{w_j, \hw_j\} - \hw_j\}_{j}, \{\hw_j\}_{j})  \\
    &\leq \opt(\{\max\{\hw_j, w_j\}\}_{j}, \{w_j\}_{j}) + \opt(\{\max\{w_j, \hw_j\} - \hw_j\}_{j}, \{\hw_j\}_{j})  \\
    &\leq \opt(\{w_j\}_{j}) + \opt(\{\max\{\hw_j, w_j\} - w_j \}_{j}, \{w_j\}_{j}) + \opt(\{\max\{w_j, \hw_j\} - \hw_j\}_{j}, \{\hw_j\}_{j}). \\
    &= \opt(\{w_j\}_{j}) + \Lambda
    \end{align*}
    We finally observe that $\opt(\{w_j\}_{j}) =  \opt(\chains)$, because jobs $J_a$ do not influence the objective value of an optimal solution.
    \alex{Todo n robustness}
\end{proof}

\inputTighterThanL*

\begin{proof}
    \begin{align*}
        \Lambda &= \opt(\{\max\{\hw_j, w_j\} - w_j \}_{j})
        +  \opt(\{\max\{w_j, \hw_j\} - \hw_j\}_{j}, \{\hw_j\}_{j})  \\
        &\leq n' \sum_{j \in J'} (\max\{\hw_j, w_j\} - w_j) 
        + n' \sum_{j \in J'} ( \max\{w_j, \hw_j\} - \hw_j ) \\
        &= n' \sum_{j \in J'} \abs{w_j - \hw_j}
    \end{align*}
\end{proof}


\section{Weight value predictions}

\subsection{Lower bounds}

We consider a slightly stronger static prediction variant for out-trees that decomposes the weight prediction on the root into weight predictions for each root-leaf path. More precisely, consider the root $r$ and the set $D$ of direct successors of $r$. For each $s \in D$, we have access to a set of weight value predictions, one for each path from $s$ to some leaf. Each such weight value prediction predicts the total weight on the corresponding path. In other words, we have a weight prediction for each root-leaf path and, for each such prediction, know which direct successor of the root the corresponding path uses. If we were not able to map the root-leaf path predictions to the direct successors of $r$, then the lower bound of~\Cref{obs:lb-trees-static} would translate. 
Note that for in-trees, this variant is equivalent to the originally introduced weight prediction model and, thus,~\Cref{lb:in-trees} translates.

\begin{lemma}
	\label{lb:out-trees}
	Any algorithm which has only access to the total weight of jobs on each root-leaf path of an out-tree is at least~$\Omega(n^\frac{1}{4})$-competitive. 
\end{lemma}

\begin{proof}
	We consider an instance of~$m + 1$ subtrees with roots that are connected to the main root that has weight~$0$. 
	The first subtree starts with a chain of length~$\ell$, where the last node has~$k$ children with weight~$1$. The~$m$ remaining subtrees also start with a chain of length~$\ell$, but the last node has weight~$1$ and~$k$ children of weight zero. All other jobs have weight~$0$.
	One solution is to first schedule all~$k$ valuable jobs of the first subtree, followed by the chains of the other subtrees in any sequential order, achieving a total weighted completion time of 
	\[	
	\bigO(\ell \cdot k + k^2 + (l+k) m + m^2 \cdot \ell) \geq \opt. 
	\]
	Since all subtrees look identical to an algorithm and have the same set of root-leaf predictions per subtree, we can assume that an algorithm finishes the~$k$ valuable jobs in the first subtree last (among all jobs with weight one), implying a total weighted completion time of 
	\[
	\alg = \Omega(m^2 \cdot \ell + (m \ell + \ell) k + k^2).	
	\]
	Using~$\ell = k = \Theta(\sqrt{n})$ and~$m = \Theta(n^\frac{1}{4})$ gives that~$\alg = \Omega(n \cdot n^\frac{1}{4})$, while~$\opt = \bigO(n)$, which asserts the statement. Note that this construction does not consider all~$n$ jobs. But this is no problem, as adding them to the main root as single zero weight children neither influences an optimal solution nor helps any algorithm.
\end{proof}

\subsection{A learning-augmented algorithm for chains}

We give a formal proof of the following theorem.

\ThmStaticWeightsError*

In order to give the proof, we first formally define the \emph{predicted instance} (including $\chains_o$ and $\chains_u$).

\begin{definition}[predicted instances]
	The \emph{predicted instance}~$\hchains$, the \emph{underpredicted subinstance}~$\chains_u$ and the \emph{overpredicted subinstance}~$\chains_o$ are constructed by considering
	for every~$c = [j_1,\ldots,j_\ell] \in \chains$ the following cases:
	\begin{enumerate}[(i)]
		\item If~$\hW_c = W_c$, then the chain~$\hc = c$ with job weights~$\hw_{j} = w_j$ for all~$j \in c$ is added to~$\hchains$.
		\item If~$\hW_c < W_c$, then the chain~$\hc = [j_1,\ldots,j_k]$, where~$k$ is the smallest index s.t.~$\hW_c \leq \sum_{i=1}^{k} w_i$, with weights~$\hw_{j_i} = w_{j_i}$ for all~$1 \leq i \leq k - 1$ and~$\hw_{j_k} = \hW_c - \sum_{i=1}^{k-1} w_i$ is added to~$\hchains$. Additionally, a chain~$c_u = [\bot, j_{k+1}, \ldots, j_\ell]$ with weights~$\hw_{j_i} = w_{j_i}$ for all~$k+1 \leq i \leq \ell$ and~$\hw_{\bot} = \sum_{i=1}^{k} w_i - \hW_c$ is added to~$\chains_u$, where the processing requirement of~$\bot$ is equal to the total processing requirement of~$\hc$.
		\item If~$\hW_c > W_c$, then chain~$\hc = [j_1,\ldots,j_\ell]$ with weights $\hw_{j_i} = w_{j_i}$ for all~$1 \leq i \leq \ell - 1$ and $\hw_{j_\ell} = \hW_c - \sum_{i=1}^{\ell-1} w_i$ is added to~$\hchains$. Additionally, a chain~$c_o = [\top]$ is added to~$\chains_o$, where the weight of $\top$ is equal to~$\hW_c - \sum_{i=1}^{\ell} w_i$ and its processing requirement is equal to the total processing requirement of~$\hc$.
	\end{enumerate}
	
	Finally,~$\chains_p$ is a copy of~$\hchains$ where for every overpredicted chain~$\hc \in \hchains$ the weight of its last job~$j$ is set to~$w_j = \hW_{\hc} - W_\hc$.
\end{definition}

Note that for every~$\hc \in \hchains$ we have~$\sum_{j \in \hc} \hw_j = \hW_c$, i.e., the predicted weights are correct for~$\hchains$.
In the following, we nevertheless call a chain~$\hc \in \hchains$ overpredicted resp. underpredicted if that is true for its corresponding chain in~$\chains$.
Since every job~$j$ of~$\chains_p$ is also part of~$\chains$ with the same processing requirement and a weight of at most $w_j$, we conclude: % the following bound.

The following lemma in combination with~\Cref{lemma:chain-robust} imply~\Cref{thm:ThmStaticWeightsError}.

\begin{proposition}
	$\opt(\chains_p) \leq \opt(\chains)$.
\end{proposition}


\begin{lemma}
	\Cref{alg:chain-robin-robust} with predicted chain weights achieves an objective value of at most 
	\[
	\mathcal{O}(1) \cdot \opt(\chains_p) + \mathcal{O}(1) \cdot (\opt(\chains_o) + \numc \cdot \opt(\chains_u)).
	\] 
\end{lemma}

\begin{proof}
	We first argue that~$\opt(\hchains) \leq \mathcal{O}(1) \cdot \opt(\chains_p) + \mathcal{O}(1) \cdot \opt(\chains_o)$. 
	To this end, consider the instance~$\chains_p \cup \chains_o$. 
	Every correctly predicted or underpredicted chain in~$\hchains$ is contained as an identical copy in~$\chains_p$. 
	For every overpredicted chain~$\hc \in \hchains$ with weight~$\hW_\hc$ in~$\hchains$ are all jobs of~$\hc$ contained with a total weight of~$W_\hc$ in~$\chains_p$ and the remaining weight of~$\hW_\hc - W_\hc$ is contained in~$\chains_o$. 
	Additionally, it is ensured by the processing requirement of the jobs in~$\chains_o$ that their weight can only be gained when processing at least the total processing requirement of~$\hc$. 
	This implies that the time to gain weight~$\hW_\hc - W_\hc$ of every overpredicted chain~$\hc \in \hchains$ in~$\chains_p \cup \chains_o$ takes as least as long as in~$\hchains$, and thus~$\opt(\hchains) \leq \opt(\chains_p \cup \chains_o)$. 
	Finally, it is not hard to see that~$\opt(\chains_p \cup \chains_o) \le 2 \cdot \opt(\chains_p) + 2 \cdot \opt(\chains_o)$ as~$\opt(\chains_p)$ and~$\opt(\chains_o)$ can be executed in parallel by preemptively sharing the machine, yielding the claimed bound.
	
	We now show that~$\alg \le \mathcal{O}(1) \cdot (\opt(\hchains) + \numc \cdot \opt(\chains_u))$, which implies the statement. 
	First consider the execution of \Cref{alg:chain-robin}. We may assume that the algorithm processes the artificial job added to each overpredicted chain in~$\hchains$, as it only increases its objective. Further, \Cref{alg:chain-robin} stops processing an underpredicted chain~$c \in \chains$ when a total weight of~$\hW_c$ has been completed on~$c$. 
	This concludes that the total objective of \Cref{alg:chain-robin} is at most~$\mathcal{O}(1) \cdot \opt(\hchains)$, but it does not finish underpredicted chains.
	But, due to \Cref{lemma:chain-robust}, we conclude that \Cref{alg:chain-robin-robust} always processes such chains with a rate of at least~$\frac{1}{2\numc}$. By observing that the total weight of jobs not finished by \Cref{alg:chain-robin} is exactly equal to the total weight of chains in~$\chains_u$, and the fact that the jobs in a chain~$c \in \chains_u$ can only be processed after time equal to the total processing requirement of the corresponding chain in~$\hchains$, we conclude the stated bound.
\end{proof}

\subsection{Adaptive weight predictions for out-forests}

We can generalize~\Cref{alg:chain-robin} to out-trees and adaptive weight predictions. With~\Cref{obs:lb-trees-static} we already observed that static weight predictions are not sufficient to obtain a constant competitive algorithm for out-trees. The intuitive reason for this is that we, in contrast to chains, cannot simply recompute~$\hW_{S(v)}(t)$ whenever a new front job~$v$ appears. For chains, we were able to do so in Line~$6$ of the algorithm. If we have access to adaptive predictions however, we do not need to recompute~$\hW_{S(v)}(t)$ as we simply receive a new prediction. 


%Recall that~$F_t$ is the set of front jobs at point in time~$t$.
Algorithm~\ref{alg:chain-robin-out-trees} formulates the algorithm for out-forests.

\begin{algorithm}
	\caption{Weighted Round Robin on Chains}\label{alg:chain-robin-out-trees}
	\begin{algorithmic}[1]
		\REQUIRE Out-tree~$T$ and adaptive weight predictions.
		\STATE~$t \gets 0$
		\WHILE{$F_t \neq \emptyset$}
		\STATE Process every~$v \in F_t$ with rate~$L_j^t = \frac{\hW_{S(v)}(t)}{\sum_{v \in F_t} \hW_{S(v)}(t)}$
		\STATE~$t \gets t + 1$
		\ENDWHILE
	\end{algorithmic}
\end{algorithm}

The key property of out-trees that allows us to essentially reuse the analysis of~\Cref{alg:chain-robin} is that the subgraphs~$G[S(v)]$ and~$G[S(u)]$ induced by the sets~$S(v)$ and~$S(u)$ for any two front jobs~$u,v \in F_t$ with~$u \not= v$ are disjoint.
For in-trees, this property does not hold and thus the analysis does not translate.
Using this property, we show the following theorem in the appendix.

\begin{theorem}
	For minimizing the total weighted completion time of online jobs with online out-tree precedence constraints on a single machine and accurate adaptive weight predictions, Algorithm~\ref{alg:chain-robin-out-trees} is~$4$-competitive. 
\end{theorem}

We can achieve $\omega$-robustness by simply reusing the ideas of~\Cref{sec:chains-error}. 
In terms of error dependency, we can use a simpler error than in~\Cref{sec:chains-error} as the measure can now depend on~$\hW_{S(v)}(t)$ for each point in time~$t$ and not just~$t = 0$. %To that end, let~$\eta_1 = \max_{t, v \in F_t} \frac{\hW_{S(v)}(t)}{W_{S(v)}(t)}$,~$\eta_2 = \max_{t, v \in F_t} \frac{W_{S(v)}(t)}{\hW_{S(v)}(t)}$, and~$\eta = \eta_1 \cdot \eta_2$. 
We show the following theorem in the appendix by adapting the analysis of~\Cref{theorem:chain-robin}.

\begin{theorem}
	For minimizing the total weighted completion time on a single machine with online out-tree precedence constraint and adaptive weight predictions, there is a~$\mathcal{O}(\min\left\{\eta, \omega(G) \right\})$-competitive algorithm, where
	\[
	\eta = \max_{t, v \in F_t} \frac{\hW_{S(v)}(t)}{W_{S(v)}(t)} \cdot \max_{t, v \in F_t} \frac{W_{S(v)}(t)}{\hW_{S(v)}(t)}.
	\]
	\todo{TODO: Write the proof in the appendix and check if the error actually works out.}
\end{theorem}

\todo[inline]{TODO: Reference similar error from the literature.}


\section{Static Weight Order}

\LBStaticWO*

\begin{proof}
	Consider an instance with~$\numc$ chains, each with a total weight of one. Then,~$\preceq_0$ is just an arbitrary order of the chains. The algorithm starts processing the chains~$c$ with rate~$(H_\numc \cdot i_c)^{-1}$. The first~$\numc-1$ chains have their total weight of one an the very first job and afterwards only jobs of weight zero. Chain~$\numc$, the slowest chain, has its total weight on the last job. 
	We define the chains~$c$ to contain a total of~$d \cdot H_\numc \cdot i_c$ jobs with unit processing times, for some common integer~$d$. This means that the algorithm finishes all chains at the same time.
	The optimal solution value for this instance is~$\numc \cdot (\numc + 1) + \numc - 1 + d \cdot H_\numc \cdot \numc$, where~$\numc \cdot (\numc + 1)$ is the optimal sum of completion times for the first~$\numc-1$ chains, ~$d \cdot H_\numc \cdot \numc$ is the cost for processing the last chain, and~$\numc - 1$ is the cost for delaying the last chains by the~$\numc - 1$ time units needed to process the first jobs of the first~$\numc-1$ chains. The solution value of the algorithm is at least~$d \cdot H_\numc^2 \cdot \numc^2$ as this is the cost for just processing the last chain. Thus, for large~$d$, the competitive ratio tends to~$H_\numc \cdot \numc$.
\end{proof}

\ThmStaticOrder*


\begin{proof}
	For a subset of chains~$S$, let~$\opt(S)$ denote the optimal objective value for the subinstance induced by~$S$. For a single chain~$c$,~$\opt(c)$ is just the cost for processing chain~$c$ with rate~$1$ on a single machine. 
	Let~$\alg(S)$ denote the sum of weighted completion times of the jobs that belong to chains in~$S$ in the schedule computed by the algorithm.		
	
	In the first part of the proof, we assume that all chains~$c_i$ have a total processing time of at most~$\sqrt{P}$. This only decreases the objective value of~$\opt$. For~$\alg$, we will analyze the additional cost caused by longer chains afterwards.
	In a sense, we assume that~$\alg$, for each chain~$c$, has to pay all weight that appears after~$\sqrt{P}$ processing times units of the chain two times: Once artificially  after exactly~$\sqrt{P}$ time units of the chain have been processed and once at the point during the processing where the weight actually appears. This assumption clearly only increases~$\alg$.
	In the first part of the proof, we analyze only the artificial cost and ignore the actual cost. In the context of our algorithm this is equivalent to assuming the chains have total processing times of at most~$\sqrt{P}$. In the second part of the proof we will analyze the actual cost for the jobs that appear after~$\sqrt{P}$ time units in their chain.
	
	
	\paragraph{First Part}
	Assume~$c_1 \hpreceq_0 c_2 \hpreceq_0 \ldots \hpreceq_0 c_\numc$. Therefore, the algorithm processes chain~$c_i$ with rate~$(H_\numc \cdot i)^{-1}$.
	This directly implies~$\alg(c_i) = H_\numc \cdot i \cdot \opt(c_i)$ and, thus,
	$$
	\alg = \sum_{i=1}^\numc H_\numc \cdot i \cdot \opt(c_i).
	$$
	
	Let~$\chains_{k} = \{c_1,\ldots,c_{k}\}$ for every~$k \in [\numc]$. We first analyze~$\alg(\chains_{3 \cdot \largestinv(\epsilon)})$.
	For the chains in~$\chains_{3 \cdot\largestinv(\epsilon)}$, we get
	\begin{align*}
		\alg(\chains_{3\cdot\largestinv(\epsilon)}) &= \sum_{i = 1}^{3\cdot\largestinv(\epsilon)} H_\numc \cdot i \cdot \opt(c_i)\\
		&\le H_{\numc} \cdot 3 \cdot \largestinv(\epsilon) \cdot \sum_{i = 1}^{3 \cdot\largestinv(\epsilon)} \opt(c_i)\\
		&\le H_{\numc} \cdot 3 \cdot \largestinv(\epsilon) \cdot \opt,
	\end{align*}
	meaning that, for~$\chains_{3 \cdot\largestinv(\epsilon)}$, we achieve the desired competitive ratio. 
	
	Next, consider the chains in~$\chains \setminus \chains_{3 \cdot\largestinv(\epsilon)}$, i.e., the chains~$c_i$ with~$i > 3 \cdot \largestinv(\epsilon)$.
	To analyze the cost for these chains~$C_i$, we continue by lower bounding~$\opt(c_i)$.
	To that end, consider~$\opt(\chains_i)$.
	The definition of~$\largestinv(\epsilon)$ implies that there are at most~$\largestinv(\epsilon)$ chains~$c_j \in \chains_{i}$ with~$W_{c_i} \geq (1 + \epsilon) W_{c_j}$.
	For all other chains~$c_j$ in~$\chains_i$, we have~$\frac{ W_{c_i}}{(1 + \epsilon)} <  W_{c_j}$.
	Thus, there are~$i - \largestinv(\epsilon)$ chains in~$\chains_i$ with a weight of at least~$\frac{ W_{c_i}}{(1 + \epsilon)}$. Since we consider chains with~$i> 3 \cdot \largestinv(\epsilon)$, it holds~$i - \largestinv(\epsilon) \geq 1$.
	We can lower bound~$\opt(\chains_{i})$ by assuming that all such chains consist only of a single job with weight~$\frac{ W_{c_i}}{(1 + \epsilon)}$ and ignoring the up-to~$\largestinv(\epsilon)$ other chains.
	These assumptions only decrease~$\opt(\chains_{i})$. Since in this relaxation all jobs have an equal weight and length, an optimal solution for it processes the jobs in an arbitrary order, giving
	\begin{align*}  
	\opt(\chains_{i}) &\ge \sum_{j=1}^{i-\largestinv(\epsilon)} j \cdot \frac{W_{c_i}}{1+\epsilon}\\
	&= \frac{(i-\largestinv(\epsilon)+1) \cdot (i-\largestinv(\epsilon)) \cdot W_{c_i}}{2 \cdot (1+\epsilon)}\\
	&= \frac{((i+1)\cdot i + \largestinv(\epsilon)^2 + i - 2 \cdot i \cdot \largestinv(\epsilon)-\largestinv(\epsilon)) \cdot W_{c_i}}{2 \cdot (1+\epsilon)}\\
	&\ge \frac{(i+1)\cdot i  - 3\cdot i \cdot \largestinv(\epsilon)}{2\cdot(1+ \epsilon)} \cdot W_{c_i}.
	\end{align*}

	Since we still assume that each chain has a total processing time of at most~$\sqrt{P}$, we can observe~$\opt(c_i) \le \sqrt{P} \cdot W_{c_i}$. This yields:
	\begin{align*}
		&\frac{2\cdot(1+ \epsilon)}{(i+1)\cdot i  - 3\cdot i \cdot \largestinv(\epsilon)} \cdot \sqrt{P} \cdot \opt(\chains_i)  \ge \opt(c_i)\\
	\end{align*}
	We can therefore conclude
	\begin{align*}
	\alg(\chains\setminus \chains_{3\cdot\largestinv(\epsilon)}) &= \sum_{i = 3 \cdot \largestinv(\epsilon) + 1}^\numc H_\numc \cdot i \cdot \opt(c_i)\\
	&\le \sum_{i = 3 \cdot \largestinv(\epsilon) + 1}^\numc H_\numc \cdot \frac{2 \cdot (1+\epsilon)}{(i+1)-3\cdot \largestinv(\epsilon)} \cdot \sqrt{P} \cdot \opt(\chains_{i})\\
	&\le 2 \cdot (1+\epsilon) \cdot  H_\numc  \cdot \sqrt{P} \cdot \opt \sum_{i = 3 \cdot \largestinv(\epsilon) + 1}^\numc \frac{1}{(i+1)-3\cdot \largestinv(\epsilon)} \\
	&\le 2 \cdot (1+\epsilon) \cdot  H_\numc \cdot H_{\numc- 3 \largestinv(\epsilon) + 1}  \cdot \sqrt{P} \cdot \opt \\
	&\le 2 \cdot (1+\epsilon) \cdot  H_\numc^2  \cdot \sqrt{P} \cdot \opt \\
	\end{align*}
	
	We can conclude the first part of the proof by combining the bounds for~$\alg(\chains\setminus\chains_{3 \cdot \largestinv(\epsilon)})$ and~$\alg(\chains_{3 \cdot \largestinv(\epsilon)})$:
	\begin{align*}
		\alg(\chains) &= \alg(\chains\setminus\chains_{3 \cdot \largestinv(\epsilon)}) + \alg(\chains_{3 \cdot \largestinv(\epsilon)})\\
		&\le 5 \cdot H_\numc^2 \cdot \sqrt{P} \cdot \max\{1+\epsilon, \largestinv(\epsilon)\} \cdot \opt.
	\end{align*}
	
	
	
	\paragraph{Second Part} It remains to analyze the additional cost incurred by chains with a total processing time of more than~$\sqrt{P}$.
	To that end, consider the set~$J_L$ of jobs that, in any schedule, cannot be started before~$\sqrt{P}$ time units have past. For a job~$j \in J_L$, the predecessors of~$j$ in the chain of~$j$ must have a total processing time of~$\sqrt{P}$. 
	Let~$\alg(J_L)$ and~$\opt(J_L)$ denote the weighted completion times of the jobs in~$J_L$ in the optimal solution and the schedule computed by~$\alg$, respectively.
	Then,
	$$
	\frac{\alg(J_L)}{\opt(J_L)} \le \frac{\sum_{j \in J_L} P \cdot w_j}{\sum_{j \in J_L} \sqrt{P} \cdot w_j} = \sqrt{P}.
	$$
	Thus, the additional cost of the jobs in~$J_L$ asymptotically does not worsen the competitive ratio.
\end{proof}
    

\section{Weight Predictions on Parallel Machines}



\section{Time-Sharing without Monotonicity on a Single Machine}\label{app:monotonicity}

\alexinline{TODO}

I think we don't need to explicitly require the monotonicity of the algorithm: It requires an algorithm to satisfy $C'_{j} \leq C_j$ if $p'_j \leq p_j$ in the schedules of any two instances $J'$ and $J$. However, in the proof of the above theorem we only need that the objective does not decrease if between two timesteps the processing time of jobs get decreased by the other algorithm. However, I think we can assume that the algorithms work on identical copies of the instance. If a job finishes, every algorithms knows the amount it has processed that jobs. It can then tell the other algorithm, to continue working on that job until this additional processing requirement is met.

    


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{document}


% This document was modified from the file originally made available by
% Pat Langley and Andrea Danyluk for ICML-2K. This version was created
% by Iain Murray in 2018, and modified by Alexandre Bouchard in
% 2019 and 2021 and by Csaba Szepesvari, Gang Niu and Sivan Sabato in 2022. 
% Previous contributors include Dan Roy, Lise Getoor and Tobias
% Scheffer, which was slightly modified from the 2010 version by
% Thorsten Joachims & Johannes Fuernkranz, slightly modified from the
% 2009 version by Kiri Wagstaff and Sam Roweis's 2008 version, which is
% slightly modified from Prasad Tadepalli's 2007 version which is a
% lightly changed version of the previous year's version by Andrew
% Moore, which was in turn edited from those of Kristian Kersting and
% Codrina Lauth. Alex Smola contributed to the algorithmic style files.
