11institutetext: Spoken Language Systems Group,
Saarland Informatics Campus, Saarland University, Saarbrücken, Germany.
22institutetext: Testifi.io, München, Germany
22email<EMAIL_ADDRESS>saarland.de

# TOKEN is a MASK: Few-shot Named Entity Recognition with Pre-trained Language
Models

Ali Davody  0000-0003-2687-4577 1122 David Ifeoluwa Adelani
0000-0002-0193-2083  11 Thomas Kleinbauer 11 Dietrich Klakow 11

###### Abstract

Transferring knowledge from one domain to another is of practical importance
for many tasks in natural language processing, especially when the amount of
available data in the target domain is limited. In this work, we propose a
novel few-shot approach to domain adaptation in the context of Named Entity
Recognition (NER). We propose a two-step approach consisting of a variable
base module and a template module that leverages the knowledge captured in
pre-trained language models with the help of simple descriptive patterns. Our
approach is simple yet versatile, and can be applied in few-shot and zero-shot
settings. Evaluating our lightweight approach across a number of different
datasets shows that it can boost the performance of state-of-the-art baselines
by $2-5\%$ F1-score.

###### Keywords:

Named entity recognition Few-shot learning Transfer learning Prompt-tuning

##  1 Introduction

Transfer learning has received increased attention in recent years because it
provides an approach to a common problem for many realistic Natural Language
Processing (NLP) tasks: the shortage of high-quality, annotated training data.
While different implementations exist, the basic tenet is to utilize available
data in a source domain to help training a classifier for a low-resource
target domain.

An interesting new direction of research leverages the world knowledge
captured by pre-trained language models (PLMs) with cloze-style natural
language prompts for few-shot classification (e.g. [1, 18]) and regression
[5]. These approaches are attractive because they require little to no
training, making them especially suitable for low-resource settings.

In this paper, we contribute to this research area by introducing a novel
cloze-style approach to Named Entity Recognition (NER), an important task
which has previously not been addressed via cloze-style prompts. In its
classical setting, i.e. recognizing a small number of entity types in
newspaper texts, NER achieves state-of-the-art F1 scores of $\sim{}95\%$ [25].
This is not necessarily the case, however, for more specialized domains where
data is more scarce and annotations cannot easily be provided because they may
require expert knowledge, such as e.g., for biomedical texts. With the
approach presented here, the expertise of highly trained specialists can be
utilized in a different way, by providing representative words for the named
entity types, rather than having to annotate corpus data.

The main appeal of our method lies in its simplicity, as applying it to a new
domain requires very little effort and technical expertise. Our contribution
is three-fold: (1) we introduce a new method for Named Entity Recognition
(NER) with a focus on simplicity; (2) our technique is scalable down to zero-
shot in which case _no training_ is required on top of the PLM; (3) we show
how a hybrid combination of our method with a standard classifier based on a
simple threshold outperforms both of the individual classifiers (Section 3).

The effectiveness of our method is demonstrated by a thorough evaluation
comparing different variants of the approach across a number of different data
sets (Section 5). For reproducibility, we release our code on
Github111https://github.com/uds-lsv/TOKEN-is-a-MASK

##  2 Related Work

Named entity recognition is a well-studied task in NLP, and is usually
approached as a sequence-labeling problem where pre-trained language models
such as ELMO [12], BERT [2], RoBERTa [11] and LUKE [25] have brought
significant improvements in recent years. All these methods are based on
supervised learning but they do not generalize to new domains in zero and few-
shot settings.

Meta-learning or learning to learn [17, 3, 20] is a popular approach to few-
shot learning. In the context of few-shot NER, most applications of meta-
learning make use of Prototypical Networks [4, 7, 8] or Model-Agnostic Meta-
Learning (MAML) [9]. These approaches require training on diverse domains or
datasets to generalize to new domains.

Pre-trained language models have shown impressive potential in learning many
NLP tasks without training data [13, 15]. [18] proposed using a cloze-style
question to enable masked LMs in few-shot settings to perform text
classification and natural inference tasks with better performance than GPT-3
[1]. As creating cloze-style questions is time consuming, there are some
attempts to automate this process. [6] makes use of the T5 model [16] to
generate appropriate template by filling a [MASK] phrase similar to how T5 was
trained. Shin et al. (2020) [19] use a template that combines the original
sentence to classify with some trigger tokens and a [MASK] token that is
related to the label name. The trigger tokens are learned using gradient-based
search strategy proposed in [23]. In this paper, we extend this PLM prompt
technique to named entity recognition.

##  3 Method

Our approach consists of two parts. We first describe the _base method_ that
can be used as a stand-alone, zero- or few-shot classifier (Section 3.1). In
Section 3.2, we then lay out how a simple ensemble method can combine the base
method with another classifier to potentially improve over the individual
performance of both. We call this setup the _hybrid method_.

###  3.1 Zero-Shot Base Method

The base method for classifying NEs in a sentence consists of two steps,
detecting candidate words and querying a PLM for the NE class of each
candidate word. For example, let $s=$ I will visit Munich next week be the
sentence to label. As is typical, most words in $s$ do not denote a named
entity, only Munich does (LOC). We construct a cloze-style query to the PLM
from the original sentence and a template, in which the candidate word has
been inserted:

I would like to visit Munich next week. Munich is a [MASK].

The first part of the prompt serves as the context for the second part of the
prompt, a template of a predefined form e.g. [TOKEN] is a [MASK]. The [TOKEN]
is replaced with the term to label. For auto-regressive LMs like GPT-2, [MASK]
is empty, the next word is predicted given a context that ends with “TOKEN is
a ”.

The prediction of the PLM for the [MASK] is a probability distribution
$P(w|s)$ over the tokens $w$ in the vocabulary $\mathcal{V}$. Intuitively,
since NE labels themselves often are descriptive words (e.g. location, person,
etc.) contained in $\mathcal{V}$, the answer to the query could be found by
observing $P(label|s)$ for all labels and selecting the one with the highest
probability. We found this approach not to perform well, possibly because NE
labels tend to describe abstract higher-level concepts that are not commonly
used in sentences realized by our template.

However, by associating with each entity type a list of words representative
of that type, we reach competitive performance to state-of-the-art approaches
(see Section 5). As an example, table 1 shows representative words for the
five named entity classes Location, Person, Organization, Ordinal and Date.

More formally, let $\mathcal{L}$ be the set of all labels for the NER
classification task. We provide a list of representative words
$\mathcal{W}_{l}$ for each label $l$. Denoting the output of the PLM by
$P(\cdot|s+T(w))$ where $s$ is the original sentence, $T(w)$ is the prompt for
token $w$, and $+$ stands for string concatenation, we assign label $l_{w}$ to
the token $w$ by:

$l_{w}=\operatorname*{arg\,max}_{l}P(v\in\mathcal{W}_{l}|s+T(w)).$ (1)

For the example above ($s=$ I will visit Munich next week;
$T(\textit{Munich})=$ Munich is a [MASK]), the top-5 predictions using the
BERT-large model are: city, success, democracy, capital, dream. The largest
probability ($0.43$) among all words is assigned to city which is among the
representative words for label LOC. Thus, Munich is labeled as a location. A
graphical depiction of the full method is shown in Figure 1.

The outlined approach raises three design questions which we address in turn:

  1. 1.

Given the input sentence, how to detect the candidate tokens to label?

  2. 2.

What constitutes a good template for the second half of the prompt?

  3. 3.

Which words to include in the list of representative words for each entity
label?

A fourth decision to make is the choice of pre-trained language model. Our
results comparing four state-of-the-art PLMs are listed in section 5.1, but we
shall first attend to the three questions listed above.

Figure 1: Overview of the proposed template method: The PLM prompt consists of the sentence and the template instantiated with the word to label. The PLM predicts the probability of [MASK] for all representative words, and the label associated with the most probable word is returned. Entity Type | Representative Words
---|---
LOC | location, city, country, region, area, province, state, town
PER | person, man, woman, boy, girl, human, someone, kid
ORG | organization, community, department, association, company, team
ORDINAL | number, digit, count, third, second
DATE | date, day, month, time, year
Table 1: Examples of representative word lists for entity types location
(LOC), person (PER), organization (ORG), Ordinal (ORDINAL), and date (DATE).

#### Identifying Named Entities.

In sequence labeling tasks, it is common that the identification of token
boundaries and the actual label of the token is performed jointly as both
decisions are often informed by the same features. Here, we perform these
steps separately. This is possible because named entities are usually realized
as proper nouns (although some NE schemes also include entities such as
numbers, date, and time expressions), licensing the use of a task-independent
part-of-speech tagger to identify candidate tokens in the input sentence
before labeling it with the template method. Part-of-speech (POS) 222We make
use of Spacy POS tagger https://spacy.io/usage/linguistic-features taggers can
identify occurrences of proper nouns (or numerals, ordinals) with a high
degree of accuracy. However, entity boundaries in case of multi-word
expressions are usually not labeled explicitly. A phrase structure parser
could be employed to determine the boundaries of multi-word named entities,
but we found simply treating consecutive proper nouns as a single entity to be
a reasonable heuristic in our experiments.

#### Template Selection.

In order to gain insights into what constitutes a good template we have
experimented with a number of variants. Overall, we found that most templates
performed similarly, except where we intentionally tested the limits of the
format. These experiments are detailed in Section 5.2. Generally speaking, a
template should be grammatical and natural. Simple variants work better than
overly complicated templates. The simple copula [TOKEN] is a [MASK] is a good
recommendation as it performed well in all of our tested conditions.

#### Representative Words.

If some examples of the target domain are available at training time, the
representative word lists can be derived from predictions over this data. That
is, the representative words for each entity type can be taken as the most
probable mask fillers given the respective prompts. Alternatively, in a zero-
shot setting or where otherwise appropriate, a set of words can be provided by
a domain expert. For the experiments in the next section, this is the strategy
we followed. Of course, it is possible to combine both methods, with an expert
choosing a suitable subset from words with the highest probability in the
automatic setting. Additionally, we can use static word embeddings like GloVe
to extract a list of representative for each category based on word
similarity.

###  3.2 Few-shot Hybrid Method

The method described thus far can be used for zero-shot classification as it
does not require any training. In a few-shot setting, however, we can improve
the performance of the system by fine-tuning the PLM using the labeled data in
the target domain.

A further performance gain can be made by combining our method with a standard
supervised classifier in a simple two-fold ensemble. Based on a selection
threshold $p_{h}$, we label the token according to the prediction of the base
method if the probability of the predicted label is higher than the threshold
$p_{h}$:

$\max_{l}P(v\in\mathcal{W}_{l}|s+T(w))>p_{h},$ (2)

otherwise we relay the output of the supervised classifier. The threshold
$p_{h}$ is a hyper-parameter that can be tuned on the training examples from
the target domain.

##  4 Data

We consider three popular NER datasets (CoNLL03, OntoNotes 5.0 and i2b2) from
different domains and with different label sets.

The CoNLL03 data [22] consists of documents from the English news domain that
have been annotated with four named entity types: personal name (PER),
organization (ORG), location (LOC), and miscellaneous entity (MISC).

The OntoNotes 5.0 dataset [14] consist of NER in three languages (English,
Chinese and Arabic). In this work we make use of the English dataset with six
annotated domains: broadcast news (BN), broadcast conversation (BC), magazines
(MZ), telephone conversation (TC), and web data (WB). The annotation scheme of
OntoNotes 5.0 distinguishes between $18$ entity types, making it a more
challenging task than CoNLL03.

The third dataset, i2b2 2014 [21], is a BioNLP dataset commonly used for de-
identification tasks. The dataset contains $25$ entity types from seven
Private Health Information (PHI) categories: Name, Profession, Location, Age,
Date, Contact, and Ids.

In our few-shot experiments, $1$, $5$, or $100$ data points are sampled per
label from each training set, depending on the setting. In the zero-shot case,
no training is used.

##  5 Experiments

