ifaamas [AAMAS ’24]Proc. of the 23rd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2024)May 6 – 10, 2024 Auckland, New
ZealandN. Alechina, V. Dignum, M. Dastani, J.S. Sichman (eds.) 2024 2024 1097
School of Intelligent Systems Engineering, Sun Yat-Sen University Shenzhen
China School of Intelligent Systems Engineering, Sun Yat-Sen University
Shenzhen China School of Intelligent Systems Engineering, Sun Yat-Sen
University Shenzhen China

# Simple $k$-crashing Plan with a Good Approximation Ratio

Ruixi Luo<EMAIL_ADDRESS>,  Kai Jin<EMAIL_ADDRESS>and  Zelin Ye
<EMAIL_ADDRESS>
###### Abstract.

In project management, a project is typically described as an activity-on-edge
network (AOE network), where each activity / job is represented as an edge of
some network $N$ (which is a DAG). Some jobs must be finished before others
can be started, as described by the topology structure of $N$. It is known
that job $j_{i}$ in normal speed would require $b_{i}$ days to be finished
after it is started. Given the network $N$ with the associated edge lengths
$b_{1},\ldots,b_{m}$, the duration of the project is determined, which equals
the length of the critical path (namely, the longest path) of $N$.

To speed up the project (i.e. reduce the duration), the manager can crash a
few jobs (namely, reduce the length of the corresponding edges) by investing
extra resources into that job. However, the time for completing $j_{i}$ has a
lower bound due to technological limits – it requires at least $a_{i}$ days to
be completed. Moreover, it is expensive to buy resources. Given $N$ and an
integer $k\geq 1$, the $k$-crashing problem asks the minimum amount of
resources required to speed up the project by $k$ days. We show a simple and
efficient algorithm with an approximation ratio
$\frac{1}{1}+\ldots+\frac{1}{k}$ for this problem.

We also study a related problem called $k$-LIS, in which we are given a
sequence $\omega$ of numbers and we aim to find $k$ disjoint increasing
subsequence of $\omega$ with the largest total length. We show a
$(1-\frac{1}{e})$-approximation algorithm which is simple and efficient.

###### Key words and phrases:

Project duration, Network optimization, Greedy algorithm, Maximum flow,
Critical path

##  1\. Introduction

Critical Path Method (CPM) are commonly used in network analysis and project
management. A fundamental problem in CPM is to optimize the total project cost
subject to a prescribed completion date Siemens (1971). The general setting is
that the project manager can expedite a few jobs by investing extra resources,
hence reduce the duration of the entire project and thus meet the desired
completion date. Meanwhile, the extra resources spent should be as few as
possible. A formal description of the problem is given in subsection 1.1. In
this paper, we revisit a simple incremental algorithm for solving this problem
and prove that it has an approximation ratio $\frac{1}{1}+\ldots+\frac{1}{k}$,
where $k$ denotes the amount of days the duration of the project has to be
shortened (which is easily determined by the prescribed completion date and
the original duration of the project).

The mentioned algorithm is based on greedy. It speeds up the project by only
one day at a time, and repeats it $k$ times. Each time it adopts the minimum
cost strategy to shorten the project (by one day). This does not guarantee the
minimum total cost for $k>1$ (see an example in subsection 2.3). Nevertheless,
it is a simple, efficient, and practical algorithm, which should have been
applied by several engineers. Therefore, a theoretical analysis on its
approximation performance seems to be important and may benefit relevant
researchers and engineers. Such an analysis is not easy and is absent in
literature, hence we cover it in this paper.

As a comparison, we also conduct an analysis of a similar greedy algorithm for
another fundamental problem called _$k$ -LIS problem_, in which we are given a
sequence $\omega$ and we aim to find $k$ disjoint increasing subsequence of
$\omega$ with the largest total length. The greedy algorithm for this problem
is as the following: Find the longest increasing subsequence (LIS) at one time
and remove it. Repeat it for $k$ times. However, this does not guarantee an
optimum solution as well; for example, consider
$\omega=(3,4,5,8,9,1,6,7,8,9),k=2$. Nevertheless, we prove that it is a
$(1-\frac{1}{e})$-approximation algorithm. Moreover, we show that for every
$k>1$, there are cases for which the greedy solution is only $0.75$ times the
maximum solution.

###  1.1. Description of the $k$-crashing problem

A project is considered as an activity-on-edge network (AOE network, which is
a directed acyclic graph) $N$, where each activity / job of the project is an
edge. Some jobs must be finished before others can be started, as described by
the topology structure of $N$.

It is known that job $j_{i}$ in normal speed would take $b_{i}$ days to be
finished after it is started, and hence the (normal) duration of the project
$N$, denoted by $d(N)$, is determined, which equals the length of the critical
path (namely, the longest path) of $N$.

To speed up the project, the manager can crash a few jobs (namely, reduce the
length of the corresponding edges) by investing extra resources into that job.
However, the time for completing $j_{i}$ has a lower bound due to
technological limits - it requires at least $a_{i}$ days to be completed.
Following the convention, assume that the duration of a job has a linear
relation with the extra resources put into this job; equivalently, there is a
parameter $c_{i}$ (slope), so that shortening $j_{i}$ by
$d\leavevmode\nobreak\ (0\leq d\leq b_{i}-a_{i})$ days costs $c_{i}\cdot d$
resources.

Given project $N$ and an integer $k\geq 1$, the _$k$ -crashing problem_ asks
the minimum cost to speed up the project by $k$ days.

In fact, many people also care about the case of non-linear relation,
especially the convex case where shortening an edge becomes more difficult
after a previous shortening. Delightfully, the greedy algorithm performs
equally well for this convex case. Without any change, it still finds a
solution with the approximation ratio $\frac{1}{1}+\ldots+\frac{1}{k}$. For
simplicity, we focus on the linear case throughout the paper, but our proofs
are still correct for the convex case.

###  1.2. Related work (about $k$-crashing)

The first solution to the $k$-crashing problem was given by Fulkerson
Fulkerson (1961) and by Kelley Kelley (1961) respectively in 1961. The results
in these two papers are independent, yet the approaches are essentially the
same, as pointed out in Phillips and Dessouky (1977). In both of them, the
problem is first formulated into a linear program problem, whose dual problem
is a minimum-cost flow problem, which can then be solved efficiently.

Later in 1977, Phillips and Dessouky Phillips and Dessouky (1977) reported
another clever approach (denoted by Algorithm PD). Similar as the greedy
algorithm mentioned above, Algorithm PD also consists of $k$ steps, and each
step it locates a minimal cut in a flow network derived from the original
project network. This minimal cut is then utilized to identify the jobs which
should be expedite or de-expedite in order to reduce the project reduction. It
is however not clear whether this algorithm can always find an optimal
solution. We have a tendency to believe the correctness, yet cannot find a
proof in Phillips and Dessouky (1977).

It is noteworthy to mention that Algorithm PD shares many common logics with
the greedy algorithm we considered. Both of them locates a minimal cut in some
flow network and then use it to identify the set of jobs to expedite / de-
expedite (there is no de-expedite allowed in the greedy algorithm, but there
are de-expedites in Algorithm PD) in the next round. However, the constructed
flow networks are different. The one in the greedy algorithm has only capacity
upperbounds, whereas the one in Algorithm PD has both capacity upperbounds and
lowerbounds and is thus more complex.

The greedy algorithm we considered is much simpler and easier to implement
comparing to all the approaches above.

Other approaches for the problem are proposed by Siemens Siemens (1971) and
Goyal Goyal (1996), but these are heuristic algorithms without any guarantee –
approximation ratio are not proved in these papers.

Many variants of the $k$-crashing problem have been studied in the past
decades; see Gerk and Qassim (2008), Ballesteros-Pérez et al. (2019), and the
references within.

###  1.3. Related work (about $k$-LIS)

The $k$-LIS problem is a generalization of the well-known LIS problem, most of
the study about $k$-LIS lies on revealing the connections between LIS and
Young tableau. Utilizing the Young tableau, Schensted Schensted (1961) managed
to compute the length of the longest increasing and decreasing subsequence of
$\omega$, which offers a way to solve the LIS problem. Greene Greene (1974)
extended the result of Schensted (1961) to $k$-LIS problem and calculates the
exact result (the $k$ increasing subsequences) of the $k$-LIS problem. First,
it takes the largest $k$ rows of the Young tableau of $\omega$. Then it
transform $\omega$ into a canonical form $\tilde{\omega}$. Next, it transform
$\tilde{\omega}$ back to $\omega$ while modifying the largest $k$ rows of the
Young tableau accordingly. In the end, we can get the modified $k$ rows as the
optimal result of the $k$-LIS problem. The results of Greene (1974) are
applied in some problems related to LIS; see Thomas and Yong (2011) Ferrari et
al. (2022).

Another approach to solve the $k$-LIS problem is as follows. We first
formulate the $k$-LIS problem into a minimum-cost network flow problem (which
contains $O(n^{2})$ arcs, where $n$ denotes the length of the given sequence).
Basically, if some element $u$ of $\omega$ is smaller than $v$ of $\omega$ and
$u$ is preceding $v$, we build an arc from node $u^{\prime}$ to node $v$. By
solving the flow problem, we obtain the optimum solution of the $k$-LIS
problem. However, the time complexity of this approach is much higher
comparing to the greedy algorithm.

Finding an approximation of the LIS can be solved in sublinear time
Mitzenmacher and Seddighin (2021). See more results about LIS in a monograph
Romik (2015).

##  2\. $k$-crashing problem

Project $N$.:

Assume $N=(V,E)$ is a directed acyclic graph with a single source node $s$ and
a single sink node $t$ (a source node refers to a node without incoming edge,
and a sink node refers to a node without outgoing edges). Each edge $e_{i}\in
E$ has three attributes $(a_{i},b_{i},c_{i})$, as introduced in subsection
1.1.

Critical paths & critical edges.:

A path of $N$ refers to a path of $N$ from source $s$ to sink $t$. Its length
is the total length of the edges included, and the length of edge $e_{i}$
equals $b_{i}$. The path of $N$ with the longest length is called a _critical
path_. The duration of $N$ equals the length of the critical paths. There may
be more than one critical paths. An edge that belongs to some critical paths
is called a _critical edge_.

Accelerate plan $X$.:

Denote by $E_{b\setminus a}$ the multiset of edges of $N$ that contains
$e_{i}$ with a multiplicity $b_{i}-a_{i}$. Each subset $X$ of $E_{b\setminus
a}$ (which is also a multiset) is called an _accelerate plan_ , or _plan_ for
short. The multiplicity of $e_{i}$ in $X$, denoted by
$x_{i}\leavevmode\nobreak\ (0\leq x_{i}\leq b_{i}-a_{i})$, describes how much
length $j_{i}$ is shortened; i.e., $j_{i}$ takes $b_{i}-x_{i}$ days when plan
$X$ is applied. The _cost_ of plan $X$, denoted by $\mathsf{cost}(X)$, is
$\sum_{i}c_{i}x_{i}$.

Accelerated project $N(X)$.:

Define $N(X)$ as the project that is the same as $N$, but with $b_{i}$
decreased by $x_{i}$; in other words, $N(X)$ stands for the project optimized
with plan $X$.

$k$-crashing.:

We say a plan $X$ is _$k$ -crashing_, if the duration of the project $N$ is
shortened by $k$ when we apply plan $X$.

Cut of $N$.:

Suppose that $V$ is partitioned into two subsets $S,T$ which respectively
contain $s$ and $t$. Then, the set of edges from $S$ to $T$ is referred to as
a _cut_ of $N$. Notice that we cannot reach $t$ from $s$ if any cut of $N$ is
removed.

Let $k_{max}$ be the duration of the original project $N$ minus the duration
of the accelerated project $N(E_{b\setminus a})$. Clearly, the duration of
$N(X)$ is at least the duration of $N(E_{b\setminus a})$, since $X$ is a
subset of $E_{b\setminus a}$. It follows that a $k$-crashing plan only exists
for $k\leq k_{max}$.

Throughout this section, we assume that $k\leq k_{max}$.

The greedy algorithm in the following (see Algorithm 1) finds a $k$-crashing
plan efficiently. It finds the plan incrementally – each time it reduces the
duration of the project by 1.

Algorithm 1 Greedy algorithm for finding a $k$-crashing plan.

Input: A project $N=(V,E)$.
Output: A $k$-crashing plan $G$.

$G\leftarrow\varnothing$;

for $i=1$ to $k$ do

Find the optimum $1$-crashing plan of $N(G)$, denoted by $A_{i}$;

$G\leftarrow G\cup A_{i}$; (regard as multiset union)

end for

Observe that $G$ is an $i$-crashing plan of $N$ after the $i$-th iteration
$G\leftarrow G\cup A_{i}$, as the duration of $N(G)$ is reduced by 1 at each
iteration. Therefore, $G$ is a $k$-crashing plan at the end.