| BERT |  RoBERTa | GPT-2 | XLNet
---|---|---|---|---
LOC | 69% | 65% | 42% | 58%
PER | 80% | 73% | 45% | 57%
ORG | 42% | 43% | 13% | 34%
Micro-Avg. | 60% | 59% | 36% | 49%

Table 2: F1-scores for four PLMs on the CoNLL03 dataset in the zero-shot
setting.

###  5.1 Comparing Language Models

We study the role of the choice of PLM in our approach by comparing four
state-of-the-art pre-trained language models: BERT [2], RoBERTa [11], GPT-2
[15] and XLNET [27]. BERT and RoBERTa are trained to predict masked tokens
that are randomly corrupted in the training sentence. GPT-2 is based on
autoregressive language modeling, but it is less efficient predicting masked
tokens. XLNET attempts to address the limitations of BERT for next-word
prediction (i.e autoregressive LM) while retaining good performance on natural
language understanding tasks.

Table 2 compares the four PLMs on the CoNLL03 dataset for the zero-shot
setting as described above. In all of these experiments, the template [TOKEN]
is a [MASK] and the representative word lists from Table 1 were used. We
observe that BERT and RoBERTa outperform the other two LMs. Interestingly,
GPT-2 does not perform well in this setting with an average F1 score of just
$36\%$.

###  5.2 Choice of Template

ID | Template
---|---
$T_{1}$ | [TOKEN] is a [MASK].
$T_{2}$ | [TOKEN] was a [MASK].
$T_{3}$ | [TOKEN] would be a [MASK].
$T_{4}$ | [TOKEN] a [MASK].
$T_{5}$ | [TOKEN] [MASK].
$T_{6}$ | [TOKEN] is an example of a [MASK].
$T_{7}$ | [TOKEN] is an instance of a [MASK].
$T_{8}$ | [TOKEN] denotes a [MASK].
$T_{9}$ | [TOKEN] is well-known to be a [MASK].
$T_{10}$ | Many people consider [TOKEN] to be a [MASK].
$T_{11}$ | [TOKEN] is a common [MASK] known to many people.
$T_{12}$ | There are many [MASK]s but [TOKEN] stands out nevertheless.
$T_{13}$ | A [MASK] like [TOKEN] is often mentioned in conversations.
$T_{14}$ | A [MASK] like [TOKEN].
$T_{15}$ | This [MASK], [TOKEN], is worth discussing.

Table 3: List of templates used in the comparative experiments. Aspects
considered include tense, mood, expression length and complexity, verb choice,
grammaticality, and TOKEN/MASK order, in different forms.

A second variable in the setup is the choice of the template used in the
prompt. We compare 15 different templates in the zero-shot setting, listed in
Table 3. We examined these templates on the CoNLL03 and OntoNotes datasets
using location, person and organization as entity classes. Tables 4 and 5
present the results of this experiment.

$T_{1}$ is a straight-forward default and copula template that directly
identifies the token with the mask. $T_{2}$ template differs from $T_{1}$ only
in the verb. We added it to study the influence of tense on the prediction
quality. In our experiments, it lead to slightly worse results, but it might
be useful e.g. for historical texts. $T_{3}$ is similar to the above but uses
a modal auxiliary. We further experimented with stripping down a template to
the minimum useful form in $T_{4}$. This template is ungrammatical, however,
and does not perform well. $T_{5}$ is the smallest template possible modulo
word order. It is the worst performing template in our experiments, especially
failing to predict the PER class. The next four templates $T_{6}-T_{9}$ are
further variations of $T_{1}$ that replace the verb to be with longer
constructions.

In all previous templates, the token to label appears as the first word. In
$T_{10}$, we test whether a longer left-hand side context is beneficial to the
PLM prediction. With $T_{11}$, we test the effect of extending the right-hand
context. It does not produce the same performance gain as $T_{10}$, though.
$T_{12}$ extends both the left-hand and the right-hand side context
simultaneously, but also presents token and mask in a contrasting relation. It
seems that the language model has more difficulties associating the mask and
the token with each other in this template, as the performance drops
considerably for CoNLL03. $T_{13}$ also reverses the order of mask and token
but outperforms $T_{12}$ template in the case of CoNLL03.

Are the additional filler words responsible for the good performance of
$T_{13}$, or is it the way the relation between mask and token are expressed
using the word like? $T_{14}$ reduced template suggests the latter, as it
performs even slightly better than $T_{13}$. Finally $T_{15}$ is similar in
spirit to ${T_{5}}$ in that it tests whether proximity of mask and token are
important, only with the order of the two reversed, and some context words
added. It performs better than ${T_{5}}$ but not en par with most other
templates.

The key message of these experiments is that our approach is robust against
the details of the template format as long as it is not too artificial.
Indeed, we do not observe a high variation in the performance of the model
when using different natural sounding templates.

| $T_{1}$ | $T_{2}$ | $T_{3}$ | $T_{4}$ | $T_{5}$ | $T_{6}$ | $T_{7}$ | $T_{8}$ | $T_{9}$ | $T_{10}$ | $T_{11}$ | $T_{12}$ | $T_{13}$ | $T_{14}$ | $T_{15}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
LOC | 69% | 60% | 62% | 52% | 46% | 66% | 63% | 60% | 67% | 69% | 61% | 57% | 73% | 70% | 60%
PER | 80% | 72% | 73% | 65% | 7% | 81% | 82% | 71% | 76% | 82% | 83% | 15% | 76% | 81% | 57%
ORG | 42% | 48% | 51% | 35% | 35% | 44% | 39% | 41% | 47% | 44% | 41% | 36% | 48% | 54% | 34%
Micro-Avg. | 60% | 57% | 57% | 47% | 31% | 59% | 57% | 55% | 60% | 62% | 59% | 36% | 62% | 63% | 49%

Table 4: Comparing different templates $T_{1}$–$T_{15}$ and their impact on
the F1-score in the zero-shot setting on CoNLL03. The results suggest that the
performance of a template depends mainly on its naturalness.

| $T_{1}$ | $T_{2}$ | $T_{3}$ | $T_{4}$ | $T_{5}$ | $T_{6}$ | $T_{7}$ | $T_{8}$ | $T_{9}$ | $T_{10}$ | $T_{11}$ | $T_{12}$ | $T_{13}$ | $T_{14}$ | $T_{15}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
LOC | 71% | 72% | 71% | 64% | 50% | 69% | 67% | 72% | 67% | 67% | 64% | 68% | 67% | 68% | 63%
PER | 49% | 45% | 43% | 47% | 24% | 51% | 51% | 44% | 48% | 49% | 51% | 43% | 45% | 43% | 47%
ORG | 47% | 45% | 44% | 41% | 36% | 43% | 42% | 42% | 46% | 47% | 47% | 45% | 44% | 45% | 42%
Micro-Avg. | 57% | 55% | 54% | 52% | 38% | 56% | 54% | 54% | 55% | 56% | 56% | 54% | 53% | 54% | 50%

Table 5: Impact of template choice in the zero-shot setting for OntoNotes

###  5.3 Domain Adaptation

In this section, we assess the extent to which our prompt-based approach can
improve the performance of available baseline methods for NER in a domain
adaptation setting. Specifically, we are interested in a setting where
knowledge of the source domain should be transferred to a target domain for
which the number of available training samples is very limited. This is of
particular importance as annotating a new large corpus is often prohibitive.

We consider three baselines: in the AGG baseline, we merge the training data
of the source and target domain and train a NER classifier on the resulting
aggregated dataset. In the Fine-tuning baseline, we first train the model on
the source domain and then fine-tune it on the training set of the target
domain. Both of these approaches have been shown to reach results competitive
with other state-of-the-art methods [10]. In both cases, a BERT-large cased
pre-trained LM followed by a linear layer is used as the NER classifier.

The third baseline is StructShot, introduced by [26]. It is based on a feature
extractor module obtained by training a supervised NER model on the source
domain. The generated contextual representations are used at inference time by
a nearest neighbor token classifier. Additionally, label dependencies are
captured by employing a viterbi decoder of a conditional random field layer
and estimating the tag transitions using source domain.

Method | BC | BN | MZ | NW | TC | WB | AVG
---|---|---|---|---|---|---|---
AGG | 46.3 | 47.9 | 46.9 | 52.7 | 51.7 | 43.8 | 48.2
AGG+$T$ | 61.1 | 66.2 | 62.1 | 71.0 | 73.3 | 47.4 | 63.5
Fine-Tuning | 66.7 | 71.2 | 69.3 | 74.1 | 65.2 | 49.1 | 65.9
Fine-Tuning+$T$ | $\bm{72.0}$ | $72.1$ | 74.7 | $\bm{74.3}$ | 77.0 | 49.1 | 69.9
StructShot | 63.2 | 70.6 | 71.6 | 71.8 | 67.3 | 51.2 | 65.9
StructShot +$T$ | 70.3 | $\bm{72.8}$ | $\bm{75.5}$ | 73.5 | $\bm{78.4}$ | $\bm{51.9}$ | $\bm{70.4}$
In-domain | 91.6 | 94.3 | 94.1 | 93.2 | 76.9 | 67.1 | 86.2

Table 6: Domain adaptation for NER: F1 score of using the OntoNotes and i2b2
datasets. Combining our prompt-based method $T$ with the Fine-Tuning approach
achieves the best performance. For all few-shot methods, we use K=100 samples
of target domain training set. In contrast, the In-domain method uses all
available training samples and serves as a topline.

In-domain | AGG |  AGG+$T$ | Fine-Tuning |  Fine-Tuning+$T$ | StructShot |  StructShot +$T$
---|---|---|---|---|---|---
94.8 | 53.5 | 57.2 | 62.3 | $\bm{65.1}$ | 60.2 | 64.2

Table 7: Results of domain adaptation for NER using OntoNotes as the source
domain and i2b2 as the target domain.

| one-shot | five-shot
---|---|---
| Group A | Group B | Group C | Group A | Group B | Group C
Fine-Tuning | $7.4\pm 2.4$ | $8.9\pm 4.3$ | $9.1\pm 2.0$ | $13.1\pm 1.8$ | $21.4\pm 7.3$ | $20.8\pm 4.2$
Fine-Tuning+$T$ | $8.9\pm 2.1$ | $11.8\pm 3.9$ | $13.6\pm 1.7$ | $14.9\pm 1.6$ | $20.7\pm 6.5$ | $22.5\pm 2.6$
StructShot | $26.7\pm 4.8$ | $33.2\pm 15.6$ | $23.0\pm 11.4$ | $\bm{47.8}\pm 3.5$ | $56.5\pm 9.3$ | $53.4\pm 3.2$
StructShot +$T$ | $\bm{27.3}\pm 4.2$ | $\bm{33.6}\pm 14.1$ | $\bm{26.5}\pm 8.7$ | $46.0\pm 2.9$ | $\bm{57.7}\pm 7.8$ | $\bm{55.1}\pm 2.1$

Table 8: Results of F1 scores on one-shot NER for different target labels.

Following [24], we take one domain of the dataset as the target domain and the
other domains as the source domain. We randomly select $K=100$ sample
sentences from the target domain as our target training set. For selecting
source and target labels, heterogeneous setup is adopted in which we choose
PERSON, ORG, PRODUCT as source labels and PERSON, ORG, PRODUCT, LOC, LANGUAGE,
ORDINAL as target labels. This discrepancy between target and source labels
makes transfer learning more challenging.

Table 6 depicts the results of our experiments on the various OntoNotes
datasets averaged over five runs each. The table compares the performance of
the baseline models with that of our hybrid approach. It also shows the
results of an in-domain method, where we use all the training samples of
target domain for training a fully supervised classifier. As is evident from
this table, our prompt-based approach boosts the performance of all baseline
models by a considerable margin. In our next experiment, we are interested in
the impact of a greater discrepancy between source and target domain. We
therefore take the OntoNotes 5.0 dataset as the source domain and the i2b2
2014 dataset as the target domain.

We use PERSON, ORG, DATE, LOC as source labels and PERSON, ORG, DATE, LOC,
PROFESSION as target labels. Table 7 shows the results of our experiments. We
observe the same pattern as before, i.e., combining our method with supervised
baselines achieves the best performance. Lastly, we examine the role of tags
on the performance of our method. To do so, we follow the same strategy as
[26] and split the entity categories of the OntoNotes into three non-
overlapping groups:

  * •

Group A: ORG, NORP, ORDINAL, WORK OF ART, QUANTITY, LAW

  * •

Group B: GPE, CARDINAL, PERCENT, TIME, EVENT, LANGUAGE

  * •

Group C: PERSON, DATE, MONEY, LOC, FAC, PRODUCT

When we pick a group, e.g. A, as the target group, the corresponding tags are
replaced with the O-tag in the training data. Thus, the model is trained only
on source groups B and C. At inference time, we evaluate the model on the test
set which contains only target labels (A). The results of this experiments are
shown in Tables 8 for the one-shot and $5$-shot setting. We again observe the
improvement of baseline models by integrating them into template approach. The
amount of performance gain depends on the target group, of course. In
particular, we get a large amount of improvement for group C of tags around
$3.5$ in one-shot and $1.7$ in the five-shot setting.

##  6 Conclusion and Future Work

We proposed a novel, lightweight approach to NER for zero- and few-shot
settings, using pre-trained language models to fill in cloze-style prompts. It
is based on extracting information available in PLMs and utilizes it to labels
named entity instances identified by a domain-independent POS tagger. Results
show that masked language models have a better performance in this setting
compared with auto-regressive language models. We explored a wide range of
possible prompts with different datasets. We observed that the proposed method
is robust against contextual details of prompts. This is of practical
significance in the low-resource setting where there is not enough data to
tune the model. Our method is simple, general and can be used to boost the
performance of available domain adaptation baselines. We also propose a hybrid
approach that can easily combine the template method with any other
supervised/unsupervised classifier, and demonstrated the effectiveness of this
hybrid approach empirically.

Further work could investigate the possibility of fine-tuning templates while
having access only to a few training samples. It would be also interesting to
explore more sophisticated approaches for combining the predictions of the
template model and other few-shot NER baselines. Two aspects of our approach
currently require manual intervention, the template and the representative
word lists. Finding ways to determine these fully automatically is another
interesting direction to explore. As mentioned before, one way to extract
representative words is by making use of word embeddings like GloVe. Indeed,
we found that almost all subsets of our representative words perform fairly
well in practice. We leave automatically extraction of representative words
and its evaluation to future work.

##  7 Acknowledgments

This work was funded by the EU-funded Horizon 2020 projects: COMPRISE
(http://www.compriseh2020.eu/) under grant agreement No. 3081705 and ROXANNE
under grant number 833635.

## References

  * [1] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J.D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., Amodei, D.: Language models are few-shot learners. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) In NeurIPS. vol. 33, pp. 1877–1901 (2020)
  * [2] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: BERT: Pre-training of deep bidirectional transformers for language understanding. In: NAACL-HLT. pp. 4171–4186 (Jun 2019)
  * [3] Finn, C., Abbeel, P., Levine, S.: Model-agnostic meta-learning for fast adaptation of deep networks. In: ICML (2017)
  * [4] Fritzler, A., Logacheva, V., Kretov, M.: Few-shot classification in named entity recognition task. In: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing. p. 993–1000. SAC ’19 (2019)
  * [5] Gao, T., Fisch, A., Chen, D.: Making pre-trained language models better few-shot learners. arXiv:2012.15723 (31 December 2020)
  * [6] Gao, T., Fisch, A., Chen, D.: Making pre-trained language models better few-shot learners (2020)
  * [7] Hou, Y., Che, W., Lai, Y., Zhou, Z., Liu, Y., Liu, H., Liu, T.: Few-shot slot tagging with collapsed dependency transfer and label-enhanced task-adaptive projection network. In: ACL. pp. 1381–1393. Online (Jul 2020)
  * [8] Huang, J., Li, C., Subudhi, K., Jose, D., Balakrishnan, S., Chen, W., Peng, B., Gao, J., Han, J.: Few-shot named entity recognition: A comprehensive study. ArXiv abs/2012.14978 (2020)
  * [9] Krone, J., Zhang, Y., Diab, M.: Learning to classify intents and slot labels given a handful of examples. In: Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI. pp. 96–108. Association for Computational Linguistics, Online (Jul 2020)
  * [10] Li, J., Shang, S., Shao, L.: Metaner: Named entity recognition with meta-learning. In: Proceedings of The Web Conference 2020. p. 429–440. WWW ’20, Association for Computing Machinery, New York, NY, USA (2020)
  * [11] Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., Stoyanov, V.: Roberta: A robustly optimized bert pretraining approach. ArXiv abs/1907.11692 (2019)
  * [12] Peters, M.E., Neumann, M., Iyyer, M., Gardner, M., Clark, C., Lee, K., Zettlemoyer, L.: Deep contextualized word representations. In: NAACL-HLT. pp. 2227–2237 (Jun 2018)
  * [13] Petroni, F., Rocktäschel, T., Lewis, P., Bakhtin, A., Wu, Y., Miller, A.H., Riedel, S.: Language models as knowledge bases? (2019)
  * [14] Pradhan, S., Moschitti, A., Xue, N., Ng, H.T., Björkelund, A., Uryupina, O., Zhang, Y., Zhong, Z.: Towards robust linguistic analysis using OntoNotes. In: Proceedings of the Seventeenth Conference on Computational Natural Language Learning. pp. 143–152. Association for Computational Linguistics, Sofia, Bulgaria (Aug 2013)
  * [15] Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I.: Language models are unsupervised multitask learners. https://d4mucfpksywv.cloudfront.net/better-language-models/language_models_are_unsupervised_multitask_learners.pdf (2019)
  * [16] Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., Liu, P.J.: Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res. 21, 140:1–140:67 (2020)
  * [17] Ravi, S., Larochelle, H.: Optimization as a model for few-shot learning. In: ICLR (2017)
  * [18] Schick, T., Schütze, H.: Exploiting cloze questions for few shot text classification and natural language inference. In: EACL. online (19–23 April 2021)
  * [19] Shin, T., Razeghi, Y., Logan IV, R.L., Wallace, E., Singh, S.: AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts. In: EMNLP. pp. 4222–4235. Online (Nov 2020)
  * [20] Snell, J., Swersky, K., Zemel, R.: Prototypical networks for few-shot learning. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) NeurIPS. vol. 30, pp. 4077–4087. Curran Associates, Inc. (2017)
  * [21] Stubbs, A., Kotfila, C., Uzuner, O.: Automated systems for the de-identification of longitudinal clinical narratives. J. of Biomedical Informatics 58(S), S11–S19 (Dec 2015)
  * [22] Tjong Kim Sang, E.F., De Meulder, F.: Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition. In: Proceedings of the 7th CoNLL at HLT-NAACL 2003. pp. 142–147 (2003)
  * [23] Wallace, E., Feng, S., Kandpal, N., Gardner, M., Singh, S.: Universal adversarial triggers for attacking and analyzing nlp. In: EMNLP/IJCNLP (2019)
  * [24] Wang, J., Kulkarni, M., Preotiuc-Pietro, D.: Multi-domain named entity recognition with genre-aware and agnostic inference. In: ACL. pp. 8476–8488. Online (Jul 2020)
  * [25] Yamada, I., Asai, A., Shindo, H., Takeda, H., Matsumoto, Y.: LUKE: Deep contextualized entity representations with entity-aware self-attention. In: EMNLP. pp. 6442–6454. Online (Nov 2020)
  * [26] Yang, Y., Katiyar, A.: Simple and effective few-shot named entity recognition with structured nearest neighbor learning. In: EMNLP. pp. 6365–6375. Online (Nov 2020)
  * [27] Yang, Z., Dai, Z., Yang, Y., Carbonell, J., Salakhutdinov, R.R., Le, Q.V.: Xlnet: Generalized autoregressive pretraining for language understanding. In: In NeurIPS. vol. 32, pp. 5753–5763 (2019)


11institutetext:  IBISC, Univ Evry, Universite Paris-Saclay, 91025, Evry,
France
11email<EMAIL_ADDRESS>22institutetext: CEA, DAM,
DIF, F-91297 Arpajon, France
22email<EMAIL_ADDRESS>33institutetext: LIHPC - Laboratoire en
Informatique Haute Performance pour le Calcul et la simulation - DAM Île-de-
France, University of Paris-Saclay

# A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with
Bounded Tree-width

Eric Angel 11 Sébastien Morais 2233 Damien Regnault 11

###### Abstract

In this paper we study a scheduling problem arising from executing numerical
simulations on HPC architectures. With a constant number of parallel machines,
the objective is to minimize the makespan under memory constraints for the
machines. Those constraints come from a neighborhood graph $G$ for the jobs.
Motivated by a previous result on graphs $G$ with bounded path-width, our
focus is on the case when the neighborhood graph $G$ has bounded tree-width.
Our result is a bi-criteria fully polynomial time approximation algorithm
based on a dynamic programming algorithm. It allows to find a solution within
a factor of $1+\epsilon$ of the optimal makespan, where the memory capacity of
the machines may be exceeded by a factor at most $1+\epsilon$. This result
relies on the use of a nice tree decomposition of $G$ and its traversal in a
specific way which may be useful on its own. The case of unrelated machines is
also tractable with minor modifications.

##  1 Introduction

In this paper, we study the scheduling problem $Pk|G,mem|C_{max}$ previously
introduced in [1] where the number of machines is a fixed constant. This
problem is motivated by running distributed numerical simulations based on
high-ordered finite elements or volume methods [5, 12]. Such approaches
require the geometric domain of study to be discretized into basic elements,
called cells, which form a mesh. Each cell has a computational cost, and a
memory weight depending on the amount of data (i.e. density, pressure, …)
stored on that cell. Moreover, performing the computation of a cell requires,
in addition to its data, data located in its neighborhood111The neighborhood
is most of the time topologically defined (cells sharing an edge or a face)..
For a distributed simulation, the problem is to assign all the computations to
processing units with bounded memory capacities, while minimizing the
makespan. As an illustration of the previous notions, let us consider Figure 1
where a mesh and its associated computations are assigned onto 3 processing
units. Each color corresponds to a processing unit and the total amount of
memory needed by each processing unit is not limited to the colored cells but
extends to some adjacent cells. An exploded view of the mesh is pictured in
Figure 1, where we consider an edge-based adjacency relationship and where the
memory needed by each processing unit is equal to both colored and white
cells. In practice, efficient partitioning tools such as Scotch [18], MeTiS
[19], Zoltan [20] or PaToH [17] are used. However, the solutions returned by
these tools may not respect the memory capacities of the processing units
[21].

Figure 1: In ($a$), a 2D mesh and its computations are assigned onto 3
processing units. In ($b$), an exploded view of the assignment with an edge-
based adjacency relationship.

Formally, the scheduling problem under memory constraints is defined as
follows. We have a set of $n$ jobs $J$, and each job $j\in J$ requires
$\operatorname{\it p}_{j}\in\mathbb{N}$ units of time to be executed
(computation time) and an amount $\operatorname{\it m}_{j}\in\mathbb{N}$ of
memory. Jobs have to be assigned among a fixed number $k$ of identical
machines, each machine $l$ having a memory capacity $M_{l}\in\mathbb{N}$, for
$l=1,\ldots,k$. Additionally we have an undirected graph $G(J,E)$, which we
refer to as the neighborhood graph. Two jobs $j\in J$ and $j^{\prime}\in J$
are said to be adjacent if there is an edge $(j,j^{\prime})\in E$ in $G$.
Moreover, each job $j$ requires data from its set of adjacent jobs, denoted by
$\mathcal{N}(j):=\\{j^{\prime}\in J\,|\,(j,j^{\prime})\in E\\}$. For a subset
of jobs $J^{\prime}\subseteq J$, we note $\operatorname{{\cal
N}}(J^{\prime}):=\cup_{j\in J^{\prime}}\operatorname{{\cal N}}(j)\setminus
J^{\prime}$ and denote $\operatorname{{\cal
N}}[J^{\prime}]:=\operatorname{{\cal N}}(J^{\prime})\cup J^{\prime}$. When a
subset of jobs $J^{\prime}\subseteq J$ is scheduled on a machine, this machine
needs to allocate an amount of memory equal to $\sum_{j\in{\cal
N}[J^{\prime}]}\operatorname{\it m}_{j}$, while its processing time is
$\sum_{j\in J^{\prime}}\operatorname{\it p}_{j}$. The objective is to assign
each job of $J$ onto exactly a machine, such that the makespan (the maximum
processing time over all machines) is minimized and ensuring that the amount
of memory allocated by each machine is smaller than or equal to its memory
capacity.