If a $1$-crashing plan of $N(G)$ does not exist in the $i$-th iteration $i\leq
k$, we determine that there is no $k$-crashing plan; i.e. $k>k_{max}$.

Let $G=A_{1}\cup\ldots\cup A_{k}$ be the $k$-crashing plan found by Algorithm
1. Let $\mathsf{OPT}$ denote the optimal $k$-crashing plan. Then,

$\mathsf{cost}(G)\leq\sum_{i=1}^{k}\frac{1}{i}\mathsf{cost}(\mathsf{OPT}).$

The proof of the theorem is given in the following, which applies Lemma 2.
This applied lemma is nontrivial and is proved below.

###### Lemma

For any project $N$, its $k$-crashing plan (where $k\leq k_{max}$) costs at
least $k$ times the cost of the optimum $1$-crashing plan.

###### Proof of Theorem 2.

For convenience, let $N_{i}=N(A_{1}\cup\ldots\cup A_{i})$, for $0\leq i\leq
k$. Note that $N_{0}=N$ is the original project.

Fix $i$ in $\\{1,\ldots,k\\}$ in the following. By the algorithm, $A_{i}$ is
the optimum $1$-crashing plan of $N_{i-1}$. Using Lemma 2, we know (1) any
$(k+1-i)$-crashing plan of $N_{i-1}$ costs at least
$(k+1-i)\cdot\mathsf{cost}(A_{i})$.

Let $Y=A_{1}\cup\ldots\cup A_{i-1}$ and $X=\mathsf{OPT}\setminus Y$; hence
$X\cup Y\supseteq\mathsf{OPT}$.

Observe that $N(Y\cup X)$ saves $k$ days comparing to $N$, because $Y\cup
X\supseteq\mathsf{OPT}$ is $k$-crashing, whereas $N(Y)=N_{i-1}$ saves $i-1$
days comparing to $N$. So, $N(Y\cup X)$ saves $k-(i-1)$ days comparing to
$N(Y)$, which means (2) $X$ is a $(k-i+1)$-crashing plan of $N(Y)=N_{i-1}$.
Combining (1) and (2), $\mathsf{cost}(X)\geq(k+1-i)\mathsf{cost}(A_{i})$.

Further since $\mathsf{cost}(X)\leq\mathsf{cost}(\mathsf{OPT})$ (as
$X\subseteq\mathsf{OPT}$), we obtain a relation
$(k-i+1)\mathsf{cost}(A_{i})\leq\mathsf{cost}(\mathsf{OPT})$. Therefore,

$\mathsf{cost}(G)=\sum_{i=1}^{k}\mathsf{cost}(A_{i})\leq\sum_{i=1}^{k}\frac{1}{k-i+1}\mathsf{cost}(\mathsf{OPT}).$

∎

The _critical graph_ of network $H$, denoted by $H^{*}$, is formed by all the
critical edges of $H$; all the edges not critical are removed in $H^{*}$.

Before presenting the proof to the key lemma (Lemma 2), we shall briefly
explain how do we find the optimum $1$-crashing plan of some project $H$
(e.g., the accelerated project $N(G)$ in Algorithm 1). First, compute the
critical graph $H^{*}$ and define the capacity of $e_{i}$ in $H^{*}$ by
$c_{i}$ if $e_{i}$ in $H$ can still be shortend (i.e., its length is more than
$a_{i}$) and otherwise define the capacity of $e_{i}$ in $H^{*}$ to be
$\infty$. Then we compute the minimum $s-t$ cut of $H^{*}$ (using the max-flow
algorithm Cruz-Mejía and Letchford (2023)), and this cut gives the optimum
$1$-crashing plan of $H$.

###  2.1. proof (part I)

###### Proposition

A $k$-crashing plan $X$ of $N$ contains a cut of $N^{*}$.

###### Proof.

Because $X$ is $k$-crashing, each critical path of $N$ will be shortened in
$N(X)$ and that means it contains an edge of $X$. Further since paths of
$N^{*}$ are critical paths of $N$ (which simply follows from the definition of
$N^{*}$), each path of $N^{*}$ contains an edge in $X$.

As a consequence, after removing the edges in $X$ that belong to $N^{*}$, we
disconnect source $s$ and sink $t$ in $N^{*}$. Now, let $S$ denote the
vertices of $N^{*}$ that can still be reached from $s$ after the remove, and
let $T$ denote the remaining part. Observe that all edges from $S$ to $T$ in
$N^{*}$, which forms a cut of $N^{*}$, belong to $X$. ∎

When $X$ contains at least one cut of network $H$, let $\mathsf{mincut}(H,X)$
be the minimum cut of $H$ among all cuts of $H$ that belong to $X$.

Recall that $d(H)$ is the duration of network $H$.

In the following, suppose $X$ is a $k$-crashing plan of $N$. We introduce a
decomposition of $X$ which is crucial to our proof.

First, define