The scheduling problem under memory constraints embraces other well-known NP-
hard scheduling problems and cannot be solved in polynomial time unless P=NP.
Thus, one could be interested in developping approximation algorithms. An
$\alpha$-approximation algorithm (for some $\alpha\geq 1$) for a minimization
problem is a polynomial-time algorithm that produces, for any given problem
instance $I$, a solution whose value is at most $\alpha$ times the optimum
value. In particular, a fully polynomial-time approximation scheme (FPTAS) is
a family of (1+$\epsilon$)-approximation algorithms for all $\epsilon>0$ whose
time complexity is polynomial in both the input size and $1/\epsilon$.
Considering the scheduling problem under memory constraints, one could wonder
if approximation algorithms can be obtained when the memory constraints are
relaxed. For $\alpha\geq 1$ and $\beta\geq 1$, an $(\alpha,\beta)$ (bi-
criteria) approximation algorithm returns a schedule with objective value at
most $\alpha C$ and with memory load at most $\beta M$, where $C$ and $M$,
respectively, are the maximum computation time and the memory load of an
optimal schedule with respect to the makespan. Following the terminology of
[22], a bi-FPTAS for the scheduling problem under memory constraints is a
FPTAS which is a bicriteria $(1+\epsilon,1+\epsilon)$ approximation algorithm.

###  1.1 Related problems

The problem $Rk|G,mem|C_{max}$ contains other well-known NP-hard scheduling
problems. When $\operatorname{\it m}_{j}=0$ for each job $j$, the problem
$Rk|G,mem|C_{max}$ becomes the scheduling problem $Rk||C_{max}$ for which
several approximations algorithms exist [6, 11, 15]. When the neighborhood
graph has no edges, and the memory is bounded on each machine, and
$\operatorname{\it m}_{j}=1$ for each job $j$, we get the so-called Scheduling
Machines with Capacity Constraints problem (SMCC). In this problem, each
machine can process at most a fixed number of jobs. Zhang et al. [4] gave a
$3$-approximation algorithm by using the iterative rounding method. Saha and
Srinivasan [14] gave a $2$-approximation in a more general scheduling setting,
i.e. Scheduling Unrelated Machines with Capacity Constraints. Lately, Keller
and Kotov [8] gave a $1.5$-approximation algorithm. Chen et al. established an
EPTAS [3] for this problem and, for the special case of two machines,
Woeginger designed a FPTAS [16].

###  1.2 Main Contribution

As the scheduling problem under memory constraints is a generalization of
those well-known scheduling problems, a reasonable question is to know whether
we can get approximation algorithms, which could depend on some parameters of
the neighborhood graph, when the number of machines is a fixed constant. We
answered this question in a previous paper [1] by providing a fixed-parameter
tractable (FPT) algorithm with respect to the path-width of the neighborhood
graph, which returns a solution within a ratio of $(1+\varepsilon)$ for both
the optimum makespan and the memory capacity constraints (assuming that there
exists at least one feasible solution). In this paper we extend this result by
providing a bi-FPTAS for graphs with tree-width bounded by a constant. Unlike
the FPT algorithm which relies on the numbering of the vertices of the
neighborhood graph, the bi-FPTAS takes advantage of a nice tree decomposition
of the neighborhood graph and of its traversal in a particular way to bound
the algorithm complexity.

###  1.3 Outline of the Paper

We start by briefly recalling in Section 2 the definitions of different
notions useful in the sequel. We then provide in Section 3 an algorithm that
computes all the solutions to this problem. This algorithm consists of three
steps: build a nice tree decomposition of $G(J,E)$; compute a layout $L$
defining a bottom-up traversal of the nice tree decomposition; and use a
dynamic programming algorithm traversing the nice tree decomposition following
$L$. Since the time complexity of this algorithm is not polynomial in the
input size, we apply the Trimming-of-the-State-Space technique [7] in Section
4 obtaining a bi-criteria approximation algorithm for graphs with tree-width
bounded by a constant. Finally, we give some concluding remarks in Section 5.

##  2 Definitions

Throughout this paper we consider simple, finite undirected graphs. Let us
start by defining the notions of tree decomposition, tree-width and nice tree
decomposition. The notions of tree decomposition and tree-width were initially
introduced in the framework of graph minor theory [13]. For a graph $G(J,E)$,
let $J(G):=J$ be its vertices and $E(G):=E$ be its edges. A tree decomposition
for $G$ is a pair $(T,X)$, where $T:=(J(T),E(T))$ is a tree, and
$X:=(X_{u})_{u\in J(T)}$ is a family of subsets of $J$ satisfying the
following conditions:

  1. 1.

For each $j\in J(G)$ there is at least one $u\in J(T)$ such that $j\in X_{u}$.

  2. 2.

For each $\\{j,j^{\prime}\\}\in E(G)$ there is at least one $u\in J(T)$ such
that $j$ and $j^{\prime}$ are in $X_{u}$.

  3. 3.

For each $j\in J(G)$, the set of vertices $u\in J(T)$ such that $j\in X_{u}$
induces a subtree of $T$.

To distinguish between vertices of $G$ and $T$, the latter are called nodes.
The width of a tree decomposition is $\max(|X_{u}|-1:u\in J(T))$ and the tree-
width of $G$, noted $tw(G)$, is the minimum width over all tree decompositions
of $G$. A graph $G(J,E)$ is illustrated on Figure 2(a) and a tree
decomposition of this graph is illustrated on Figure 2(b).

(a) A graph $G(J,E)$.

(b) A tree decomposition $(T,X)$ of the graph $G(J,E)$.

Figure 2: Example of a graph $G(J,E)$ in (a) and a tree decomposition $(T,X)$
of this graph where $X$ is composed of the sets $X_{1}=\\{j_{1},j_{4}\\}$,
$X_{2}=\\{j_{1},j_{2},j_{4}\\}$, $X_{3}=\\{j_{1},j_{3},j_{4}\\}$,
$X_{4}=\\{j_{2},j_{5}\\}$ in (b).

Choosing an arbitrary node $r\in J(T)$ as root, we can make a rooted tree
decomposition out of $(T,X)$ with natural parent-child and ancestor-descendant
relations. A node without children is called a leaf.

A rooted tree decomposition $(T,X)$ with root $r$ is called nice if every node
$u\in J(T)$ is of one of the following types:

  * •

Leaf: node $u$ is a leaf of $T$ and $|X_{u}|=1$.

  * •

Introduce: node $u$ has only one child $c$ and there is a vertex $j\in J(G)$
such that $X_{u}=X_{c}\cup\\{j\\}$.

  * •

Forget: node $u$ has only one child $c$ and there is a vertex $j\in J(G)$ such
that $X_{c}=X_{u}\cup\\{j\\}$.

  * •

Join: node $u$ has only two children $l$ and $r$ such that
$X_{u}=X_{l}=X_{r}$.

In Figure 3 we present a nice tree decomposition of $G(J,E)$ illustrated on
Figure 2(a)

Figure 3: Example of a nice tree decomposition of the graph $G(J,E)$ with
width $tw(G)=2$ where the node types are written in grey.

Note that a vertex of $J(G)$ can be forgotten at most once in a node of
$J(T)$. Otherwise, it would conflict with the third condition listed in the
definition of a tree decomposition. We leverage this property later in the
article.

There is an alternative definition to the nice tree decomposition where the
root $r$ and all leaves $u$ of $T$ are such that $X_{r}$ = $X_{u}$ =
$\emptyset$. But one can switch from one of these decompositions to the other
in a trivial way.

When $G$ is a graph with $tw(G)=h$, where $h$ is any fixed constant, we can
compute a tree decomposition of $G$ in linear time with tree-width at most $h$
[2]. Given a tree decomposition $(T,X)$ of $G(J,E)$ of constant width $h\geq
1$, there is an algorithm that converts it into a nice tree decomposition
$(T^{\prime},X^{\prime})$ with the same width $h$ and with at most $4n$ nodes,
where $n=|J(G)|$, in $O(n)$ times (Lemma 13.1.3 in [9]). In the rest of the
article, we will consider a nice tree decomposition obtained in this way.

Now, let us introduce the notion of layout of a nice tree decomposition
$(T,X)$, which is simply a one-to-one mapping
$L:J(T)\rightarrow\\{1,\ldots,|J(T)|\\}$. We say that a layout $L$ defines a
bottom-up traversal of a nice tree decomposition $(T,X)$ if for any edge
$\\{u,v\\}\in E(T)$ such that $v$ is a child of $u$ one has $L(v)<L(u)$. In
that case, we say that $L$ is a bottom-up layout.

##  3 An Exact Algorithm Using Dynamic Programming

Briefly, our algorithm consists of three steps. First, we build a nice tree
decomposition $(T,X)$ of the graph $G(J,E)$ with bounded tree-width. Such a
tree decomposition can be obtained in polynomial time for graph $G$ with tree-
width bounded by a constant (see Section 2). Then, we compute a specific
layout $L$ defining a bottom-up traversal of the nice tree decomposition.
Finally, a dynamic programming algorithm passes through the nodes following
the previously defined order $L$ and computes a set $\operatorname{{\cal
S}}_{L(u)}$ of states, which encodes partial solutions for
$G_{i}=(J_{i},E_{i})$ a subgraph of $G=(J,E)$, for each node $u\in J(T)$. In
Section 3.1, we start by presenting the dynamic programming algorithm where we
detail how the set of states $\operatorname{{\cal S}}_{L(u)}$ is computed
depending on the type of node $u$. Then, in Section 3.2, we give a proof of
correctness of our dynamic programming algorithm when the nodes of the nice
tree decomposition are traversed in a bottom-up way. Eventually, we compute
the complexity of our dynamic programming algorithm when the decomposition is
traversed following the layout $L$. This layout is used to bound the
complexity of our algorithm and, being bottom-up, it is compliant with the
pre-requisite on proof of completeness.

###  3.1 The Dynamic Programming Algorithm

The presentation of the dynamic algorithm is done for two machines, but it can
be generalized to a constant number $k$ of machines, with $k>2$. The dynamic
algorithm goes through $|J(T)|$ phases. Each phase $i$, with
$i=1,\ldots,|J(T)|$, processes the node $L^{-1}(i)\in J(T)$ and produces a set
$\operatorname{{\cal S}}_{i}$ of states. In the sequel, for sake of
readability, we use the notation $Z_{i}:=X_{L^{-1}(i)}$. Each state in the
state space $\operatorname{{\cal S}}_{i}$ encodes a solution for the graph
$G_{i}=(J_{i},E_{i})$, where $J_{i}:=\cup_{o=1}^{i}Z_{o}$ with
$J_{0}=\emptyset$, and $E_{i}:=E_{i-1}\cup E_{Z_{i}}$ with $E_{0}=\emptyset$
and $E_{Z_{i}}$ the set of all edges in $E$ which have both endpoints in
$Z_{i}$.

For each phase $i$, we denote by $J_{L}(i)$ the set of vertices of $J(G)$
which have not been forgotten when going through nodes $L^{-1}(1)$ to
$L^{-1}(i)$. For convenience, we note $J_{L}(0):=\emptyset$. Formally,
$J_{L}(i):=J_{i}\setminus V_{R}(i)$, where $V_{R}(i)$ is the set of vertices
that where removed in a Forget node $o$ such that $L(o)\leq i$.

A state $s\in\operatorname{{\cal S}}_{i}$ is a vector
$[c_{1},c_{2},c_{3},c_{4},\operatorname{{\cal C}}_{i}]$ where:

  * •

$c_{1}$ (resp. $c_{2}$) is the total processing time on the first (resp.
second) machine in the constructed schedule,

  * •

$c_{3}$ (resp. $c_{4}$) is the total amount of memory required by the first
(resp. second) machine in the constructed schedule,

  * •

$\operatorname{{\cal C}}_{i}$ is an additional structure, called combinatorial
frontier. For a given solution of $G_{i}(J_{i},E_{i})$, it is defined as
$\operatorname{{\cal C}}_{i}:=(J_{L}(i),\sigma_{i},\sigma_{i}^{\prime})$ where
$\sigma_{i}:J_{L}(i)\rightarrow\\{1,2\\}$ and
$\sigma_{i}^{\prime}:J_{L}(i)\rightarrow\\{0,1\\}$ such that $\sigma_{i}(j)$
is the machine on which $j\in J_{L}(i)$ has been assigned, and
$\sigma_{i}^{\prime}(j):=1$ if the machine on which $j$ is not assigned, i.e.
machine $3-\sigma_{i}(j)$, has already memorised the data of $j$. Notice that
$J_{L}(i)\subseteq J_{i}$ and keeping into memory the combinatorial frontier
with respect to $J_{L}(i)$ rather than $J_{i}$ is a key point in our algorithm
in order to bound its complexity.

In the following, we present how to compute $\operatorname{{\cal S}}_{i}$ from
$\operatorname{{\cal S}}_{i-1}$ depending on the type of node $L^{-1}(i)$. For
that, we present how states of $\operatorname{{\cal S}}_{i}$ are obtained from
an arbitrary state $s=[c_{1},c_{2},c_{3},c_{4},\operatorname{{\cal
C}}_{i-1}]\in\operatorname{{\cal S}}_{i-1}$. When $L^{-1}(i)$ is a Leaf node
with $Z_{i}=\\{j\\}$ or an Introduce node with $j$ the vertex introduced, we
note $s_{a}$ ($a=1,2$) the state of $\operatorname{{\cal S}}_{i}$ obtained
from $s$ and resulting from the assignment of $j$ to machine $a$, and
$\operatorname{{\cal C}}_{i}^{a}$ the combinatorial frontier obtained from
$\operatorname{{\cal C}}_{i-1}$ when $j$ is assigned to machine $a$.

Leaf Let $L^{-1}(i)\in J(T)$ be a Leaf of $T$ with $Z_{i}=\\{j\\}$. For each
state of $\operatorname{{\cal S}}_{i-1}$ we add at most two states in
$\operatorname{{\cal S}}_{i}$. If $j\in J_{L}(i-1)$, it means that $j$ has
already been assigned to a machine. Therefore, there is nothing to do and
$\operatorname{{\cal S}}_{i}=\operatorname{{\cal S}}_{i-1}$. Now, let us
assume that $j\notin J_{L}(i-1)$. In this case, we must compute two new states
taking into account the assignment of $j$ to machine one or two. We have

$s_{a}=[c_{1}+\delta_{a,1}c_{j},~{}c_{2}+\delta_{a,2}c_{j},~{}c_{3}+\delta_{a,1}\operatorname{\it
m}_{j},~{}c_{4}+\delta_{a,2}\operatorname{\it m}_{j},~{}\operatorname{{\cal
C}}_{i}^{a}]$

where $\delta$ is the Kronecker function ($\delta_{i,j}=1$ if $i=j$, and
$\delta_{i,j}=0$ otherwise). Since $j\notin J_{L}(i-1)$, the new combinatorial
frontier is obtained by extending $\operatorname{{\cal C}}_{i-1}$ in adding
new information related to $j$, i.e. $\sigma_{i}(j)=a$ and
$\sigma_{i}^{\prime}(j)=0$. Note that we have $\sigma_{i}^{\prime}(j)=0$
because $j$ was not assigned before phase $i$ and $E_{Z_{i}}=\emptyset$.

Introduce Let $L^{-1}(i)\in J(T)$ be an Introduce node of $T$ and $j\in J(G)$
being the vertex introduced. Again, for each state $s$ of $\operatorname{{\cal
S}}_{i-1}$ we are going to add at most two states to $\operatorname{{\cal
S}}_{i}$ depending on $j$ assignment. However, processing an Introduce node
differs from a Leaf because we may have to consider new edges. This happens
when $E_{i}\backslash E_{i-1}\neq\emptyset$. There are two cases to consider.
The first one is when $j\in J_{L}(i-1)$. In that case, job $j$ has already
been assigned on machine $a=\sigma_{i-1}(j)$. We add a state in
$\operatorname{{\cal S}}_{i}$ for every state $s$ in $\operatorname{{\cal
S}}_{i-1}$. Let $F_{a}$ and $F_{a}^{\prime}$ be the set of edges such that

$F_{a}=\\{\\{j,j^{\prime}\\}\in E_{Z_{i}}:a\neq\sigma_{i-1}(j^{\prime})\text{
and }\sigma_{i-1}^{\prime}(j^{\prime})=0\\},$ (1)
$F_{a}^{\prime}=\\{\\{j,j^{\prime}\\}\in
E_{Z_{i}}:a\neq\sigma_{i-1}(j^{\prime})\text{ and
}\sigma_{i-1}^{\prime}(j)=0\\}.$ (2)

The set $F_{a}$ represents the new edges in $E_{Z_{i}}$ inducing additional
amount of data on machine $a$. The set $F_{a}^{\prime}$ represents the new
edges in $E_{Z_{i}}$ inducing that $\operatorname{\it m}_{j}$ must be added on
the machine not processing $j$. Note that some edges in $E_{Z_{i}}$ may have
already been considered in a previous node and that they can’t be a part of
$F_{a}$ or $F_{a}^{\prime}$. Thus, we have

$s_{a}=[c_{1},~{}c_{2},~{}c_{3}+\delta_{a,1}\alpha_{i}^{1}+\delta_{a,2}\beta_{i}^{1},~{}c_{4}+\delta_{a,2}\alpha_{i}^{2}+\delta_{a,1}\beta_{i}^{2},~{}\operatorname{{\cal
C}}_{i}^{a}]$

where $\alpha_{i}^{a}=\sum_{\\{j,j^{\prime}\\}\in F_{a}}\operatorname{\it
m}_{j^{\prime}}$ and $\beta_{i}^{a}=\operatorname{\it m}_{j}I\llbracket
F_{a}^{\prime}\neq\emptyset\rrbracket$ where $I\llbracket A\rrbracket$ is the
indicator function which returns one if condition $A$ is satisfied and zero
otherwise. Finally, the combinatorial frontier of the new state $s_{a}$ is
obtained from that of $s$ by updating, if necessary, the information of $j$
and vertices $j^{\prime}$ such that $\\{j,j^{\prime}\\}\in F_{a}$. If we have
$F_{a}^{\prime}\neq\emptyset$, it means that $j$ was not memorised by machine
$3-a$ in state $s$. However, this is no longer the case for $s_{a}$ as new
edges have been taken into account leading us to
$\sigma_{i}^{\prime}(j)=1\neq\sigma_{i-1}^{\prime}(j)$. If we have
$F_{a}\neq\emptyset$, then some vertices processed by machine $3-a$ were not
memorised by machine $a$ in state $s$. Again, this is no longer the case in
$s_{a}$ following the inclusion of new edges leading us to
$\sigma_{i}^{\prime}(j^{\prime})=1\neq\sigma_{i-1}^{\prime}(j^{\prime})$ for
every vertex $j^{\prime}$ such that $\\{j,j^{\prime}\\}\in F_{a}$.

Now, if $j\notin J_{L}(i-1)$ then we add two states in $\operatorname{{\cal
S}}_{i}$ for every state $s\in\operatorname{{\cal S}}_{i-1}$. For $a=1,2$, we
have

$\displaystyle s_{a}=[{}$ $\displaystyle c_{1}+\delta_{a,1}\operatorname{\it
p}_{j},~{}c_{2}+\delta_{a,2}\operatorname{\it p}_{j},$ $\displaystyle
c_{3}+\delta_{a,1}(\operatorname{\it
m}_{j}+\alpha_{i}^{1})+\delta_{a,2}\beta_{i}^{1},~{}c_{4}+\delta_{a,2}(\operatorname{\it
m}_{j}+\alpha_{i}^{2})+\delta_{a,1}\beta_{i}^{2},~{}\operatorname{{\cal
C}}_{i}^{a}].$

The way to obtain the first four coordinates of each new state in
$\operatorname{{\cal S}}_{i}$ is similar to the case where $j\in J_{L}(i-1)$
except that we have to add $\operatorname{\it p}_{j}$ and $\operatorname{\it
m}_{j}$ on the machine processing $j$. In the case of the combinatorial
frontier, updates defined for $j\in J_{L}(i-1)$ also apply and we have to add
information related to $j$ since it was unknown so far. The added data is
$\sigma_{i}(j)=a$ and $\sigma_{i}^{\prime}(j)=I\llbracket\exists j^{\prime}\in
Z_{i}:\\{j,j^{\prime}\\}\in E_{Z_{i}}\text{ and }\sigma_{i-1}(j^{\prime})\neq
a\rrbracket$.

Forget Let $L^{-1}(i)\in J(T)$ be a Forget node of $T$ and $j\in J(G)$ being
the vertex forgotten. This type of node is easier to handle than previous ones
since we don’t have to deal with new vertex or edges. The only thing to do is
to withdraw $j$ from the combination frontier. Thus, for each state
$s\in\operatorname{{\cal S}}_{i-1}$ we add a state
$s^{\prime}\in\operatorname{{\cal S}}_{i}$ where the combinatorial frontier of
$s^{\prime}$ is equal to that of $s$ from which information on $j$ was
removed.

Join Let $L^{-1}(i)\in J(T)$ be a Join node of $T$. This type of node is even
simpler to deal with than the previous one. Once again, there are no new
vertex or edges to handle. Moreover, we don’t forget any vertex. For each
state $s\in\operatorname{{\cal S}}_{i-1}$ we add $s$ to $\operatorname{{\cal
S}}_{i}$. Thus, we have $\operatorname{{\cal S}}_{i}=\operatorname{{\cal
S}}_{i-1}$.

Our algorithm ends up by returning the state
$s=[c_{1},c_{2},c_{3},c_{4},\operatorname{{\cal
C}}_{|J(T)|}]\in\operatorname{{\cal S}}_{|J(T)|}$ with $c_{3}\leq M_{1}$,
$c_{4}\leq M_{2}$ and such that $\max\\{c_{1},c_{2}\\}$ is minimum.

###  3.2 Algorithm Correctness

Now, let us present the proof of correctness of our dynamic programming
algorithm when the nodes of the nice tree decomposition are traversed in
bottom-up. We will prove our algorithm correctness by maintaining the
following invariant: the states in $\operatorname{{\cal S}}_{i}$ encode all
the solutions for the graph $G_{i}=(J_{i},E_{i})$, defined at Section 3.1.

#### Initialization

Let us start with the first node encountered. Let $G_{0}=(J_{0},E_{0})$ be an
empty graph and $\operatorname{{\cal S}}_{0}$ be the set composed of the
single state $[0,0,0,0,\operatorname{{\cal C}}_{0}]$ where
$\operatorname{{\cal C}}_{0}$ does not store information. The nodes being
traversed in bottom-up, the first node encountered is a Leaf. Let $j\in J(G)$
be the vertex such that $Z_{1}=\\{j\\}$. Since $j\notin J_{L}(0)$ we have
$\operatorname{{\cal S}}_{1}=[(\operatorname{\it p}_{j},0,\operatorname{\it
m}_{j},0,\operatorname{{\cal C}}_{1}^{1}),(0,\operatorname{\it
p}_{j},0,\operatorname{\it m}_{j},\operatorname{{\cal C}}_{1}^{2})]$ where,
for $a=1,2$, $\operatorname{{\cal C}}_{1}^{a}$ is such that $\sigma_{1}(j)=a$
and $\sigma_{1}^{\prime}(j)=0$. These two states encode the assignment of $j$
on machines one and two when considering the graph $G_{1}=(J_{1},E_{1})$.
Moreover, the combinatorial frontier obtained allows us to keep in memory
potentially necessary knowledge for graphs of which $G_{1}=(J_{1},E_{1})$ is a
sub-graph. Thus the invariant is correct for the first node.