$\left\\{\begin{array}[]{ccc}N_{1}&=&N,\\\ X_{1}&=&X,\\\
C_{1}&=&\mathsf{mincut}(N_{1}^{*},X_{1}).\end{array}\right.$ (1)

Figure 1. An example of the construction of $N_{i},X_{i},C_{i}$.

(Because $X_{1}=X$ is $k$-crashing, applying Proposition 2.1, $X_{1}$ contains
at least one cut of $N^{*}_{1}$. It follows that $C_{1}$ is well-defined.)

Next, for $1<i\leq k$, define

$\left\\{\begin{array}[]{ccc}N_{i}&=&N_{i-1}^{*}(C_{i-1}),\\\
X_{i}&=&X_{i-1}\setminus C_{i-1}.\\\
C_{i}&=&\mathsf{mincut}(N^{*}_{i},X_{i}).\end{array}\right.$ (2)

See Figure 1 for an example.

###### Proposition

For $1<i\leq k$, it holds that

1\. $d(N_{i})=d(N_{i-1})-1$ (namely, $d({N_{i}})=d(N)-i+1$).

2\. $X_{i}$ contains a cut of $N^{*}_{i}$ (and thus $C_{i}$ is well-defined).

###### Proof.

1\. Because $C_{i-1}$ is a cut of $N^{*}_{i-1}$, set $C_{i-1}$ is a 1-crashing
plan of $N^{*}_{i-1}$, which means $d(N^{*}_{i-1}(C_{i-1}))\leq
d(N^{*}_{i-1})-1$.

Moreover, it cannot hold that $d(N^{*}_{i-1}(C_{i-1}))\leq d(N^{*}_{i-1})-2$.
Otherwise, cancel one edge of $C_{i-1}$ and it still holds that
$d(N^{*}_{i-1}(C_{i-1}))\leq d(N^{*}_{i-1})-1$, which means $C_{i-1}$ is at
least $1$-crashing for $N^{*}_{i-1}$, and thus contains a cut of $N^{*}_{i-1}$
(by Proposition 2.1). This contradicts the assumption that $C_{i-1}$ is the
minimum cut.

Therefore, $d(N_{i})=d(N^{*}_{i-1}(C_{i-1}))=d(N^{*}_{i-1})-1=d(N_{i-1})-1$.

2\. According to Proposition 2.1, it is sufficient to prove that $X_{i}$ is a
1-crashing plan to $N_{i}$.

Suppose to the opposite that $X_{i}$ is not 1-crashing to $N_{i}$. There
exists a path $P$ in $N^{*}_{i}$ that is disjoint with $X_{i}$. Observe that

(1) The length of $P$ in $N(X)$ is the original length of $P$ (in $N$) minus
the number of edges in $X$ that fall in $P$.

(2) The length of $P$ in $N^{*}_{i}$ is the original length of $P$ (in $N$)
minus the number of edges in $(C_{1}\cup\ldots\cup C_{i-1})$ that fall in $P$.

(3) The number of edges in $(C_{1}\cup\ldots\cup C_{i-1})$ that fall in $P$
equals the number of edges in $X$ that fall in $P$, because
$X\setminus(C_{1}\cup\ldots\cup C_{i-1})=X_{i}$ is disjoint with $P$.

Together, the length of $P$ in $N(X)$ equals the length of $P$ in $N^{*}_{i}$,
which equals $d(N^{*}_{i})=d(N_{i})=d(N)-i+1>d(N)-k$. This means $X$ is not a
$k$-crashing plan of $P$, contradicting our assumption. ∎

The following lemma easily implies Lemma 2.

###### Lemma

$\mathsf{cost}(C_{i})\leq\mathsf{cost}(C_{i+1})$ for any
$i\leavevmode\nobreak\ (1\leq i<k)$.

We show how to prove Lemma 2 in the following. The proof of Lemma 2.1 will be
shown in the next subsection.

###### Proof of Lemma 2.

Suppose $X$ is $k$-crashing to $N$.

By Lemma 2.1, we know
$\mathsf{cost}(C_{1})\leq\mathsf{cost}(C_{i})\leavevmode\nobreak\ (1\leq i\leq
k)$.

Further since $\bigcup^{k}_{i=1}C_{i}\subseteq X$,

$k\cdot\mathsf{cost}(C_{1})\leq\mathsf{cost}(\bigcup^{k}_{i=1}C_{i})\leq\mathsf{cost}(X).$

Because $C_{1}$ is the minimum cut of $N^{*}$ that is contained in $X$,
whereas $A_{1}$ is the minimum cut of $N^{*}$ among all,
$\mathsf{cost}(A_{1})\leq\mathsf{cost}(C_{1})$. To sum up, we have
$k\cdot\mathsf{cost}(A_{1})\leq\mathsf{cost}(X).$ ∎

It is noteworthy to mention that $\bigcup^{k}_{i=1}C_{i}$ is not always equal
to $X$ and $\bigcup^{k}_{i=1}C_{i}$ may not be $k$-crashing.

###  2.2. proof (part II)

Assume $i\leavevmode\nobreak\ (1\leq i<k)$ is fixed. In the following we prove
that $\mathsf{cost}(C_{i})\leq\mathsf{cost}(C_{i+1})$, as stated in Lemma 2.1.
Some additional notation shall be introduced here. See Figure 2 and Figure 3.

Assume the cut $C_{i}$ of $N^{*}_{i}$ divides the vertices of $N^{*}_{i}$ into
two parts, $U_{i},W_{i}$, where $s\in U_{i}$ and $t\in W_{i}$. The edges of
$N^{*}_{i}$ are divided into four parts: 1\. $S_{i}$ – the edges within
$U_{i}$; 2\. $T_{i}$ – the edges within $W_{i}$; 3\. $C_{i}$ – the edges from
$U_{i}$ to $W_{i}$; 4\. $RC_{i}$ – the edges from $W_{i}$ to $U_{i}$.

Figure 2. Example of the definition of $S_{i}$, $T_{i}$, $RC_{i}$ and $C_{i}$

###### Proposition

(1) $C_{i+1}\cap RC_{i}=\emptyset$ and (2) $C_{i}\subseteq N^{*}_{i+1}$.

###### Proof.

(1) Consider $N^{*}_{i}$. Any path involving $RC_{i}$ goes through $C_{i}$ at
least twice. Such paths are shorten by $C_{i}$ by at least 2, and are thus
excluded from $N_{i+1}$. However, $C_{i+1}$ are edges in $N^{*}_{i+1}$ and so
are included in $N_{i+1}$. Together, $C_{i+1}\cap RC_{i}=\emptyset$.

(2) Suppose there is an edge $e_{i}\in C_{i}$ and $e_{i}\notin N^{*}_{i+1}$.
All paths in $N^{*}_{i}$ passing $e_{i}$ will be shortened by at least 2 after
expediting $C_{i}$ to avoid becoming a critical path (which makes $e_{i}$
critical). If the shortening of $e_{i}$ is canceled, the paths can still be
shortened by 1. So $C_{i}\setminus\\{e_{i}\\}$ still contains a cut to
$N^{*}_{i}$, which violates the assumption that $C_{i}$ is the minimum cut,
contradictory. So $C_{i}\subseteq N^{*}_{i+1}$. ∎

Figure 3. Key notation used in the proof of Lemma 2.1.

Because $C_{i+1}$ is a subset of the edges of $N^{*}_{i+1}$, and the edges of
$N^{*}_{i+1}$ are also in $N^{*}_{i}$, we see $C_{i+1}\subseteq T_{i}\cup
S_{i}\cup C_{i}\cup RC_{i}$. Further since $C_{i+1}\cap RC_{i}=\emptyset$
(proposition 2.2), set $C_{i+1}$ consists of three disjoint parts:

$\left\\{\begin{split}C_{i+1}^{+}&=C_{i+1}\cap T_{i};\\\
C_{i+1}^{0}&=C_{i+1}\cap C_{i};\\\ C_{i+1}^{-}&=C_{i+1}\cap
S_{i}.\end{split}\right.$ (3)

Due to $C_{i}\subseteq N^{*}_{i+1}$ (proposition 2.2), set $C_{i}$ consists of
four disjoint parts:

$\left\\{\begin{split}C_{i}^{+}&=C_{i}\cap T_{i+1}\\\ C_{i}^{0}&=C_{i}\cap
C_{i+1}\\\ C_{i}^{-}&=C_{i}\cap S_{i+1}\\\ C_{i}^{R}&=C_{i}\cap
RC_{i+1}\end{split}\right.$ (4)

See Figure 3 for an illustration. Note that $C_{i}^{0}=C_{i+1}^{0}$.

###### Proposition

1\. $C_{i+1}^{+}\cup C_{i}^{0}\cup C_{i}^{+}$ contains a cut of $N^{*}_{i}$.

2\. $C_{i+1}^{-}\cup C_{i}^{0}\cup C_{i}^{-}$ contains a cut of $N^{*}_{i}$.

###### Proof.

To show that $C_{i+1}^{+}\cup C_{i}^{0}\cup C_{i}^{+}$ contains a cut of
$N^{*}_{i}$, it is sufficient to prove that any path $P$ in $N^{*}_{i}$ goes
through $C_{i+1}^{+}\cup C_{i}^{0}\cup C_{i}^{+}$.

Assume that $P$ is disjoint with $C_{i}^{+}\cup C_{i}^{0}$, otherwise it is
trivial. We shall prove that $P$ goes through $C_{i+1}^{+}$.

Clearly, $P$ goes through $C_{i}=C_{i}^{+}\cup C_{i}^{0}\cup C_{i}^{-}\cup
C_{i}^{R}$, a cut of $N^{*}_{i}$. Therefore, $P$ goes through $C_{i}^{-}\cup
C_{i}^{R}$. See Figure 4.

Take the last edge in $C_{i}^{-}\cup C_{i}^{R}$ that $P$ goes through; denoted
by $e_{a}$ with endpoint $a$. Denote the part of $P$ after $e_{a}$ by $P^{+}$
($P^{+}\cap C_{i}=\emptyset$).

We now claim that

(1) $P^{+}\subseteq T_{i}$.

(2) In $N^{*}_{i}$, there must be a path $P^{-}\subseteq S_{i}$ from the
source to $e_{a}$ without passing $C_{i}$.($P^{-}\cap C_{i}=\emptyset$)

(3) $a\in U_{i+1}$.

Since $P$ is disjoint with $C_{i}^{+}\cup C_{i}^{0}$ and $P^{+}$ has gone
through $C_{i}^{-}\cup C_{i}^{R}$, we obtain (1).

If (2) does not hold, then all paths in $N^{*}_{i}$ that pass through $e_{a}$
have pass through $C_{i}$ already. In this case, $C_{i}\setminus e_{a}$ also
contains a cut of $N^{*}_{i}$, which contradicts our definition of minimum cut
$C_{i}$. Thus we have (2).

By the definition (3), any edge of $C_{i}^{-}\cup C_{i}^{R}$ ends at a vertex
of $U_{i+1}$. Since $a$ is the endpoint of $e_{a}\in C_{i}^{-}\cup C_{i}^{R}$,
we have (3).

By (2), we can obtain a $P^{-}$ from $s$ to $e_{a}$. Concatenate
$P^{-},e_{a},P^{+}$, we obtain a path $P^{\prime}$ in $N^{*}_{i}$. Since
$(P^{-}\cup P^{+})\cap C_{i}=\emptyset$ and $e_{a}\in C_{i}$, $P^{\prime}$
only goes through $C_{i}^{-}\cup C_{i}^{R}$ once. So $P^{\prime}$ is only
shortened by 1 and still critical after expediting $C_{i}$. Therefore,
$P^{\prime}$ exists in $N^{*}_{i+1}$ .

According to (3), we known that $P^{+}\in P^{\prime}$ starts with $a\in
U_{i+1}$ and ends at the sink in $W_{i+1}$. Thus it must go though the cut
$C_{i+1}$.

According to (1) and definition (3), path $P^{+}$ (which is a subset of
$T_{i}$ due to (1)) can only go through $C_{i+1}^{+}\subset T_{i}$.

Since $P^{+}\subset P$, we have $P$ goes through $C_{i+1}^{+}$. So any path
$P$ in $N^{*}_{i}$ goes through $C_{i+1}^{+}\cup C_{i}^{0}\cup C_{i}^{+}$.

Therefore, $C_{i+1}^{+}\cup C_{i}^{0}\cup C_{i}^{+}$ contains a cut of
$N^{*}_{i}$.

Figure 4. Construction of $P^{\prime}$ in the proof of Proposition 2.2 part 1.

To show that $C_{i+1}^{-}\cup C_{i}^{0}\cup C_{i}^{-}$ contains a cut of
$N^{*}_{i}$, it is sufficient to prove that any path $P$ in $N^{*}_{i}$ goes
through $C_{i+1}^{-}\cup C_{i}^{0}\cup C_{i}^{-}$.

Assume that $P$ is disjoint with $C_{i}^{-}\cup C_{i}^{0}$, otherwise it is
trivial. We shall prove that $P$ goes through $C_{i+1}^{-}$.

Clearly, $P$ goes through $C_{i}=C_{i}^{+}\cup C_{i}^{0}\cup C_{i}^{-}\cup
C_{i}^{R}$, a cut of $N^{*}_{i}$. Therefore, $P$ goes through $C_{i}^{+}\cup
C_{i}^{R}$. See Figure 5.

Take the first edge in $C_{i}^{+}\cup C_{i}^{R}$ that $P$ goes through;
denoted by $e_{b}$ with start point $b$. Denote the part of $P$ before $e_{b}$
by $P^{-}$ ($P^{-}\cap C_{i}=\emptyset$).

We now claim that

(1) $P^{-}\subseteq S_{i}$.

(2) In $N^{*}_{i}$, there must be a path $P^{+}\subseteq T_{i}$ from $e_{b}$
to the sink without passing $C_{i}$.($P^{+}\cap C_{i}=\emptyset$)

(3) $b\in W_{i+1}$.

Since $P$ is disjoint with $C_{i}^{-}\cup C_{i}^{0}$ and $P^{-}$ hasn’t reach
$C_{i}^{+}\cup C_{i}^{R}$, we obtain (1).

If (2) does not hold, then all paths in $N^{*}_{i}$ that pass through $e_{b}$
will pass through $C_{i}$ anyway. In this case, $C_{i}\setminus e_{b}$ also
contains cut of $N^{*}_{i}$, which contradicts our definition of minimum cut
$C_{i}$. Thus we have (2).

By the definition (3), any edge of $C_{i}^{+}\cup C_{i}^{R}$ starts with a
vertex of $W_{i+1}$. Since $b$ is the start of $e_{b}\in C_{i}^{+}\cup
C_{i}^{R}$, we have (3).

By (2), we can obtain a $P^{+}$ from $e_{b}$ to the sink. Concatenate
$P^{-},e_{b},P^{+}$, we obtain a path $P^{\prime}$ in $N^{*}_{i}$. Since
$(P^{-}\cup P^{+})\cap C_{i}=\emptyset$ and $e_{b}\in C_{i}$, $P^{\prime}$
only goes through $C_{i}^{+}\cup C_{i}^{R}$ once. So $P^{\prime}$ is only
shortened by 1 and still critical after expediting $C_{i}$. Therefore,
$P^{\prime}$ exists in $N^{*}_{i+1}$ .

According to (3), we known that $P^{-}\in P^{\prime}$ starts from the source
and ends at $b\in W_{i+1}$. Thus it must go though the cut $C_{i+1}$.

According to (1) and definition (3), path $P^{-}$ (which is a subset of
$S_{i}$ due to (1)) can only go through $C_{i+1}^{-}\subset S_{i}$.

Since $P^{-}\subset P$, we have $P$ goes through $C_{i+1}^{-}$. So any path
$P$ in $N^{*}_{i}$ goes through $C_{i+1}^{-}\cup C_{i}^{0}\cup C_{i}^{-}$.

Therefore, $C_{i+1}^{-}\cup C_{i}^{0}\cup C_{i}^{-}$ contains a cut of
$N^{*}_{i}$.

∎

Figure 5. Construction of $P^{\prime}$ in the proof of Proposition 2.2 part 2.

We are ready to prove Lemma 2.1.

###### Proof of Lemma 2.1.

According to proposition 2.2, $C_{i+1}^{+}\cup C_{i}^{0}\cup C_{i}^{+}$ and
$C_{i}^{-}\cup C_{i}^{0}\cup C_{i+1}^{-}$ each contains a cut of $N^{*}_{i}$.
Notice that $((C_{i+1}^{+}\cup C_{i}^{0}\cup C_{i}^{+})\cup(C_{i}^{-}\cup
C_{i}^{0}\cup C_{i+1}^{-})\cup C_{i}^{R})=(C_{i}\cup C_{i+1})\subset X_{i}$,
so the mentioned two cuts are in $X_{i}$. Further since $C_{i}$ is the minimum
cut of $N^{*}_{i}$ in $X_{i}$. We obtain

$\begin{split}\mathsf{cost}(C_{i})&=\mathsf{cost}(C_{i}^{+}\cup C_{i}^{0}\cup
C_{i}^{-}\cup C_{i}^{R})\leq\mathsf{cost}(C_{i+1}^{+}\cup C_{i}^{0}\cup
C_{i}^{+})\\\ \mathsf{cost}(C_{i})&=\mathsf{cost}(C_{i}^{+}\cup C_{i}^{0}\cup
C_{i}^{-}\cup C_{i}^{R})\leq\mathsf{cost}(C_{i+1}^{-}\cup C_{i}^{0}\cup
C_{i}^{-})\end{split}$

By adding the inequalities above (and note that
$C_{i+1}^{0}=C_{i}^{0}=C_{i}\cap C_{i+1}$), we have

$\begin{split}2\mathsf{cost}(C_{i}^{+}\cup C_{i}^{0}\cup C_{i}^{-}\cup
C_{i}^{R})\\\ \leq\mathsf{cost}(C_{i+1}^{+}\cup C_{i}^{0}\cup
C_{i}^{+})+\mathsf{cost}(C_{i}^{-}\cup C_{i+1}^{0}\cup
C_{i+1}^{-})\end{split}$

Equivalently,

$\begin{array}[]{cc}&2\mathsf{cost}(C_{i}^{+}\cup C_{i}^{0}\cup
C_{i}^{-})+2\mathsf{cost}(C_{i}^{R})\\\ \leq&\mathsf{cost}(C_{i}^{-}\cup
C_{i}^{0}\cup C_{i}^{+}\cup C_{i+1}^{+}\cup C_{i+1}^{0}\cup
C_{i+1}^{-}).\end{array}$

By removing one piece of $\mathsf{cost}(C_{i}^{-}\cup C_{i}^{0}\cup
C_{i}^{+})$ from both side,

$\mathsf{cost}(C_{i})+\mathsf{cost}(C_{i}^{R})\leq\mathsf{cost}(C_{i+1}^{+}\cup
C_{i+1}^{0}\cup C_{i+1}^{-})=\mathsf{cost}(C_{i+1})$

Therefore, $\mathsf{cost}(C_{i})\leq\mathsf{cost}(C_{i+1})$. ∎

Recall the “convex case” mentioned in subsection 1.1, in which shortening an
edge becomes more and more expensive. We claim that Algorithm 1 finds a
solution with the approximation ratio $\frac{1}{1}+\ldots+\frac{1}{k}$ even
for this convex case. Essentially, the proof does not need any change. We
leave the readers to verify this by themselves. (Hint: the value of the
crashing cost is only applied in Lemma 2.1, so all the other lemmas or
propositions remain correct.)

###  2.3. Counter-example of Algorithm 1

The greedy algorithm given in Algorithm 1 does not always find an optimal
$k$-crashing plan. Here we show an example.

Figure 6. An example with 5 jobs. The parameters $a_{i},b_{i},c_{i}$ of job
$j_{i}$ are shown as a label $i:[a_{i},b_{i}](c_{i})$ in the graph. The source
$s$ equals 1, whereas the sink $t$ equals 4.

The network is as shown in Figure 6 (a), and we consider $k=2$. The critical
path of this network has length $9$. The unique critical path consists of jobs
$j_{1}$, $j_{3}$, and $j_{5}$.

The greedy algorithm expedites job $j_{3}$ for one day in the first iteration;
see Figure 6 (c). It further expedites jobs $j_{1}$ and $j_{2}$ for one day in
the second iteration; see Figure 6 (d). The total cost is $9+9+10=28$.

The optimal $k$-crashing plan is to expedite jobs $j_{1}$ and $j_{5}$, as
shown in Figure 6 (b), which costs $10+10=20$.

##  3\. The $k$-LIS problem

Recall that the $k$-LIS problem aims to find $k$ disjoint increasing
subsequences among a given sequence $(a_{1},a_{2},\ldots,a_{n})$, so that the
total length of the $k$ subsequences is maximized. The following greedy
algorithm can be used to find a solution for the problem.

Algorithm 2 Greedy algorithm for $k$-LIS problem

Input: A sequence of number $\omega$.
Output: $k$ increasing subsequences of $\omega$.

for $i=1$ to $k$ do

Find the longest increasing subsequence $A_{i}$ of $\omega$;

Output $A_{i}$ and remove $A_{i}$ from $\omega$;

end for

This algorithm does not guarantee an optimal result for $k>1$. For example,
consider $\omega=(3,4,5,8,9,1,6,7,8,9),k=2$. We have the optimal result as
$\\{(3,4,5,8,9),(1,6,7,8,9)\\}$ with the total length of $10$. Yet the greedy
algorithm finds $\\{(3,4,5,6,7,8,9),(8,9)\\}$ with a total length of $9$,
which is not optimal.

###  3.1. A lower Bound of the Greedy Algorithm

We show that Algorithm 2 is an $(1-\frac{1}{e})$-approximation algorithm in
the following. Denote by $|\alpha|$ the length of any sequence $\alpha$.
Moreover, for any set $\mathcal{S}$ of (nonoverlapping) subsequences, let
$|\mathcal{S}|$ denote the total length of subsequences in $\mathcal{S}$.

Let $L_{1},\ldots,L_{k}$ denote the nonoverlapping subsequences given by the
optimal solution of the $k$-LIS problem. Assume that
$|L_{1}|\geq\ldots|L_{k}|$ without loss of generality. Let
$A_{1},\ldots,A_{k}$ denote the nonoverlapping subsequences found by the
greedy algorithm (Algorithm 2). To be clear, $A_{i}$ refers to the subsequence
found at the $i$-th step.

For any $x$ in $\\{0,\ldots,k\\}$, define
$r_{x}(L_{i})=L_{i}\setminus\\{A_{1}\cup\ldots\cup A_{x}\\}$, which is the
remaining part of $L_{i}$ after removing those elements selected in the first
$x$ rounds of the greedy algorithm.

We start with the case $k=2$, and we first bound
$\sum_{i=1}^{k}|r_{1}(L_{i})|$.

$|r_{1}(L_{1})|+|r_{1}(L_{2})|\geq|L_{1}|+|L_{2}|-|A_{1}|$ (5)

###### Proof of (5).

Following the definition of $r_{1}(L_{1})$ and $r_{1}(L_{2})$, we have

$L_{1}\cup L_{2}\subseteq r_{1}(L_{1})\cup r_{1}(L_{2})\cup A_{1},$

and thus

$|L_{1}\cup L_{2}|\leq|r_{1}(L_{1})\cup r_{1}(L_{2})\cup A_{1}|.$

Note that the left side equals $|L_{1}|+|L_{2}|$, whereas the right side
equals $|r_{1}(L_{1})|+|r_{1}(L_{2})|+|A_{1}|$, because of the disjointness of
$L_{1},L_{2}$ and that of $r_{1}(L_{1}),r_{1}(L_{2}),A_{1}$. Therefore, we
obtain (5). ∎

Next, we point out two relations between $|A_{i}|$ and $|L_{i}|$.

$\displaystyle 2|A_{1}|$ $\displaystyle\geq$ $\displaystyle|L_{1}|+|L_{2}|$
(6) $\displaystyle 2|A_{2}|+|A_{1}|$ $\displaystyle\geq$
$\displaystyle|L_{1}|+|L_{2}|$ (7)

Summing up (6) divided by 4 with (7) divided by 2,
$|A_{1}|+|A_{2}|\geq\frac{3}{4}(|L_{1}|+|L_{2}|)$. So, Algorithm 2 is a
$\frac{3}{4}$-approximation for $k=2$.

###### Proof of (6).

$2|A_{1}|=|A_{1}|+|A_{1}|\geq|L_{1}|+|L_{2}|$. ∎

###### Proof of (7).

At the moment where the greedy algorithm is about to select $A_{2}$ (after
chosen $A_{1}$), sequence $r_{1}(L_{1})$ and $r_{1}(L_{2})$ are both available
for being selected by the greedy algorithm, hence

$|A_{2}|\geq|r_{1}(L_{1})|\text{ and }|A_{2}|\geq|r_{1}(L_{2})|.$ (8)

Summing them up, $2|A_{2}|\geq|r_{1}(L_{1})|+|r_{1}(L_{2})|$. Combining this
with (5), we have $2|A_{2}|\geq|L_{1}|+|L_{2}|-|A_{1}|$, i.e., (7) holds. ∎

We extend the above process to the case $k>2$ in the next. Denote
$\mathsf{OPT}=\\{L_{1},\ldots,L_{k}\\}$, and $g_{x}=|A_{1}|+\ldots+|A_{x}|$
for $x\leq k$.

###### Lemma

For each $x\leavevmode\nobreak\ (1\leq x\leq k)$,

$\displaystyle\sum_{i=1}^{k}|r_{x}(L_{i})|$ $\displaystyle\geq$
$\displaystyle|\mathsf{OPT}|-g_{x},$ (9) $\displaystyle k|A_{x}|+g_{x-1}$
$\displaystyle\geq$ $\displaystyle|\mathsf{OPT}|$ (10)

Be aware that (9) extends (5), whereas (10) extends (6) and (7).

###### Proof of (9).

Denote $B=\bigcup_{j=1}^{x}A_{j}$ for short in this proof. Recall that
$L_{i}\setminus B$ is defined to be $r_{x}(L_{i})$. Clearly,
$\mathsf{OPT}\setminus B=(L_{1}\cup\ldots\cup L_{k})\setminus
B=r_{x}(L_{1})\cup\ldots\cup r_{x}(L_{k}).$ As a corollary,

$\mathsf{OPT}\subseteq(\mathsf{OPT}\setminus B)\cup
B=r_{x}(L_{1})\cup\ldots\cup r_{x}(L_{k})\cup B.$

It follows that $|\mathsf{OPT}|\leq\sum_{i=1}^{k}|r_{x}(L_{i})|+g_{x}$. Hence
(9) holds. ∎

###### Proof of (10).

Similar to (8), we have

$|A_{x}|\geq|r_{x-1}(L_{i})|\leavevmode\nobreak\ (\text{for each
}i\in\\{1,\ldots,k\\}).$ (11)

Applying (9), $g_{x-1}\geq|\mathsf{OPT}|-\sum_{i=1}^{k}|r_{x-1}(L_{i})|.$

Together, $g_{x-1}\geq|\mathsf{OPT}|-k|A_{x}|$; namely, (10) holds. ∎

For any $k\geq 1$, it holds that

$\frac{g_{k}}{|\mathsf{OPT}|}\geq 1-(\frac{k-1}{k})^{k}>1-\frac{1}{e}.$ (12)

###### Proof.

We first claim that for each $x\leavevmode\nobreak\ (1\leq x\leq k)$,

$kg_{x}\geq\sum_{i=0}^{x-1}(\frac{k-1}{k})^{i}|\mathsf{OPT}|.$ (13)

It follows that

$\begin{split}kg_{k}\geq&\sum_{i=0}^{k-1}(\frac{k-1}{k})^{i}|\mathsf{OPT}|\\\
=&\frac{(\frac{k-1}{k})^{k}-1}{\frac{k-1}{k}-1}|\mathsf{OPT}|=k\left(1-(\frac{k-1}{k})^{k}\right)|\mathsf{OPT}|,\end{split}$
(14)

which implies the ratio in (12).

We prove the essential formula (13) by induction in the following.

Note that $kg_{1}=k|A_{1}|\geq|L_{1}|+\ldots+|L_{k}|=|\mathsf{OPT}|$, whereas
$\sum_{i=0}^{0}(\frac{k-1}{k})^{i}=1$. So (13) holds for $x=1$. Next, assuming
that (13) holds for $x=m-1$, we shall prove that it also holds for $x=m$.

$\begin{split}kg_{m}&=k(|A_{m}|+g_{m-1})=(k|A_{m}|+g_{m-1})+\frac{k-1}{k}(kg_{m-1})\\\
&\geq|\mathsf{OPT}|+\frac{k-1}{k}\sum_{i=0}^{m-2}(\frac{k-1}{k})^{i}|\mathsf{OPT}|\\\
&=|\mathsf{OPT}|+\sum_{i=1}^{m-1}(\frac{k-1}{k})^{i}|\mathsf{OPT}|=\sum_{i=0}^{m-1}(\frac{k-1}{k})^{i}|\mathsf{OPT}|.\end{split}$

Thus the formula (13) also holds for $x$, completing the proof. ∎

###  3.2. Examples where $\frac{g_{k}}{|\mathsf{OPT}|}\approx\frac{3}{4}$ for
any $k\geq 2$

This subsection constructs an example, in which

$\frac{g_{k}}{|\mathsf{OPT}|}=\frac{1}{k^{2}}\lceil\frac{3}{4}k^{2}\rceil$
(15)

First, we define a $k\times k$ matrix $M$, whose rows are indexed with
$1,\ldots,k$ from bottom to top, and columns are indexed with $1,\ldots,k$
from left to right. Each element in the $i$-th row has a value $i$.

$k$ | $\ldots$ | $k$
---|---|---
$\vdots$ | $\ddots$ | $\vdots$
1 | $\ldots$ | 1

Next, build a sequence $\omega$ of length $k^{2}$ by concatenating the
following diagonals of $M$ — $(M_{1,1})$, $(M_{2,1},M_{1,2})$, …,
$(M_{k,1},\ldots,M_{1,k})$, …, $(M_{k,k-1},M_{k-1,k})$, $(M_{k,k})$. Elements
within each diagonal are enumerated from top left to bottom right; and
diagonals are enumerated from left to right; e.g. $\omega=(1,2,1,3,2,1,3,2,3)$
for $k=3$.

It is obvious that $\omega$ can be partitioned into $k$ subsequences, each of
which is a copy of $(1,\ldots,k)$. This means $|\mathsf{OPT}|=k^{2}$ when
$\omega$ is the given input of the $k$-LIS problem. In the following we show
that the greedy algorithm may return with
$g_{k}=\lceil\frac{3}{4}k^{2}\rceil$.

Let $D_{1-k},\ldots,D_{k-1}$ denote the $2k-1$ diagonals of $M$ parallel to
the minor diagonal of $M$; formally, $D_{x}\leavevmode\nobreak\ (1-k\leq x\leq
k-1)$ contains $M_{i,j}$ if $j=i+x$. We regard $D_{x}$ as a sequence rather
than a set — the elements are listed from bottom left to top right; e.g.,
$D_{0}=(M_{1,1},\ldots,M_{k,k})$. In this way, each $D_{x}$ is a subsequence
of $\omega$.

$D_{1-k}$ | $\ldots$ | $D_{-1}$ | $D_{0}$
---|---|---|---
$\vdots$ | $\iddots$ | $\iddots$ | $D_{1}$
$D_{-1}$ | $D_{0}$ | $\iddots$ | $\vdots$
$D_{0}$ | $D_{1}$ | $\ldots$ | $D_{k-1}$

###### Lemma

The greedy algorithm above may return the longest $k$ diagonals among
$D_{1-k},\ldots,D_{k-1}$ as its solution (namely, it returns $A_{1}=D_{0}$,
$A_{2i}=D_{i}$, $A_{2i+1}=D_{-i}$), yielding a total length
$\lceil\frac{3}{4}k^{2}\rceil$.

###### Proof.

Clearly, $D_{0}$ can be chosen as $A_{1}$, because $|D_{0}|=k$.

Suppose the lemma holds for the first $2j-1$ steps $j\geq 1$. Let $i=2j$.
Currently, the $2j-1$ longest subdiagonals of the table have been removed,
leaving 2 symmetrical triangular areas at the top left and bottom right of the
table. Let $T_{1}$ denote the top left triangular area and $T_{2}$ denote the
bottom right triangular area.

k | $\ldots$ | k | $\times$
---|---|---|---
$\vdots$ | $\ddots$ | $\times$ | $k-j$
$j+1$ | $\times$ | $\ddots$ | $\vdots$
$\times$ | 1 | $\ldots$ | 1

Note that there are 2 subdiagonals with the length of $k-j$, one is
$\\{j+1,\ldots,k\\}$, the other is $\\{1,\ldots,k-j\\}$, which are the longest
subdiagonals at the moment. Now we prove that there is no increasing
subsequence left that is longer than $k-j$.

Suppose we pick an increasing subsequence $S$ from $\omega_{k\times k}$, we
discuss its maximum length case by case.

(i)If $S$ starts in $T_{1}$, it starts from a number no smaller than $j+1$.
Since we only have $k$ numbers to form a sequence, $S$ can only be at most
$k-j$ long.

(ii)If $S$ ends in $T_{2}$, it ends with a number no bigger than $k-j$. Since
we only have $k$ numbers to form a sequence, $S$ can only be at most $k-j$
long.

(iii)If $S$ starts in $T_{2}$ and ends in $T_{1}$, it must have two
consecutive numbers $s_{1}s_{2}$, so that $s_{1}$ is in $T_{2}$ and $s_{2}$ is
in $T_{1}$. Then, we know that for $s_{1}$ in $T_{2}$, we have $s_{1}+j$ to
the left of it in $\omega_{k\times k}$. By observing the table, we know that
for all possible options in $T_{1}$, we have $s_{2}>s_{1}+j$. Since we only
have $k$ numbers to form a sequence, so $|S|\leq k-j$.

Therefore, for all possible increasing subsequence $S$, we have $|S|\leq k-j$.
So we take the two subdiagonals with the length of $k-j$ as the $D_{\max}$ for
step $2j$ and $2j+1$, and they are the longest increasing subsequences at that
time.

The total length of $|A_{1}|+\ldots+|A_{k}|$ can be calculated as follows.

$\left\\{\begin{array}[]{ll}k+2\sum_{i=1}^{\frac{k-1}{2}}(k-i)=\frac{3k^{2}+1}{4}=\lceil\frac{3}{4}k^{2}\rceil,&k\text{
is odd},\\\
k+2\sum_{i=1}^{\frac{k-2}{2}}(k-i)+\frac{k}{2}=\frac{3k^{2}}{4}=\lceil\frac{3}{4}k^{2}\rceil&k\text{
is even}.\end{array}\right.$

∎

##  4\. Summary & future work

We have shown that simple greedy algorithms achieve pretty small approximation
ratio in $k$-LIS and $k$-crashing problems. And the analysis is non-trivial.

Hopefully, the techniques developed in this paper can be used for analyzing
greedy algorithms of other related problems.

We would like to end up this paper with one challenging problem: Can we prove
a constant approximation ratio for Algorithm 1?

## References

  * (1)
  * Ballesteros-Pérez et al. (2019) Pablo Ballesteros-Pérez, Kamel Mohamed Elamrousy, and Mª Carmen González-Cruz. 2019.  Non-linear time-cost trade-off models of activity crashing: Application to construction scheduling and project compression with fast-tracking.  _Automation in Construction_ 97 (2019), 229–240.  https://doi.org/10.1016/j.autcon.2018.11.001
  * Cruz-Mejía and Letchford (2023) Oliverio Cruz-Mejía and Adam N. Letchford. 2023.  A survey on exact algorithms for the maximum flow and minimum-cost flow problems.  _Networks_ 82, 2 (2023), 167–176.  https://doi.org/10.1002/net.22169
  * Ferrari et al. (2022) Patrik L Ferrari, Muhittin Mungan, and M Mert Terzi. 2022\.  The Preisach graph and longest increasing subsequences.  _Annales de l’Institut Henri Poincaré D_ (2022).
  * Fulkerson (1961) Delbert Ray Fulkerson. 1961\.  A Network Flow Computation for Project Cost Curves.  _Management Science_ 7, 2 (1961), 167–178.  http://www.jstor.org/stable/2627099
  * Gerk and Qassim (2008) JosÉ Eduardo Vinhaes Gerk and Raad Yahya Qassim. 2008.  Project Acceleration via Activity Crashing, Overlapping, and Substitution.  _IEEE Transactions on Engineering Management_ 55, 4 (2008), 590–601.  https://doi.org/10.1109/TEM.2008.927786
  * Goyal (1996) Suresh K. Goyal. 1996\.  A simple time-cost tradeoff algorithm.  _Production Planning & Control_ 7, 1 (1996), 104–106.  https://doi.org/10.1080/09537289608930331
  * Greene (1974) Curtis Greene. 1974\.  An extension of Schensted’s theorem.  _Advances in Mathematics_ 14, 2 (1974), 254–265.
  * Kelley (1961) James E. Kelley. 1961\.  Critical-Path Planning and Scheduling: Mathematical Basis.  _Operations Research_ 9, 3 (1961), 296–320.  http://www.jstor.org/stable/167563
  * Mitzenmacher and Seddighin (2021) Michael Mitzenmacher and Saeed Seddighin. 2021.  Improved sublinear time algorithm for longest increasing subsequence. In _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_. SIAM, 1934–1947.
  * Phillips and Dessouky (1977) Steve Phillips and Mohamed I. Dessouky. 1977.  Solving the Project Time/Cost Tradeoff Problem Using the Minimal Cut Concept.  _Management Science_ 24, 4 (1977), 393–400.  http://www.jstor.org/stable/2630261
  * Romik (2015) Dan Romik. 2015\.  _The surprising mathematics of longest increasing subsequences_.  Number 4. Cambridge University Press.
  * Schensted (1961) Craige Schensted. 1961\.  Longest increasing and decreasing subsequences.  _Canadian Journal of mathematics_ 13 (1961), 179–191.
  * Siemens (1971) Nicolai Siemens. 1971\.  A Simple CPM Time-Cost Tradeoff Algorithm.  _Management Science_ 17, 6 (1971), B354–B363.  http://www.jstor.org/stable/2629138
  * Thomas and Yong (2011) Hugh Thomas and Alexander Yong. 2011.  Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm.  _Advances in Applied Mathematics_ 46, 1-4 (2011), 610–642.


# Transfer to a Low-Resource Language via Close Relatives:
The Case Study on Faroese

Vésteinn Snæbjarnarson1,2 Annika Simonsen3 Goran Glavaš4 Ivan Vulić5
1University of Copenhagen 2Miðeind ehf 3University of Iceland
4University of Würzburg 5University of Cambridge

###### Abstract

Multilingual language models have pushed state-of-the-art in cross-lingual NLP
transfer. The majority of zero-shot cross-lingual transfer, however, use one
and the same massively multilingual transformer (e.g., mBERT or XLM-R) to
transfer to all target languages, irrespective of their typological,
etymological, and phylogenetic relations to other languages. In particular,
readily available data and models of resource-rich sibling languages are often
ignored. In this work, we empirically show, in a case study for Faroese – a
low-resource language from a high-resource language family – that by
leveraging the phylogenetic information and departing from the ‘one-size-fits-
all’ paradigm, one can improve cross-lingual transfer to low-resource
languages. In particular, we leverage abundant resources of other Scandinavian
languages (i.e., Danish, Norwegian, Swedish, and Icelandic) for the benefit of
Faroese. Our evaluation results show that we can substantially improve the
transfer performance to Faroese by exploiting data and models of closely-
related high-resource languages. Further, we release a new web corpus of
Faroese and Faroese datasets for named entity recognition (NER), semantic text
similarity (STS), and new language models trained on all Scandinavian
languages.

##  1 Introduction

Massively multilingual Transformer-based language models (MMTs) such as mBERT
Devlin et al. (2019), XLM-RoBERTa Conneau et al. (2020a) and mT5 Xue et al.
(2021) have been the driving force of modern multilingual NLP, allowing for
rapid bootstrapping of language technology for a wide range of
low(er)-resource languages by means of (zero-shot or few-shot) cross-lingual
transfer from high(er)-resource languages Lauscher et al. (2020); Hu et al.
(2020); Xu and Murray (2022); Schmidt et al. (2022). Cross-lingual transfer
with MMTs is not without drawbacks. MMTs’ representation spaces are heavily
skewed in favor of high-resource languages, for which they have been exposed
to much more data in pretraining Joshi et al. (2020); Wu and Dredze (2020);
combined with the ‘curse of multilinguality’ – i.e., limited per-language
representation quality stemming from a limited capacity of the model Conneau
et al. (2020a); Pfeiffer et al. (2022) – this leads to lower representational
quality for languages underrepresented in MMTs’ pretraining. Cross-lingual
transfer with MMTs thus fails exactly in settings in which it is needed the
most: for low-resource languages with small digital footprint Zhao et al.
(2021). Despite these proven practical limitations, the vast majority of work
on cross-lingual transfer still relies on MMTs due to their appealing
conceptual generality: in theory, they support transfer between any two
languages seen in their pretraining. Such strict reliance on MMTs effectively
ignores the linguistic phylogenetics and fails to directly leverage resources
of resource-rich languages that are closely related to a target language of
interest.

In this work, we attempt to mitigate the above limitations for a particular
group of languages, departing from the ‘one-size-fits-all’ paradigm based on
MMTs. We focus on a frequent and realistic setup in which the target language
is a low-resource language but from a high-resource language family, i.e.,
with closely related resource-rich languages. A recent comprehensive
evaluation of the languages used in Europe111The _Digital Language Equality in
Europe by 2030: Strategic Agenda and Roadmap_ published by the European
Language Equality Programme (ELE), https://european-language-
equality.eu/agenda/. scores languages based on the available resources.
Languages such as German and Spanish score at around 0.5 of the English
scores, and more than half of the languages are scored below 0.02 of the
English score. Many, including almost all regional and minority languages such
as Faroese, Scottish Gaelic, Occitan, Luxembourgish, Romani languages,
Sicilian and Meänkieli have the score of (almost) 0. However, what
differentiates these languages from low-resource languages from Africa (e.g.,
Niger-Congo family) or indigenous languages of Latin America (e.g., Tupian
family) is the fact that they typically have closely related high-resource
languages as ‘language siblings’. In this case, we believe, language models
(LMs) of closely related high-resource languages promise more effective
transfer compared to using MMTs, plagued by the ‘curse of multilinguality’, as
the vehicle of transfer.

In this proof-of-concept case study, we focus on Faroese as the target
language and demonstrate the benefits of linguistically informed transfer. We
take advantage of available data and resources from the closely related but
much more ‘NLP-developed’ other Scandinavian languages.222The Scandinavian
languages are a family of Indo-European languages that form the North Germanic
branch of the Germanic languages. The largest languages of the family are: (1)
Danish (population 5.8M), Norwegian (5.4M) and Swedish (10.4M) – the Mainland
Scandinavian languages, and (2) Icelandic (373K) and Faroese (54K) – the
Insular Scandinavian languages. We show that using “Scandinavian” LMs brings
substantial gains in downstream transfer to Faroese compared to using XLM-R as
a widely used off-the-shelf MMT. The gains are particularly pronounced for the
task of semantic text similarity (STS), the only high-level semantic task in
our evaluation. We further show that adding a limited-size target-language
corpus to LM’s pretraining corpora brings further gains in downstream
transfer. As another contribution of this work, we collect and release: (1) a
corpus of web-scraped monolingual Faroese, (2) multiple LMs suitable for
Faroese, including those trained on all five Scandinavian languages, and (3)
two new task-specific datasets for Faroese labeled by native speakers: for NER
and STS.

##  2 Background and Related Work

Cross-Lingual Transfer Learning with MMTs and Beyond. A common approach to
cross-lingual transfer learning involves pretrained MMTs Devlin et al. (2019);
Conneau et al. (2020a); Xue et al. (2021). These models can be further
pretrained for specific languages or directly adapted for downstream tasks. A
major downside of the MMTs has been dubbed the _curse of multilinguality_
Conneau et al. (2020a), where the model becomes saturated and performance can
not be improved further for one language without a sacrifice elsewhere,
something which continued pretraining for a given language alleviates Pfeiffer
et al. (2020). Adapter training, such as in Pfeiffer et al. (2020); Üstün et
al. (2022), where small adapter modules are added to pretrained models, has
also enabled cost-efficient adaptation of these models. The adapters can then
be used to fine-tune for specific languages and tasks without incurring
catastrophic forgetting.

Other methods involve translation-based transfer Hu et al. (2020); Ponti et
al. (2021), and transfer from monolingual language models Artetxe et al.
(2020); Gogoulou et al. (2022); Minixhofer et al. (2022). Bilingual lexical
induction (BLI) is the method of mapping properties, in particular embeddings,
from one language to another via some means such as supervised embedding
alignment, unsupervised distribution matching or using an orthogonality
constraint Lample et al. (2018); Søgaard et al. (2018); Patra et al. (2019),
and has also been used to build language tools in low-resource languages Wang
et al. (2022).

Attempts to alleviate the abovementioned issues have been made, such as
vocabulary extension methods Pfeiffer et al. (2021), which add missing tokens
and their configurations to the embedding matrix. Phylogeny-inspired methods
have also been used where adapters have been trained for multiple languages
and stacked to align with the language family of the language of interest
Faisal and Anastasopoulos (2022). Some analysis on the effects of using
pretrained MMTs has been done: Fujinuma et al. (2022) conclude that using
pretrained MMTs that share script and overlap in the family with the target
language is beneficial. However, when adapting the model for a new language,
they claim that using as many languages as possible (up to 100) generally
yields the best performance.

Inspired by this line of research, in this work, we focus on improving MMT-
based cross-lingual transfer for a particular group of languages, those that
have sibling languages with more abundant data and resources.

NLP Resources in Scandinavian Languages. A fair amount of language resources
have been developed for the Scandinavian languages, particularly if aggregated
across all languages of the family. It is also worth mentioning that Danish,
Icelandic, Norwegian and Swedish are represented in raw multilingual corpora
such as CC100 Conneau et al. (2020b) or mC4 Xue et al. (2021) as well as in
parallel datasets such as Schwenk et al. (2021); Agić and Vulić (2019). Large
multilingual language models have been trained on these datasets Devlin et al.
(2019); Liu et al. (2020); Xue et al. (2021) but have been shown to have
limited capacity for languages with smaller relative representation in
pretraining corpora. Faroese is not included (at least not correctly labelled)
in these crawled corpora.This may be in part due to the limited amount of
Faroese that can be found online, and in part due to its close relatedness to
the other languages of the Scandinavian family Haas and Derczynski (2021). A
brief overview of prior work in cross-lingual transfer to Faroese is given in
Appendix D.

In this work, we use the following open language resources for the
Scandinavian languages.

Danish: The Danish Gigaword Corpus Strømberg-Derczynski et al. (2021) is a
billion-word corpus containing a wide variety of text.We also use a NER
resource, the DaNE corpus Hvingelby et al. (2020).

Icelandic: With Icelandic as the most closely related language to Faroese, we
experiment with an Icelandic language model, IceBERT Snæbjarnarson et al.
(2022). For the NER experiment, we make use of the MIM-GOLD-NER corpus
Ingólfsdóttir et al. (2020).

Norwegian: The Norwegian Colossal Corpus (NCC) Kummervold et al. (2022)
contains 49GB of clean Norwegian data from a variety of sources, making it the
largest such public collection in the Nordics. We also make use of the NorNE
Jørgensen et al. (2020) NER corpus (both for Bokmål and Nynorsk).

Swedish: The Swedish Gigaword Corpus Eide et al. (2016) contains text from
between 1950 and 2015. The latest NER corpus for Swedish is Swe-NERC Ahrenberg
et al. (2020), where the authors include more modern texts than in earlier
corpora.

Faroese: A POS corpus, the Sosiualurin corpus is an annotated Newspaper corpus
with 102k words Hansen et al. (2004). The Faroese Wikipedia has also been used
to create a tree bank Tyers et al. (2018), which has a Universal Dependencies
(UD) mapping. We use this corpus along with the FarPaHc Ingason et al. (2012),
which also has a UD mapping.

##  3 New Faroese Datasets

###  3.1 Faroese Common Crawl Corpus (FC3)

Faroese monolingual data is scarce, mainly because of the limited size of the
Faroese-speaking population. Despite this, we manage to extract a decent
amount of varied Faroese text from the Common Crawl corpus (FC3). To this
effect, we adopted the approach of Snæbjarnarson et al. (2022) for Icelandic,
i.e., we targeted the websites with the Faroese top-level domain (.fo). After
clean-up and deduplication, the obtained Faroese corpus consists of 98k
paragraphs containing in total 9M word-level tokens. Albeit relatively small
compared to corpora from other Scandinavian languages, this Faroese corpus
still drives significant downstream performance gains (see §5).

###  3.2 Named Entity Recognition (FoNE)

We annotate the Sosialurin corpus (6,286 lines, 102k words) with named
entities following the CoNLL schema using an Icelandic NER-tagger trained
using the ScandiBERT model, see §4. The annotation was then manually reviewed.
Out of the 118,533 tokens (including punctuation), 9,001 are annotated using
the Date (546), Location (1,774), Miscellaneous (332), Money (514),
Organization (2,585), Percent (115), Person (2,947) and Time (188) tags. We
refer to this new dataset as _FoNE_.

###  3.3 Semantic Similarity (Fo-STS)

The STS Benchmark Cer et al. (2017) measures semantic text similarity (STS)
between pairs of sentences. For each pair of sentences, the annotators
assigned the score (on a Likert 1-5 scale) that indicates the extent to which
the two sentences are semantically aligned. We manually translated from
English to Faroese 729 sentence pairs from the test portion of the STS
Benchmark; the translation was carried out by a native speaker of Faroese
fluent in English, who was instructed to preserve in the translation the
extent of semantic alignment between the original English sentences.

##  4 Model Training

We train the following new language models: (i) _ScandiBERT_ is trained on
concatenated corpora of all Scandinavian languages, (ii) _ScandiBERT-no-fo_ is
trained on concatenated corpora of all Scandinavian languages except Faroese
(i.e., without any Faroese data, that is, no FC3, Bible or Sosialurin), and
(iii) _DanskBERT_ which is trained only on the Danish data; we train
_DanskBERT_ for the purposes of comparison with IceBERT, in the setup in which
we carry out downstream transfer to Faroese by means of a monolingual model of
a closely related language (with Danish being more distant to Faroese than
Icelandic). We additionally evaluate transfer with models that have been
further pretrained on the FC3 corpus (indicated with the _-fc_ suffix). We
provide an overview of all training datasets and hyperparameter configurations
used in our experiments in Appendix A.

##  5 Experiments

| POS | NER | UD FP | UD oft | STS
---|---|---|---|---|---
Model | F1 | Acc. | F1 | Acc. | F1 | Acc. | F1 | Acc. | Acc.
IceBERT | 85.5 $\pm$ 0.19 | 85.2 $\pm$ 0.16 | 87.9 $\pm$ 0.54 | 96.4 $\pm$ 0.09 | 93.6 $\pm$ 0.06 | 94.6 $\pm$ 0.03 | 92.7 $\pm$ 0.32 | 94.2 $\pm$ 0.25 | 70.6 $\pm$ 1.9
IceBERT-fc3 | 90.9 $\pm$ 0.06 | 90.4 $\pm$ 0.06 | 90.9 $\pm$ 0.41 | 98.9 $\pm$ 0.03 | 96.6 $\pm$ 0.06 | 97.1 $\pm$ 0.06 | 95.3 $\pm$ 0.38 | 96.1 $\pm$ 0.32 | 72.9 $\pm$ 1.8
DanskBERT | 73.4 $\pm$ 0.19 | 74.3 $\pm$ 0.16 | 85.6 $\pm$ 0.44 | 98.4 $\pm$ 0.06 | 86.2 $\pm$ 0.16 | 87.7 $\pm$ 0.09 | 84.8 $\pm$ 0.57 | 88.7 $\pm$ 0.44 | 73.2 $\pm$ 1.3
DanskBERT-fc3 | 87.1 $\pm$ 0.13 | 86.4 $\pm$ 0.13 | 89.7 $\pm$ 0.54 | 98.8 $\pm$ 0.06 | 96.0 $\pm$ 0.06 | 96.6 $\pm$ 0.03 | 94.2 $\pm$ 0.28 | 95.7 $\pm$ 0.19 | 75.3 $\pm$ 1.1
XLM-R | 84.6 $\pm$ 0.28 | 85.0 $\pm$ 0.28 | 87.8 $\pm$ 0.47 | 96.3 $\pm$ 0.06 | 93.5 $\pm$ 0.06 | 94.3 $\pm$ 0.03 | 91.5 $\pm$ 0.44 | 93.6 $\pm$ 0.35 | 69.5 $\pm$ 2.1
XLM-R-fc3 | 91.2 $\pm$ 0.09 | 91.2 $\pm$ 0.09 | 90.9 $\pm$ 0.41 | 98.9 $\pm$ 0.06 | 97.3 $\pm$ 0.06 | 97.7 $\pm$ 0.03 | 95.7 $\pm$ 0.22 | 96.8 $\pm$ 0.19 | 69.2 $\pm$ 2.1
ScandiBERT-no-fo | 88.4 $\pm$ 0.09 | 88.1 $\pm$ 0.09 | 89.9 $\pm$ 0.25 | 96.7 $\pm$ 0.16 | 95.9 $\pm$ 0.06 | 96.4 $\pm$ 0.06 | 93.8 $\pm$ 0.35 | 95.0 $\pm$ 0.32 | 75.3 $\pm$ 1.5
ScandiBERT-no-fo-fc3 | 91.5 $\pm$ 0.09 | 91.2 $\pm$ 0.09 | 91.4 $\pm$ 0.35 | 98.8 $\pm$ 0.06 | 97.4 $\pm$ 0.03 | 97.8 $\pm$ 0.03 | 96.3 $\pm$ 0.22 | 96.8 $\pm$ 0.19 | 76.5 $\pm$ 1.3
ScandiBERT | 90.3 $\pm$ 0.09 | 90.0 $\pm$ 0.13 | 90.2 $\pm$ 0.28 | 99.0 $\pm$ 0.06 | 96.5 $\pm$ 0.06 | 97.1 $\pm$ 0.03 | 95.2 $\pm$ 0.32 | 96.2 $\pm$ 0.25 | 46.3 $\pm$ 6.3
ScandiBERT-fc3 | 91.6 $\pm$ 0.06 | 91.3 $\pm$ 0.09 | 91.0 $\pm$ 0.35 | 99.0 $\pm$ 0.03 | 97.3 $\pm$ 0.06 | 97.7 $\pm$ 0.06 | 95.9 $\pm$ 0.25 | 96.7 $\pm$ 0.22 | 63.8 $\pm$ 6.2
Table 1: Results for all downstream tasks in Faroese using the different base
language models, with and without continued Faroese pre-training. The -fc3
postfix indicates models that were further pretrained on FC3. Standard error
intervals are also reported.

###  5.1 Downstream Performance for Faroese

Experimental Setup. In addition to the models presented in §4, we make use of
the monolingual Icelandic model IceBERT and the massively multilingual XLM-on-
RoBERTa (XLM-R).333We use the base-sized XLM-R: https://huggingface.co/xlm-
roberta-base. We evaluate the performance of this set of pretrained models in
several downstream tasks in Faroese: Part-of-Speech tagging (POS), Dependency
Parsing (DP) (UD datasets introduced in §2), Named Entity Recognition (NER),
and Semantic Text Similarity (i.e., the new NER and STS datasets introduced in
§3). For all downstream tasks the task-specific training and evaluation data
span monolingual Faroese data points only: we carry out the experimentation
via ten-fold cross-validation on the respective Faroese datasets.444Note that
our study aims to establish how different pretraining strategies – and in
particular languages included in pretraining – affect the models’ downstream
Faroese performance, rather than to investigate the downstream cross-lingual
transfer. One could, naturally, additionally incorporate task-specific data in
other Scandinavian languages (and also in English and other languages) in
downstream training (i.e., perform cross-lingual transfer for the downstream
task). For each model and downstream task, we carry out ten runs with
different random seeds (each run trains the model for 5 epochs with batches of
16 instances) and report the average performance across runs. The exception is
the STS training in which the models were fine-tuned for 3 epochs (with
training batches of size 8).555Due to the limited size of the Faroese dataset,
longer training with larger batch size consistently led to overfitting.

Results and Discussion. Table 1 summarizes the results across the four
downstream tasks. The best-performing model for POS, as evaluated on the
Sosialurin POS corpus, is ScandiBERT-fc3, outperforming ScandiBERT by more
than 1 point in terms of F1. However, the ScandiBERT-no-fo-fc3 model, without
any Faroese data at pretraining, obtains fully on-par performance with the
variant that does include Faroese data.

The best-performing model for NER, and STS is the ScandiBERT-no-fo-fc3 model.
Somewhat surprisingly, we get the best performance for the model that does not
include any Faroese data in the initial pretraining, that is, it does not
adjust the tokenizer/vocabulary to Faroese. Put simply, we observe slight
gains over the ScandiBERT-fc3 model. We hypothesize that this might be due to
the fact that including Faroese in the vocabulary results in a lower subword
overlap with the other Scandinavian languages, which in consequence, slightly
reduces the potential for transfer. While there is only a difference of 95
tokens between the two vocabularies, the difference yields 6% of the words in
FC3 being tokenized differently.

Finally, the results also demonstrate the importance of focusing on a smaller
set of related languages rather than relying on a broader set of languages
from the MMTs. Unlike the results from Fujinuma et al. (2022), our results
suggest that for languages with higher-resource ‘siblings’ such as Faroese, a
higher-performing LM is a less general ScandiBERT model rather than an MMT
such as XLM-R or mBERT. Different variants of ScandiBERT outperform XLM-R
without any Faroese data across the board in all evaluation tasks. Another
interesting finding is that additionally fine-tuning on Faroese data (the -fc3
variants) has a much stronger positive impact on XLM-R as the underlying model
than on ScandiBERT. Put simply, the importance of in-target language data
decreases with the availability of more focused pretained LMs covering only
languages related to the target language.

###  5.2 Additional Experiments

Transfer with Wechsel. To put our work in further context, beyond comparison
to MMTs, we consider an alternative transfer learning approach, the Wechsel
method Minixhofer et al. (2022), a recent well-performing method for
transferring monolingual Transformers to a new language. Further details and
results are presented in Appendix B: they all show far worse performance than
those presented in Table 1. We hypothesize this is due to how closely related
the languages we consider are, as opposed to the distant languages considered
in the original Wechsel work.

Task-Specific Transfer. To explore the potential for task-specific transfer
between closely related languages, we consider if labelled Scandinavian
datasets can be combined to benefit Faroese. In particular, we look at NER as
there is an easy way to map between labels of the different languages. See
Appendix C for more details. The best result is achieved when training
directly from the IceBERT model, which has been trained on the large MIM-GOLD-
NER dataset, showing that given enough resources and a close enough language
model, such a direct approach can be the most effective.

Further Discussion. Some of the results in Table 1 are as expected. Starting
from the closest language relative, the Icelandic model, IceBERT, results in
better performance for all downstream tasks than starting with the Danish
model DanskBERT. The ScandiBERT model performs better than the massively
multilingual XLM-R on all tasks, bar the more semantic FO-STS task.

What is more interesting is that the ScandiBERT-no-fo model that is not
trained on Faroese outperforms the model that has Faroese included, when fine-
tuned further on the FC3 dataset. In particular, for the higher level Fo-STS
task. We hypothesize that this forces the Faroese adaptation to use the word
segmentations from the related languages for a higher transfer benefit, as the
tokenizing vocabulary was trained without Faroese. This is something we hope
to investigate more in future work.

##  6 Conclusion and Future Work

We have shown that leveraging phylogenetic information and departing from the
‘one-size-fits-all’ paradigm can improve cross-lingual transfer to low-
resource languages. Our evaluation results show that we can substantially
improve the transfer performance to Faroese by exploiting data and models of
closely-related high-resource languages instead of relying on MMTs. In future
work, we hope to extend the investigations and methodology beyond Faroese, to
other low-resource languages for which higher-resource language relatives
exist.

In order to boost and guide future research on Scandinavian languages in
general and Faroese in particular, we make the models _ScandiBERT_
666https://huggingface.co/vesteinn/ScandiBERT, _ScandiBERT-no-fo_
777https://huggingface.co/vesteinn/ScandiBERT-no-faroese, _DanskBERT_
888https://huggingface.co/vesteinn/DanskBERT and _FoBERT (ScandiBERT-no-fo-
fc3)_ 999https://huggingface.co/vesteinn/FoBERT available. As well as the new
datasets _FC3_ 101010https://huggingface.co/datasets/vesteinn/FC3, _FoNE_
111111https://huggingface.co/datasets/vesteinn/sosialurin-faroese-ner, and
_Fo-STS_ 121212https://huggingface.co/datasets/vesteinn/faroese-sts.

## Acknowledgments

VS is supported by the Pioneer Centre for AI, DNRF grant number P1. The work
of IV has been supported by a personal Royal Society University Research
Fellowship (no 221137; 2022-).

We would like to thank Haukur Barri Símonarson for his comments on the work in
its early stages. We also thank Prof. Dr.-Ing. Morris Riedel and his team for
providing access to the DEEP cluster at Forschungszentrum Jülich.

## References

  * Agić and Vulić (2019) Željko Agić and Ivan Vulić. 2019.  JW300: A wide-coverage parallel corpus for low-resource languages.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3204–3210, Florence, Italy. Association for Computational Linguistics.
  * Ahrenberg et al. (2020) Lars Ahrenberg, Johan Frid, and Leif-Jöran Olsson. 2020.  A new resource for swedish named-entity recognition.
  * Artetxe et al. (2020) Mikel Artetxe, Sebastian Ruder, and Dani Yogatama. 2020.  On the cross-lingual transferability of monolingual representations.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4623–4637, Online. Association for Computational Linguistics.
  * Barry et al. (2019) James Barry, Joachim Wagner, and Jennifer Foster. 2019.  Cross-lingual parsing with polyglot training and multi-treebank learning: A Faroese case study.  In _Proceedings of the 2nd Workshop on Deep Learning Approaches for Low-Resource NLP (DeepLo 2019)_ , pages 163–174, Hong Kong, China. Association for Computational Linguistics.
  * Cer et al. (2017) Daniel Cer, Mona Diab, Eneko Agirre, Iñigo Lopez-Gazpio, and Lucia Specia. 2017\.  SemEval-2017 task 1: Semantic textual similarity multilingual and crosslingual focused evaluation.  In _Proceedings of the 11th International Workshop on Semantic Evaluation (SemEval-2017)_ , pages 1–14, Vancouver, Canada. Association for Computational Linguistics.
  * Conneau et al. (2020a) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020a.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8440–8451, Online. Association for Computational Linguistics.
  * Conneau et al. (2020b) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Édouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020b.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8440–8451.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Eide et al. (2016) Stian Rødven Eide, Nina Tahmasebi, and Lars Borin. 2016.  The swedish culturomics gigaword corpus: A one billion word swedish reference dataset for nlp.
  * Faisal and Anastasopoulos (2022) Fahim Faisal and Antonios Anastasopoulos. 2022.  Phylogeny-inspired adaptation of multilingual models to new languages.  In _Proceedings of the 2nd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 12th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 434–452, Online only. Association for Computational Linguistics.
  * Forcada and Tyers (2016) Mikel L. Forcada and Francis M. Tyers. 2016.  Apertium: a free/open source platform for machine translation and basic language technology.  In _Proceedings of the 19th Annual Conference of the European Association for Machine Translation: Projects/Products_ , Riga, Latvia. Baltic Journal of Modern Computing.
  * Fujinuma et al. (2022) Yoshinari Fujinuma, Jordan Boyd-Graber, and Katharina Kann. 2022.  Match the script, adapt if multilingual: Analyzing the effect of multilingual pretraining on cross-lingual transferability.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1500–1512, Dublin, Ireland. Association for Computational Linguistics.
  * Gogoulou et al. (2022) Evangelia Gogoulou, Ariel Ekgren, Tim Isbister, and Magnus Sahlgren. 2022.  Cross-lingual transfer of monolingual models.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 948–955, Marseille, France. European Language Resources Association.
  * Grave et al. (2018) Edouard Grave, Piotr Bojanowski, Prakhar Gupta, Armand Joulin, and Tomas Mikolov. 2018.  Learning word vectors for 157 languages.  In _Proceedings of the International Conference on Language Resources and Evaluation (LREC 2018)_.
  * Haas and Derczynski (2021) René Haas and Leon Derczynski. 2021.  Discriminating between similar nordic languages.  In _Proceedings of the Eighth Workshop on NLP for Similar Languages, Varieties and Dialects_ , pages 67–75, Kiyv, Ukraine. Association for Computational Linguistics.
  * Hafsteinsson and Ingason (2021) Hinrik Hafsteinsson and Anton Karl Ingason. 2021.  Towards cross-lingual application of language-specific PoS tagging schemes.  In _Proceedings of the 23rd Nordic Conference on Computational Linguistics (NoDaLiDa)_ , pages 321–325, Reykjavik, Iceland (Online). Linköping University Electronic Press, Sweden.
  * Hansen et al. (2004) Zakaris Svabo Hansen, Heini Justinussen, and Mortan Ólason. 2004.  Marking av teldutøkum tekstsavni [tagging of a digital text corpus].
  * Hu et al. (2020) Junjie Hu, Sebastian Ruder, Aditya Siddhant, Graham Neubig, Orhan Firat, and Melvin Johnson. 2020.  Xtreme: A massively multilingual multi-task benchmark for evaluating cross-lingual generalisation.  In _International Conference on Machine Learning_ , pages 4411–4421. PMLR.
  * Hvingelby et al. (2020) Rasmus Hvingelby, Amalie Brogaard Pauli, Maria Barrett, Christina Rosted, Lasse Malm Lidegaard, and Anders Søgaard. 2020.  DaNE: A named entity resource for Danish.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pages 4597–4604, Marseille, France. European Language Resources Association.
  * Ingason et al. (2012) Anton Karl Ingason, Eiríkur Rögnvaldsson, Einar Freyr Sigurðsson, and Joel C. Wallenberg. 2012.  Faroese parsed historical corpus (FarPaHC) 0.1.  CLARIN-IS.
  * Ingólfsdóttir et al. (2020) Svanhvít L. Ingólfsdóttir, Ásmundur A. Guðjónsson, and Hrafn Loftsson. 2020.  Named entity recognition for icelandic: Annotated corpus and models.  In _Statistical Language and Speech Processing_ , pages 46–57, Cham. Springer International Publishing.
  * Jørgensen et al. (2020) Fredrik Jørgensen, Tobias Aasmoe, Anne-Stine Ruud Husevåg, Lilja Øvrelid, and Erik Velldal. 2020.  NorNE: Annotating named entities for Norwegian.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pages 4547–4556, Marseille, France. European Language Resources Association.
  * Joshi et al. (2020) Pratik Joshi, Sebastin Santy, Amar Budhiraja, Kalika Bali, and Monojit Choudhury. 2020.  The state and fate of linguistic diversity and inclusion in the NLP world.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 6282–6293, Online. Association for Computational Linguistics.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 66–71, Brussels, Belgium. Association for Computational Linguistics.
  * Kummervold et al. (2022) Per Kummervold, Freddy Wetjen, and Javier de la Rosa. 2022.  The Norwegian colossal corpus: A text corpus for training large Norwegian language models.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 3852–3860, Marseille, France. European Language Resources Association.
  * Lample et al. (2018) Guillaume Lample, Alexis Conneau, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. 2018.  Word translation without parallel data.  In _International Conference on Learning Representations_.
  * Lauscher et al. (2020) Anne Lauscher, Vinit Ravishankar, Ivan Vulić, and Goran Glavaš. 2020.  From zero to hero: On the limitations of zero-shot language transfer with multilingual Transformers.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 4483–4499, Online. Association for Computational Linguistics.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer. 2020.  Multilingual denoising pre-training for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , 8:726–742.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized BERT pretraining approach.  _CoRR_ , abs/1907.11692.
  * Minixhofer et al. (2022) Benjamin Minixhofer, Fabian Paischer, and Navid Rekabsaz. 2022.  WECHSEL: Effective initialization of subword embeddings for cross-lingual transfer of monolingual language models.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3992–4006, Seattle, United States. Association for Computational Linguistics.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)_ , pages 48–53, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Patra et al. (2019) Barun Patra, Joel Ruben Antony Moniz, Sarthak Garg, Matthew R. Gormley, and Graham Neubig. 2019.  Bilingual lexicon induction with semi-supervision in non-isometric embedding spaces.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 184–193, Florence, Italy. Association for Computational Linguistics.
  * Pfeiffer et al. (2022) Jonas Pfeiffer, Naman Goyal, Xi Lin, Xian Li, James Cross, Sebastian Riedel, and Mikel Artetxe. 2022.  Lifting the curse of multilinguality by pre-training modular transformers.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3479–3495, Seattle, United States. Association for Computational Linguistics.
  * Pfeiffer et al. (2020) Jonas Pfeiffer, Ivan Vulić, Iryna Gurevych, and Sebastian Ruder. 2020.  MAD-X: An Adapter-Based Framework for Multi-Task Cross-Lingual Transfer.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7654–7673, Online. Association for Computational Linguistics.
  * Pfeiffer et al. (2021) Jonas Pfeiffer, Ivan Vulić, Iryna Gurevych, and Sebastian Ruder. 2021.  UNKs everywhere: Adapting multilingual language models to new scripts.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 10186–10203, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Ponti et al. (2021) Edoardo Maria Ponti, Julia Kreutzer, Ivan Vulic, and Siva Reddy. 2021.  Modelling latent translations for cross-lingual transfer.  _CoRR_ , abs/2107.11353.
  * Schmidt et al. (2022) Fabian David Schmidt, Ivan Vulić, and Goran Glavaš. 2022.  Don’t stop fine-tuning: On training regimes for few-shot cross-lingual transfer with multilingual language models.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 10725–10742, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Schwenk et al. (2021) Holger Schwenk, Guillaume Wenzek, Sergey Edunov, Edouard Grave, Armand Joulin, and Angela Fan. 2021.  CCMatrix: Mining billions of high-quality parallel sentences on the web.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 6490–6500, Online. Association for Computational Linguistics.
  * Snæbjarnarson et al. (2022) Vésteinn Snæbjarnarson, Haukur Barri Símonarson, Pétur Orri Ragnarsson, Svanhvít Lilja Ingólfsdóttir, Haukur Jónsson, Vilhjalmur Thorsteinsson, and Hafsteinn Einarsson. 2022.  A warm start and a clean crawled corpus - a recipe for good language models.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 4356–4366, Marseille, France. European Language Resources Association.
  * Søgaard et al. (2018) Anders Søgaard, Sebastian Ruder, and Ivan Vulić. 2018.  On the limitations of unsupervised bilingual dictionary induction.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 778–788, Melbourne, Australia. Association for Computational Linguistics.
  * Strømberg-Derczynski et al. (2021) Leon Strømberg-Derczynski, Manuel Ciosici, Rebekah Baglini, Morten H. Christiansen, Jacob Aarup Dalsgaard, Riccardo Fusaroli, Peter Juel Henrichsen, Rasmus Hvingelby, Andreas Kirkedal, Alex Speed Kjeldsen, Claus Ladefoged, Finn Årup Nielsen, Jens Madsen, Malte Lau Petersen, Jonathan Hvithamar Rystrøm, and Daniel Varab. 2021.  The Danish Gigaword corpus.  In _Proceedings of the 23rd Nordic Conference on Computational Linguistics (NoDaLiDa)_ , pages 413–421, Reykjavik, Iceland (Online). Linköping University Electronic Press, Sweden.
  * Tyers et al. (2018) Francis Tyers, Mariya Sheyanova, Aleksandra Martynova, Pavel Stepachev, and Konstantin Vinogorodskiy. 2018.  Multi-source synthetic treebank creation for improved cross-lingual dependency parsing.  In _Proceedings of the Second Workshop on Universal Dependencies (UDW 2018)_ , pages 144–150, Brussels, Belgium. Association for Computational Linguistics.
  * Üstün et al. (2022) Ahmet Üstün, Arianna Bisazza, Gosse Bouma, Gertjan van Noord, and Sebastian Ruder. 2022.  Hyper-X: A unified hypernetwork for multi-task multilingual transfer.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 7934–7949, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Wang et al. (2022) Xinyi Wang, Sebastian Ruder, and Graham Neubig. 2022.  Expanding pretrained models to thousands more languages via lexicon-based adaptation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 863–877, Dublin, Ireland. Association for Computational Linguistics.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Wu and Dredze (2020) Shijie Wu and Mark Dredze. 2020.  Are all languages created equal in multilingual BERT? In _Proceedings of the 5th Workshop on Representation Learning for NLP_ , pages 120–130, Online. Association for Computational Linguistics.
  * Xu and Murray (2022) Haoran Xu and Kenton Murray. 2022.  Por qué não utiliser alla språk? mixed training with gradient optimization in few-shot cross-lingual transfer.  In _Findings of the Association for Computational Linguistics: NAACL 2022_ , pages 2043–2059, Seattle, United States. Association for Computational Linguistics.
  * Xue et al. (2021) Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. 2021.  mT5: A massively multilingual pre-trained text-to-text transformer.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 483–498, Online. Association for Computational Linguistics.
  * Zhao et al. (2021) Mengjie Zhao, Yi Zhu, Ehsan Shareghi, Ivan Vulić, Roi Reichart, Anna Korhonen, and Hinrich Schütze. 2021.  A closer look at few-shot crosslingual transfer: The choice of shots matters.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 5751–5767, Online. Association for Computational Linguistics.

##  Appendix A Training of language models

Language |  Datasets | Size
---|---|---
Icelandic |  IGC / IC3 / Skemman / Hirslan | 16 GB
Danish |  Danish Gigaword Corpus (incl. Twitter) | 4,7 GB
Norwegian |  NCC corpus | 42 GB
Swedish |  Swedish Gigaword Corpus | 3,4 GB
Faroese |  FC3 + Sosialurinn + Bible | 69 MB
Table 2: Datasets used to train ScandiBERT, ScandiBERT-no-fo and DanskBERT

We train new BPE vocabularies for all the new models we train, ScandiBERT,
ScandiBERT-no-fo, and DanskBERT. All models use the same vocabulary size of
50k. The ScandiBERT vocabulary is trained using all the languages, the
ScandiBERT-no-fo vocabulary is trained without the Faroese data, and the
DanskBERT vocabulary is only trained on the Danish text. Vocabularies are
trained using the SentencePiece software Kudo and Richardson (2018), and
character coverage is set to 99.995 %.

Pre-training of the new language models is done using fairseq Ott et al.
(2019) using the RoBERTa-base Liu et al. (2019) configuration, fine-tuning is
done using the transformers Wolf et al. (2020) library. ScandiBERT and
ScandiBERT-no-fo were trained for 72 epochs, using a batch size of 8.8k
sequences on 24 NVIDIA V100 cards for approximately 14 days each. Initial
testing showed that the larger batch size showed better performance than going
for around 2k sequences, possibly due to the mixture of differing languages.
DanskBERT, on the other hand, similar to IceBERT and RoBERTa showed better
performance at the smaller batch size. DanskBERT was trained to convergence
for 500k steps using 16 V100 cards for approximately 14 days.

All _-fc_ models are further trained for 50 epochs, with an effective batch
size of 100k tokens for 12k updates, over the FC3 dataset for Faroese
adaptation.

An overview of the data used to train the language models is shown in Table 2.
For details on the Icelandic data, we refer to Snæbjarnarson et al. (2022).
For the other datasets, we refer to §2.

##  Appendix B Wechsel results

We compare our method to another transfer learning approach presented by
Minixhofer et al. (2022). The FC3 dataset is used to train fastText embeddings
for Faroese, and the Icelandic datasets are used to train fastText embeddings
for Icelandic. These embeddings are then used to convert the multilingual
models to Faroese using the Wechsel approach. We confirm the quality of the
Icelandic embeddings by running an Icelandic semantic evaluation suite adapted
from https://github.com/stofnun-arna-magnussonar/ordgreypingar_embeddings,
showing our embeddings are comparable or of higher quality than those released
by Meta Grave et al. (2018).

The experiments in Table 3 all show sub-par performance compared to the
results in non-Wechsel results in Table 1. The Wechsel work considers transfer
from English-dominant models, GPT2 and RoBERTa to French, German, Chinese,
Swahili, Sundanese, Scottish Gaelic, Uyghur and Malagasy. None of which are
closely related to English. One reason for the discrepancy in the results
could be that the shuffling of the embedding matrix to convert it is more
catastrophic when considering close languages. Another reason could be that
both Faroese and Icelandic are morphologically rich and that all variants of
the words were not properly mapped during the conversion of the embedding
matrix.

|  | POS | NER | UD FP | UD oft | STS
---|---|---|---|---|---|---
|  Model | F1 | Acc. | F1 | Acc. | F1 | Acc. | F1 | Acc. | Acc.
Wechsel |  IceBERT | 74.4 $\pm$ 0.16 | 75.7 $\pm$ 0.16 | 67.7 $\pm$ 1.2 | 98.7 $\pm$ 0.06 | 83.6 $\pm$ 0.35 | 84.6 $\pm$ 0.38 | 66.6 $\pm$ 9.01 | 75.7 $\pm$ 5.88 | 27.3 $\pm$ 3.9
IceBERT-fc3 | 89.0 $\pm$ 0.06 | 89.4 $\pm$ 0.09 | 88.5 $\pm$ 0.47 | 96.4 $\pm$ 0.09 | 96.3 $\pm$ 0.03 | 96.5 $\pm$ 0.03 | 95.6 $\pm$ 0.28 | 96.2 $\pm$ 0.25 | 67.7 $\pm$ 2.8
XLM-R | 68.9 $\pm$ 0.16 | 73.5 $\pm$ 0.13 | 59.7 $\pm$ 0.92 | 99.0 $\pm$ 0.06 | 81.0 $\pm$ 0.19 | 84.5 $\pm$ 0.13 | 71.8 $\pm$ 0.73 | 79.7 $\pm$ 0.44 | 11.4 $\pm$ 4.6
XLM-R-fc3 | 86.8 $\pm$ 0.09 | 88.7 $\pm$ 0.09 | 88.8 $\pm$ 0.41 | 98.4 $\pm$ 0.06 | 96.3 $\pm$ 0.03 | 96.7 $\pm$ 0.03 | 95.6 $\pm$ 0.25 | 96.5 $\pm$ 0.19 | 65.7 $\pm$ 2.8
ScandiBERT-no-fo | 71.3 $\pm$ 0.16 | 72.5 $\pm$ 0.16 | 65.1 $\pm$ 0.54 | 98.8 $\pm$ 0.03 | 82.0 $\pm$ 0.19 | 83.4 $\pm$ 0.19 | 75.0 $\pm$ 0.66 | 81.0 $\pm$ 0.57 | 29.4 $\pm$ 4.8
ScandiBERT-n.f.-fc3 | 89.2 $\pm$ 0.06 | 89.6 $\pm$ 0.06 | 89.2 $\pm$ 0.54 | 99.0 $\pm$ 0.03 | 96.8 $\pm$ 0.06 | 97.1 $\pm$ 0.06 | 96.1 $\pm$ 0.28 | 96.8 $\pm$ 0.22 | 74.7 $\pm$ 1.0
ScandiBERT | 72.6 $\pm$ 0.28 | 73.8 $\pm$ 0.28 | 65.7 $\pm$ 0.54 | 98.8 $\pm$ 0.03 | 83.0 $\pm$ 0.38 | 84.0 $\pm$ 0.28 | 76.8 $\pm$ 0.51 | 82.5 $\pm$ 0.35 | 8.7 $\pm$ 5.3
ScandiBERT-fc3 | 89.3 $\pm$ 0.09 | 89.7 $\pm$ 0.09 | 88.8 $\pm$ 0.54 | 98.7 $\pm$ 0.06 | 96.8 $\pm$ 0.03 | 97.1 $\pm$ 0.03 | 96.0 $\pm$ 0.25 | 96.7 $\pm$ 0.25 | 53.6 $\pm$ 6.0
Table 3: Results for all downstream tasks using different base language models
after Wechsel adaptation, with and without continued Faroese pre-training. The
results are significantly worse than without Wechsel adaptations.

##  Appendix C Mapping NER datasets

Model | Pre-ft. | Ft. | F1 | Acc.
---|---|---|---|---
SB-no-fo-fc3 | None | Yes | 91.4 $\pm$ 0.35 | 98.8 $\pm$ 0.06
ScandiBERT | Icel. | Yes | 92.0 $\pm$ 0.32 | 98.8 $\pm$ 0.06
ScandiBERT | All | No | 91.5 $\pm$ 0.51 | 98.9 $\pm$ 0.06
ScandiBERT | All | Yes | 91.8 $\pm$ 0.51 | 99.0 $\pm$ 0.06
XLM-R | All | No | 90.6 $\pm$ 0.19 | 99.0 $\pm$ 0.03
XLM-R | All | Yes | 90.8 $\pm$ 0.47 | 99.0 $\pm$ 0.06
Table 4: NER performance when models are pre-finetuned on all Scandinavian datasets and then fine-tuned on FoNER. Language | Original | Mapped
---|---|---
Norwegian | O | O
Norwegian | PER | Person
Norwegian | ORG | Organization
Norwegian | GPE_LOC | Location
Norwegian | PROD | Miscellaneous
Norwegian | LOC | Location
Norwegian | GPE_ORG | Organization
Norwegian | DRV | O
Norwegian | EVT | Miscellaneous
Norwegian | MISC | Miscellaneous
Swedish | O | O
Swedish | EVN | Miscellaneous
Swedish | GRO | Organization
Swedish | LOC | Location
Swedish | MNT | Miscellaneous
Swedish | PRS | Person
Swedish | TME | Time
Swedish | WRK | Miscellaneous
Swedish | SMP | Miscellaneous
Table 5: Mapping of tags to create a unified NER dataset for the Scandinavian
languages.

The datasets used to create a Scandinavian NER-corpus are DaNE (Danish), FoNE
(Faroese), MIM-GOLD-NER (Icelandic), NorNE (Norwegian), and SWE-Nerc
(Swedish), presented in §2. The results in Table 4 show that the best result
is obtained when training directly from the IceBERT model. The ScandiBERT
model has a higher variance when pre-fine-tuned on the combined NER corpora.
This approach could also be made directly for the UD corpus, POS (in
particular, using the Icelandic POS data), and other corpora as they become
available for training or evaluation in Faroese. This demonstrates how
resources from a related language can substantially benefit a low-resource
language.

To combine the NER datasets, we map the tags to the CoNLL schema used by the
Icelandic MIM-GOLD-NER and the Faroese FoNE datasets. The Danish DaNE dataset
uses a subset of the tags used for Icelandic and Faroese, so the mapping is
purely nominal. The mapping for Norwegian (NorNE) and Swedish (SweNERC)
datasets is shown in Table 5.

##  Appendix D Prior Work on Transfer learning for Faroese

We know of three works that consider transfer learning for Faroese from the
Scandinavian languages. In Tyers et al. (2018), a rule-based translation
system (Apertium Forcada and Tyers (2016)) is used to translate the Faroese
Wikipedia into Swedish, Norwegian Bokmål, and Norwegian Nynorsk. The
translations are then aligned, and the translations dependency-parsed. The
resulting trees are then mapped to the original Faroese sentences and used for
POS-tagging and annotating morphological features. The second work is a
mapping between Faroese and Icelandic POS-tags Hafsteinsson and Ingason
(2021); while not a direct application, the authors suggest the mapping may be
of use for transfer learning between the languages. Finally, Barry et al.
(2019) use machine translation and dependency parsing for cross-lingual
syntactic knowledge transfer from Danish, Norwegian, and Swedish to Faroese.