#### Maintenance

Now let us assume that the invariant holds for $L^{-1}(i-1)\in J(T)$ and let
us prove that it is still correct for $L^{-1}(i)\in J(T)$.

Leaf Let $L^{-1}(i)\in J(T)$ being a Leaf with $Z_{i}=\\{j\\}$. If $j\in
J_{L}(i-1)$ then our algorithm states that $\operatorname{{\cal
S}}_{i}=\operatorname{{\cal S}}_{i-1}$. In that case, the invariant holds
because $G_{i}=(J_{i},E_{i})$ is equal to $G_{i-1}=(J_{i-1},E_{i-1})$. Now, if
$j\notin J_{L}(i)$ then our algorithm adds two new states in
$\operatorname{{\cal S}}_{i}$ for every state in $s\in\operatorname{{\cal
S}}_{i-1}$ to take into account the assignment of $j$ to machine one and two.
Each new state is obtained by adding $\operatorname{\it p}_{j}$ and
$\operatorname{\it m}_{j}$ according to the assignment of $j$ and the
associated combinatorial frontier is obtained by extending the combinatorial
frontier of $s$ with information on $j$ assignment, i.e. $\sigma_{i}(j)=a$ and
$\sigma_{i}^{\prime}(j)=0$. Since we are dealing with a Leaf and $j\notin
J_{L}(i)$ we have $G_{i}=(V_{i-1}\cup\\{j\\},E_{i-1})$. Therefore, the
invariant holds.

Introduce Let $L^{-1}(i)\in J(T)$ being an Introduce node with $j\in J(G)$
being the vertex introduced. If $j\in J_{L}(i-1)$ then our algorithm adds one
new state in $\operatorname{{\cal S}}_{i}$ for every state in
$\operatorname{{\cal S}}_{i-1}$. A new state in $\operatorname{{\cal S}}_{i}$
is obtained from a state in $\operatorname{{\cal S}}_{i-1}$ by adding, if
needed, some amount of data on machine one and two. Let $a=\sigma_{i-1}(j)$
and $F_{a}$ and $F_{a}^{\prime}$ be the sets defined in (1) and (2). We note
$F_{a}^{\prime\prime}$ the set such that
$F_{a}^{\prime\prime}=E_{Z_{i}}\backslash(F_{a}\cup F_{a}^{\prime})$.

###### Lemma 1

Let $s$ be a state encoding a solution of a graph
$G^{\prime}=(J^{\prime},E^{\prime})$. Then, if we add an edge
$e=\\{j,j^{\prime}\\}$ such that $j\in J^{\prime}$, $j^{\prime}\in J^{\prime}$
and $e\in F_{a}^{\prime\prime}$ then $s$ also encodes a solution of the graph
$G^{\prime}=(J^{\prime},E^{\prime}\cup e)$.

###### Proof

The proof of this lemma is based on the fact that introducing such edge does
not make $s$ inconsistent with graph $G^{\prime}=(J^{\prime},E^{\prime}\cup
e)$. Let us begin by noting that adding an edge $e=\\{j,j^{\prime}\\}\in
F_{a}^{\prime\prime}$ does not require to modify the processing times in $s$
to make it a state encoding a solution of
$G^{\prime}=(J^{\prime},E^{\prime}\cup e)$. Indeed, since $s$ encodes a
solution for $G^{\prime}=(J^{\prime},E^{\prime})$, the processing time induced
by the assignment of $j$ and $j^{\prime}$ has already been encoded. Now,
suppose that $e\in F_{a}^{\prime\prime}$. Then, we have either $j$ and
$j^{\prime}$ that are assigned to the same machine, or $j$ and $j^{\prime}$
that are memorised by both machines. In either case, adding such an edge does
not require to modify the amount of memory or combinatorial frontier in $s$ to
make it a state encoding a solution of $G^{\prime}=(J^{\prime},E^{\prime}\cup
e)$. $\square$

Let us now go back to our algorithm. On the machine processing $j$, our
algorithm adds $\operatorname{\it m}_{j^{\prime}}$ for every vertex
$j^{\prime}\in J_{i}$ such that $\\{j,j^{\prime}\\}\in F_{a}$. Indeed, since
$j^{\prime}$ is on a different machine than $j$ and that this machine does not
memorise $j^{\prime}$, it is necessary to add $\operatorname{\it
m}_{j^{\prime}}$ on machine $\sigma_{i-1}(j)$ to take into account the edge
$\\{j,j^{\prime}\\}$. On the machine not processing $j$, our algorithm adds
$\operatorname{\it m}_{j}$ if there is an edge $\\{j,j^{\prime}\\}\in
F_{a}^{\prime}$. Indeed, as $j^{\prime}$ is on a different machine than
$j^{\prime}$ and $j$ is not memorised by this machine, it is necessary to add
$\operatorname{\it m}_{j}$ on machine $\sigma_{i-1}(j^{\prime})$ to take into
account the existence of such an edge. Finally, we update the combinatorial
frontier information on vertex $j$ if $F_{a}^{\prime}\neq\emptyset$ and on
vertices $j^{\prime}$ such that $\\{j,j^{\prime}\\}\in F_{a}$. Therefore, the
states returned by our algorithm encode solutions for the graph
$G^{\prime}=(J_{i},E_{i-1}\cup F_{a}\cup F_{a}^{\prime}\cup
F_{a}^{\prime\prime})$ and the combinatorial frontier is consistent with the
addition of new vertices or edges. According to Lemma 1, our algorithm encodes
solutions for the graph $G_{i}=(J_{i},E_{i})$ since $E_{i}=E_{i-1}\cup
E_{Z_{i}}$ and $E_{Z_{i}}\\!=F_{a}\cup F_{a}^{\prime}\cup
F_{a}^{\prime\prime}$. Thus, the invariant holds.

Now, if $j\notin J_{L}(i-1)$ the proof of the invariant enforcement is similar
to the case where $j\in J_{L}(i-1)$. The difference lies in the fact that $j$
is not yet assigned. Thus, one must generate two new states in
$\operatorname{{\cal S}}_{i}$ for each state in $\operatorname{{\cal
S}}_{i-1}$ and the processing time, and amount of memory, of $j$ must be added
on the machine processing $j$.

Forget Let $L^{-1}(i)\in J(T)$ be a Forget node of $T$ and $j\in J(G)$ being
the vertex forgotten. Here, our algorithm generates the states of
$\operatorname{{\cal S}}_{i}$ by taking those of $\operatorname{{\cal
S}}_{i-1}$ from which it removes information on vertex $j$ from the
combinatorial frontier. First, let us note that $G_{i}=(J_{i},E_{i})$ is equal
to $G_{i-1}=(J_{i-1},E_{i-1})$ and the invariant holds. Notice that since we
traverse $T$ in bottom-up, we know that removing a vertex $j$ implies that all
edges linked to it have been explored. Otherwise, it would lead to the
violation of a property of the tree decomposition (the third listed in Section
2). Therefore, we can stop memorising the information related to vertex $j$.

Join Let $L^{-1}(i)\in J(T)$ be a Join node of $T$. In that case, our
algorithm computes $\operatorname{{\cal S}}_{i}$ by retrieving the states of
$\operatorname{{\cal S}}_{i-1}$ without modifying them. Since we have
$G_{i}=(J_{i},E_{i})$ equal to $G_{i-1}=(J_{i-1},E_{i-1})$ and no modification
on the combinatorial frontier is performed, the invariant holds.

#### Termination

Finally, from the first and second conditions listed in the definition of the
tree decomposition, we know that the graph
$G_{|J(T)|}=(J_{|J(T)|},E_{|J(T)|})$ is equal to $G=(J,E)$. Since our
invariant is valid for the first node and during the transition from nodes
$L^{-1}(i-1)$ to $L^{-1}(i)$, our algorithm returns an optimal solution for
the scheduling problem under memory constraints.

###  3.3 Algorithm Complexity

Let us now evaluate the time complexity of our dynamic programming algorithm.
Let $J_{L}^{max}:=\max_{1\leq i\leq|J(T)|}|J_{L}(i)|$. Let $\operatorname{\it
p}_{sum}:=\sum_{j\in J(G)}\operatorname{\it p}_{j}$ and $\operatorname{\it
m}_{sum}:=\sum_{j\in J(G)}\operatorname{\it m}_{j}$, then for each state
$s=[c_{1},c_{2},c_{3},c_{4},\operatorname{{\cal C}}_{i}]\in\operatorname{{\cal
S}}_{i}$, $c_{1}$ and $c_{2}$ are integers between $0$ and $\operatorname{\it
p}_{sum}$, $c_{3}$ and $c_{4}$ are integers between $0$ and $\operatorname{\it
m}_{sum}$. The number of distinct combinatorial frontiers is
$4^{J_{L}^{max}}$. Therefore, the number of states is $|\operatorname{{\cal
S}}_{i}|=O(\operatorname{\it p}_{sum}^{2}\times\operatorname{\it
m}_{sum}^{2}\times 4^{J_{L}^{max}})$. The dynamic programming algorithm
processes all $|J(T)|=O(n)$ nodes of the nice tree decomposition. Each state
in a phase can give at most two states in the next phase with a processing
time of $O(J_{L}^{max})$ to compute these states. Recall also that in the
algorithm, if two states $s$ and $s^{\prime}$ have the same components,
including the same combinatorial frontier, then only one of them is kept in
the state space. The time complexity to test whether two states $s$ and
$s^{\prime}$ are the same is thus proportional to the length of the
combinatorial frontier, and is therefore $O(J_{L}^{max})$. We obtain that the
overall complexity of the dynamic programming algorithm is
$O(n\times|\operatorname{{\cal S}}_{i}|\times(J_{L}^{max}+|\operatorname{{\cal
S}}_{i}|J_{L}^{max}))=O(n\times J_{L}^{max}\times(\operatorname{\it
p}_{sum}^{2}\times\operatorname{\it m}_{sum}^{2}\times 4^{J_{L}^{max}})^{2})$.

Notice that $J_{L}^{max}$ depends on the chosen layout $L$, and to minimize
this complexity it is therefore important to find a layout $L$ with a small
$J_{L}^{max}$.

###### Lemma 2

There exists a bottum-up layout $L$ of the nice tree decomposition such that
$J_{L}^{max}\leq tw(G)\,\lceil\log 4n\rceil$.

###### Proof

To prove that such a layout exists we present an algorithm which, when applied
to the root of the nice tree decomposition, computes a bottom-up layout $L$
such that $J_{L}^{max}\leq tw(G)\,\lceil\log 4n\rceil$. To ease the
understanding of certain parts of the proof, these parts will be illustrated
on Figure 4 where a tree with 174 nodes is depicted.

The algorithm works as follows. We perform a depth-first search starting from
the root node, and when we have a Join node we first go to the subtree having
the greatest number of nodes. With this depth-first search we get a discovery
and finishing times for each node. The labeling is obtained by sorting the
nodes in increasing order of their finishing time. As an example, the nodes of
the nice tree decomposition in Figure 3 have been labelled according to this
procedure if we consider in this example that $L^{-1}(i)=i$ for $1\leq i\leq
12$.

Now, let us analyze $J_{L}^{max}$ on the layout returned by our algorithm.
Recall that we use the notation $Z_{i}:=X_{L^{-1}(i)}$ and let us define the
operator $\sqcup$ such that $Z_{i}\sqcup Z_{i+1}:=Z_{i}\setminus\\{j\\}$ if
$L^{-1}(i+1)$ is a Forget node, with $j$ the vertex forgotten, and
$Z_{i}\sqcup Z_{i+1}:=Z_{i}\cup Z_{i+1}$ otherwise. Notice that
$J_{L}(i)=\sqcup_{o\leq i}Z_{o}$ and that if we have a set of consecutive
nodes $L^{-1}(l)$, $L^{-1}(l+1)$, …, $L^{-1}(u)$ such that $L^{-1}(i+1)$ is a
parent node for $L^{-1}(i)$ $(l\leq i\leq u-1)$, then
$\sqcup_{i=l}^{u}Z_{i}=Z_{u}$. Moreover if this chain is maximal, i.e.
$L^{-1}(u+1)$ is not a parent node of $L^{-1}(u)$, then it means that the
parent of $L^{-1}(u)$ is a Join node. For any node $L^{-1}(i)$, we have
$J_{L}(i)=\sqcup_{o\leq i}Z_{o}=\cup_{l\in A}X_{l}$, with $A$ a set of nodes,
of minimum size, that we call critical. This set of critical nodes $A$ can be
obtained by taking the last node in each maximal chain over nodes $L^{-1}(1)$
to $L^{-1}(o)$. Thus, $A$ is composed of the current node $L^{-1}(i)$ along
with other nodes whose parents are Join nodes. Such set $A$ is illustrated in
Figure 4(a) where we consider $i=166$ and where the nodes composing $A$ are
green colored.

For a Join node $L^{-1}(i)$ having two childrens $L^{-1}(l)$ and $L^{-1}(r)$,
let denote by $T_{l}(i)$ and $T_{r}(i)$ the corresponding subtrees. We will
assume that $|T_{l}(i)|\geq|T_{r}(i)|$ and therefore during the depth-first
search we use, node $L^{-1}(l)$ will be examined before node $L^{-1}(r)$. We
say that $L^{-1}(l)$ (resp. $L^{-1}(r)$) is the left (resp. right) children of
$L^{-1}(i)$. By the way the depth-first search is performed, all nodes in $A$,
excepted the current node $L^{-1}(i)$, are left children of Join nodes, and
these Join nodes are on the path $P$ between the root node and the current
node $L^{-1}(i)$. In Figure 4(a), such path $P$ contains the Join nodes purple
colored.

Now, let us bound the number of Join nodes on the path $P$. First, we
construct a reduced graph by removing the nodes of $R$ where $R$ is the set of
nodes of $P$ that are not Join nodes. Such a reduced graph is illustrated in
Figure 4(b). By doing this set of deletions, we get a tree with fewer than
$4n$ nodes (recall that the nice tree decomposition we started from has at
most $4n$ nodes). The number of Join nodes is equal to the length of the
reduced path $P\setminus R$ which is $\lceil\log 4n\rceil$. Indeed, starting
from the root, each time we go on a node along this path the number of
remaining nodes is divided by at least 2.

Thus, we have proved that $|A|\leq\lceil\log 4n\rceil$ for any node
$L^{-1}(i)$ labelled with our algorithm. Recall that $J_{L}(i)=\cup_{l\in
A}X_{l}$, and moreover from the definition of tree-width, we have $|X_{l}|\leq
tw(G)$. Thus, we have $|J_{L}(i)|\leq tw(G)\,\lceil\log 4n\rceil$ and the
proof is complete. $\square$

(a)

Figure 4: Illustration of the proof of Lemma 2 on a possible tree with 174
nodes. The tree is labelled with a bottum-up layout $L$, and for notational
convenience we consider that $L^{-1}(i)=i$ for $1\leq i\leq 174$. Some
subtrees are represented by dashed triangles. On Figure (a) is depicted the
tree. When considering node $166$, the set of critical nodes
$A=\\{166,165,160,140,100\\}$. All nodes in $A$, excepted the node $166$, are
left children of Join nodes, and these Join nodes are on the path
$P=\\{174,173,172,171,170,169,168,167,166\\}$ between the root node 174 and
the node $166$. On Figure (b) is depicted the reduced tree obtained by
removing all nodes in $P$ which are not Join nodes, namely $R$. In each
figure, the set of critical nodes $A$ associated to node $166$ is green
colored and the Join nodes in $P$ are purple colored.

Using the previous defined layout, we obtain an overall complexity of our
dynamic programming algorithm of $O(\operatorname{\it
p}_{sum}^{4}\times\operatorname{\it m}_{sum}^{4}\times
tw(G)\times\log(n)\times n^{2tw(G)+1}\times{16}^{tw(G)})$. The time complexity
of this dynamic programming algorithm being pseudo-polynomial (because of
$\operatorname{\it p}_{sum}$ and $\operatorname{\it m}_{sum}$), we are going
to transform it into a bi-FPTAS.

##  4 Application of a trimming technique

In this Section, we propose a bi-FPTAS derived from the algorithm presented in
Section 3. To transform the dynamic programming algorithm, we apply an
approach for transforming a dynamic programming formulation into a FPTAS. This
approach, called the trimming-the-state-space technique is due to Ibarra & Kim
[7] and consists in iteratively thin out the state space of the dynamic
program by collapsing states that are close to each other.

In the approximation algorithm, we are going to trim the state space by
discarding states that are close to each other. While carrying these states
deletions, we must ensure that the resulting errors cannot propagate in an
uncotrolled way. To this end, we characterize a notion of proximity between
states. We define $\Delta:=1+\varepsilon/8n$, with $\varepsilon>0$ a fixed
constant. Let us first consider the first two coordinates of a state
$s=[c_{1},c_{2},c_{3},c_{4},\operatorname{{\cal C}}_{i}]$. We have $0\leq
c_{1}\leq\operatorname{\it p}_{sum}$ and $0\leq c_{2}\leq\operatorname{\it
p}_{sum}$. We divide each of those intervals into intervals of the form $[0]$
and $[\Delta^{l},\Delta^{l+1}]$, with $l$ an integer value getting from $0$ to
$L_{1}:=\lceil\log_{\Delta}(\operatorname{\it p}_{sum})\rceil=\lceil
ln(\operatorname{\it
p}_{sum})/ln(\Delta)\rceil\leq\lceil(1+\frac{8n}{\varepsilon})ln(\operatorname{\it
p}_{sum})\rceil$. In the same way, we divide the next two coordinates into
intervals of the form $[0]$ and $[\Delta^{l},\Delta^{l+1}]$, with $l$ an
integer value getting from $0$ to
$L_{2}:=\lceil\log_{\Delta}(\operatorname{\it m}_{sum})\rceil$. The union of
those intervals defines a set of non-overlapping boxes. If two states have the
same combinatorial frontier and have their first four coordinates falling into
the same box, then they encode similar solutions and we consider them to be
close to each other.

The approximation algorithm proceeds in the same way as the exact algorithm,
except that we add a trimming step to thin out each state space
$\operatorname{{\cal S}}_{i}$. The trimming step consists in keeping only one
solution per box and per combinatorial frontier. Thus, the worst time
complexity of this approximation algorithm is $O(L_{1}^{4}\times
L_{2}^{4}\times tw(G)\times\log(n)\times n^{2tw(G)+1}\times{16}^{tw(G)})$. We
therefore get a bi-FPTAS when the tree-width $tw(G)$ is bounded by a constant.

###### Theorem 4.1

There exists a bi-FPTAS for the problem $Pk|G,mem|C_{max}$ when the tree-width
of $G$ is bounded by a constant, which returns a solution within a ratio of
$(1+\varepsilon)$ for the optimum makespan, where the memory capacity $M_{i}$,
$1\leq i\leq k$, of each machine may be exceeded by at most a factor
$(1+\varepsilon)$.

For sake of readability, the proof is presented when $k=2$. In the conclusion,
we mention the general case when $k$ is any fixed constant. We denote by
$\operatorname{{\cal U}}_{i}$ (resp. $\operatorname{{\cal T}}_{i}$) the state
space obtained before (resp. after) performing the trimming step at the $i$-th
phase of the algorithm. The proof of this theorem relies on the following
lemma.

###### Lemma 3

For each state $s=[c_{1},c_{2},c_{3},c_{4},\operatorname{{\cal
C}}_{i}]\in\operatorname{{\cal S}}_{i}$, there exists a state
$[c_{1}^{\\#},c_{2}^{\\#},c_{3}^{\\#},c_{4}^{\\#},\operatorname{{\cal
C}}_{i}]\in\operatorname{{\cal T}}_{i}$ such that

$c_{1}^{\\#}\leq\Delta^{i}c_{1}\ \text{ and }\ c_{2}^{\\#}\leq\Delta^{i}c_{2}\
\text{ and }\ c_{3}^{\\#}\leq\Delta^{i}c_{3}\ \text{ and }\
c_{4}^{\\#}\leq\Delta^{i}c_{4}.$ (3)

###### Proof

The proof of this lemma is by induction on $i$. The first node we consider is
a Leaf of the nice tree decomposition and we have $\operatorname{{\cal
T}}_{1}=\operatorname{{\cal S}}_{1}$. Therefore, the statement is correct for
$i=1$. Now, let us suppose that inequality (3) is correct for any index $i-1$
and consider an arbitrary state
$s=[c_{1},c_{2},c_{3},c_{4},\operatorname{{\cal C}}_{i}]\in\operatorname{{\cal
S}}_{i}$. Due to a lack of space, proof of the validity of the Lemma when
passing from phase $i-1$ to $i$ is only presented for a node of type
Introduce. Note that the proof for other types of nodes can be derived from
that of an Introduce node. Let $L^{-1}(i)$ be an Introduce node with $j\in
J(G)$ being the vertex introduced. We must distinguish between cases where $j$
belongs to $J_{L}(i-1)$ and where he does not.

First, let us assume that $j\in J_{L}(i-1)$. Then $s$ was obtained from a
state $[w,x,y,z,\operatorname{{\cal C}}_{i-1}]\in\operatorname{{\cal
S}}_{i-1}$ and
$s=[w,x,y+\delta_{a,1}\alpha_{i}^{1}+\delta_{a,2}\beta_{i}^{1},z+\delta_{a,2}\alpha_{i}^{2}+\delta_{a,1}\beta_{i}^{2},\operatorname{{\cal
C}}_{i}^{a}]$ with $a=\sigma_{i}(j)$. According to the induction hypothesis,
there is a state $[w^{\\#},x^{\\#},y^{\\#},z^{\\#},\operatorname{{\cal
C}}_{i-1}]\in\operatorname{{\cal T}}_{i-1}$ such that

$w^{\\#}\leq\Delta^{i-1}w\ \text{, }\ x^{\\#}\leq\Delta^{i-1}x\ \text{, }\
y^{\\#}\leq\Delta^{i-1}y\ \text{, }\ z^{\\#}\leq\Delta^{i-1}z.$ (4)

The trimmed algorithm generates the state
$[w^{\\#},x^{\\#},y^{\\#}+\delta_{a,1}\alpha_{i}^{1}+\delta_{a,2}\beta_{i}^{1},z^{\\#}+\delta_{a,2}\alpha_{i}^{2}+\delta_{a,1}\beta_{i}^{2},\operatorname{{\cal
C}}_{i}^{a}]\in{\cal U}_{i}$ and may remove it during the trimming phase, but
it must leave some state
$t=[c_{1}^{\\#},c_{2}^{\\#},c_{3}^{\\#},c_{4}^{\\#},\operatorname{{\cal
C}}_{i}^{a}]\in{\cal T}_{i}$ that is in the same box as
$[w^{\\#},x^{\\#},y^{\\#}+\delta_{a,1}\alpha_{i}^{1}+\delta_{a,2}\beta_{i}^{1},z^{\\#}+\delta_{a,2}\alpha_{i}^{2}+\delta_{a,1}\beta_{i}^{2},\operatorname{{\cal
C}}_{i}^{a}]\in~{}{\cal U}_{i}$. This state $t$ is an approximation of $s$ in
the sense of (4).

Indeed, its first coordinate $c_{1}^{\\#}$ satisfies

$c_{1}^{\\#}\leq\Delta(w^{\\#})\leq\Delta(\Delta^{i-1}w)\leq\Delta^{i}w=\Delta^{i}c_{1},$
(5)

its third coordinate $c_{3}^{\\#}$ satisfies

$\begin{split}c_{3}^{\\#}&\leq\Delta(y^{\\#}+\delta_{a,1}\alpha_{i}^{1}+\delta_{a,2}\beta_{i}^{1})\leq\Delta(\Delta^{i-1}y+\delta_{a,1}\alpha_{i}^{1}+\delta_{a,2}\beta_{i}^{1})\\\
&\leq\Delta^{i}y+\Delta(\delta_{a,1}\alpha_{i}^{1}+\delta_{a,2}\beta_{i}^{1})\leq\Delta^{i}c_{3}\end{split}$
(6)

and its last coordinate is the same as $s$. By similar arguments, we can show
that $c_{2}^{\\#}\leq\Delta^{i}c_{2}$ and $c_{4}^{\\#}\leq\Delta^{i}c_{4}$.

Now, let us assume that $j\notin J_{L}(i-1)$. In that case, the state $s$ was
obtained from a state $[w,x,y,z,\operatorname{{\cal
C}}_{i-1}]\in\operatorname{{\cal S}}_{i-1}$ and either $s=[w+\operatorname{\it
p}_{j},x,y+\operatorname{\it
m}_{j}+\alpha_{i}^{1},z+\beta_{i}^{2},\operatorname{{\cal C}}_{i}^{1}]$ or
$s=[w,x+\operatorname{\it p}_{j},y+\beta_{i}^{1},z+\operatorname{\it
m}_{j}+\alpha_{i}^{2},\operatorname{{\cal C}}_{i}^{2}]$. We assume that
$s=[w+\operatorname{\it p}_{j},x,y+\operatorname{\it
m}_{j}+\alpha_{i}^{1},z+\beta_{i}^{2},\operatorname{{\cal C}}_{i}^{1}]$ as,
with similar arguments, the rest of the proof is also valid for the other
case. By the inductive assumption, there exists a state
$[w^{\\#},x^{\\#},y^{\\#},z^{\\#},\operatorname{{\cal
C}}_{i-1}]\in\operatorname{{\cal T}}_{i-1}$ that respects (4). The trimmed
algorithm generates the state $[w^{\\#}+\operatorname{\it
p}_{j},x^{\\#},y^{\\#}+\operatorname{\it
m}_{j}+\alpha_{i}^{1},z+\beta_{i}^{2},\operatorname{{\cal C}}_{i}^{1}]\in{\cal
U}_{i}$ and may remove it during the trimming phase. However, it must leave
some state
$t=[c_{1}^{\\#},c_{2}^{\\#},c_{3}^{\\#},c_{4}^{\\#},\operatorname{{\cal
C}}_{i}^{1}]\in{\cal T}_{i}$ that is in the same box
as$[w^{\\#}+\operatorname{\it p}_{j},x^{\\#},y^{\\#}+\operatorname{\it
m}_{j}+\alpha_{i}^{1},z+\beta_{i}^{2},\operatorname{{\cal C}}_{i}^{1}]\in{\cal
U}_{i}$. This state $t$ is an approximation of $s$ in the sense of (4).
Indeed, its last coordinate $\operatorname{{\cal C}}_{i}^{1}$ is equal to
$\operatorname{{\cal C}}_{i}$ and, by arguments similar to those presented for
$j\in J_{L}(i-1)$, we can show that $c_{o}^{\\#}\leq\Delta^{i}c_{o}$, for
$o\in\llbracket 1,4\rrbracket$. Thus, our assumption is valid during the
transition from phase $i-1$ to $i$ when $i$ is an Introduce node.

Since the proof for the other type of nodes can be derived from the proof of
an Introduce node, the inductive proof is completed.

$\square$

Now, let us go back to the proof of Theorem 4.1. After at most $4n$ phases,
the untrimmed algorithm outputs the state
$s=[c_{1},c_{2},c_{3},c_{4},\operatorname{{\cal C}}]$ that minimizes the value
$\max\\{c_{1},c_{2}\\}$ such that $c_{3}\leq M_{1}$ and $c_{4}\leq M_{2}$. By
Lemma 3, there exists a state
$[c_{1}^{\\#},c_{2}^{\\#},c_{3}^{\\#},c_{4}^{\\#},\operatorname{{\cal
C}}]\in{\cal T}_{n}$ whose coordinates are at most a factor of $\Delta^{4n}$
above the corresponding coordinates of $s$. Thus, we conclude that our trimmed
algorithm returns a solution where the makespan is at most $\Delta^{4n}$ times
the optimal solution and the amount of memory for each machine is at most
$\Delta^{4n}$ its capacity. Moreover, since $\Delta:=1+\varepsilon/8n$, we
have $\Delta^{4n}\leq 1+\varepsilon$ for $\varepsilon\leq 2$.

So we have presented an algorithm that returns a solution such that the
makespan is at most $(1+\varepsilon)$ times the optimal solution and the
amount of memory for each machine is at most $(1+\varepsilon)$ its capacity.
It ends the proof of Theorem 4.1.

Notice that if we no more consider the maximum memory load as a constraint but
as an objective, our algorithm can be modified to get an $(1+\epsilon)$
approximate Pareto set [23]. At the end of the algorithm, we consider all the
states in $\operatorname{{\cal S}}_{|J(T)|}$ and compute for each state
$s=[c_{1},c_{2},c_{3},c_{4},\operatorname{{\cal
C}}_{|J(T)|}]\in\operatorname{{\cal S}}_{|J(T)|}$ the vector
$[\max\\{c_{1},c_{2}\\},\max\\{c_{3},c_{4}\\}]$. Then among this set of
vectors, we compute the set of nondominated vectors. The problem of finding a
set of nondominated vectors among a given set of vectors has been first
introduced in [24] and there exists a lots of efficient algorithms for this
problem (see for example [25]). It is easy to see that the obtained set is a
$(1+\varepsilon)$-approximate Pareto set for our problem.

##  5 Conclusion

Given $2$ machines and a neighborhood graph of jobs with bounded tree-width,
we have presented an algorithm that returns a solution, where the capacity of
the machines may be exceeded by a factor at most $1+\epsilon$, if at least one
solution exists for the scheduling problem under memory constraints. This
algorithm consists of three steps: construct a nice tree decomposition of the
neighborhood graph; compute a specific bottom-up layout $L$ of the nice tree
decomposition; and use a transformed dynamic programming algorithm traversing
the nice tree decomposition following $L$. The specific bottom-up layout $L$
is designed to bound the complexity of our algorithm but it is not optimal. It
would be interesting to lower this complexity by taking into account the
number of vertices associated to each node (see for example [10]) and avoiding
counting duplicate vertices. However, using layout $L$, the output of our
algorithm is generated in polynomial time and is such that the makespan is at
most $(1+\varepsilon)$ times the optimal solution and the amount of memory for
each machine is at most $(1+\varepsilon)$ its capacity.

Although the algorithm is presented for 2 machines, it can be extended to any
number of machines as adding machines means increasing the number of
dimensions of a state. It would require to modify the combinatorial frontier
such that $\sigma_{i}^{\prime}(j)$ would be the machines on which $j$ has not
been assigned and which have memorized the data of $j$. This would change the
time complexity to $O(n\times L_{1}^{2k}\times L_{2}^{2k}\times k\times
tw(G)\times log(n)\times n^{2(ktw(G)+1)}\times 16^{ktw(G)}\times k^{4tw(G)})$
where $n$ is the number of phases; $L_{1}^{k}\times L_{2}^{k}$ is the number
of of boxes, $L_{1}^{k}\times L_{2}^{k}\times k\times tw(G)\times log(n)$ is
the the processing time to compute if the states are the same; and
$n^{2(ktw(G)+1)}\times 16^{ktw(G)}\times k^{4tw(G)}$ is the number of
distincts combinatorial frontiers.

Now that we have provided a bi-FPTAS for graphs of bounded tree-width, it
would be interesting to look at graphs bounded by more generic graph
parameters like the clique-width and local tree-width. The latter is all the
more interesting as we know that planar graphs have locally bounded tree-width
and can be used to model numerical simulations on HPC architectures.

## References

  * [1] Angel, E., Chevalier, C., Ledoux, F., Morais, S., Regnault, D.: FPT approximation algorithm for scheduling with memory constraints. In: Dutot, P.F., Trystram, D. (eds.) Euro-Par 2016: Parallel Processing. pp. 196–208. Springer International Publishing, Cham (2016)
  * [2] Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25(6), 1305–1317(1996)
  * [3] Chen, L., Jansen, K., Luo, W., Zhang, G.: An efficient PTAS for parallel machine scheduling with capacity constraints. In: Chan, T.H., Li, M., Wang, L. (eds.) Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings. Lecture Notes in Computer Science, vol. 10043, pp. 608–623. Springer (2016)
  * [4] Chi, Z., Gang, W., Xiaoguang, L., Jing, L.: Approximating scheduling machines with capacity constraints. In: Proceedings of the 3D International Workshop on Frontiers in Algorithmics. pp. 283–292. FAW ’09, Springer-Verlag (2009)
  * [5] Ern, A., Guermond, J.L.: Theory and Practice of Finite Elements. Appl. Math. Sci. 159, Springer-Verlag, New York (2004)
  * [6] Gairing, M., Monien, B., Woclaw, A.: A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. Theor. Comput. Sci. 380(1-2), 87–99 (Jul 2007)
  * [7] Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463–468 (1975)
  * [8] Kellerer, H., Kotov, V.: A 3/2-approximation algorithm for 3/2-partitioning. Oper. Res. Lett. 39(5), 359–362 (2011)
  * [9] Kloks, T.: Treewidth, computations and approximations. In: Lecture Notes in Computer Science (1994)
  * [10] Lam, C.C., Rauber, T., Baumgartner, G., Cociorva, D., Sadayappan, P.: Memory-optimal evaluation of expression trees involving large objects. Computer Languages, Systems and Structures 37(2), 63–75 (2011)
  * [11] Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(3), 259–271 (1990)
  * [12] LeVeque, R.J.: Finite Volume Methods for Hyperbolic Problems (Cambridge Texts in Applied Mathematics). Cambridge University Press (2002)
  * [13] Robertson, N., Seymour, P.: Graph minors. i. excluding a forst. Journal of Combinatorial Theory, Series B 35(1), 39–61 (1983)
  * [14] Saha, B., Srinivasan, A.: A new approximation technique for resource-allocation problems. In: Proc. Innovations in Computer Science (ICS), 342–357 (2010)
  * [15] Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS Journal on Computing 12(1), 57–74 (2000)
  * [16] Woeginger, G.J.: A comment on scheduling two parallel machines with capacity constraints. Discret. Optim. 2(3), 269–272 (Sep 2005)
  * [17] Ü. V. Çatalyürek and C. Aykanat: (2011) PaToH (Partitioning Tool for Hypergraphs). In: Padua D. (eds) Encyclopedia of Parallel Computing. Springer, Boston, MA
  * [18] F. Pellegrini and J. Roman: Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs, International Conference and Exhibition on High-Performance Computing and Networking, 493-498, (1996)
  * [19] G. Karypis and V. Kumar: Metis A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, 1998.
  * [20] K.D. Devine, E.G. Boman, L.A. Riesen, U.V. Catalyurek and C. Chevalier: Getting Started with Zoltan: A Short Tutorial, 2009 Dagstuhl Seminar on Combinatorial Scientific Computing, 2009.
  * [21] C. Chevalier, F. Ledoux and S. Morais: A Multilevel Mesh Partitioning Algorithm Driven by Memory Constraints, Proceedings of the SIAM Workshop on Combinatorial Scientific Computing, 85–95 (2020)
  * [22] T.T. Nguyen and J. Rothe, Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs, ISAAC 2020.
  * [23] C. H. Papadimitriou and M. Yannakakis, On the approximability of trade-offs and optimal access of Web sources, Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000, 86–92.
  * [24] H. T. Kung, F. Luccio, and F. P. Preparata, On Finding the Maxima of a Set of Vectors, J. ACM 22, 4 1975, 469-–476.
  * [25] Sumit Mishra, Sriparna Saha, Samrat Mondal and Carlos A. Coello Coello, A divide-and-conquer based efficient non-dominated sorting approach, Swarm and Evolutionary Computation, 44, 2019, 748–773.