# Focusing on Persons: Colorizing Old Images Learning from Modern Historical
Movies

Xin Jin, Zhonglan Li, Ke Liu  Department of Cyber Security, Beijing Electronic
Science and Technology InstituteNo 7, Fufeng RoadFengtai DistrictBeijing
100070China ,  Dongqing Zou<EMAIL_ADDRESS>SenseTime Research and
Tetras.AIBeijing 100080China Qing Yuan Research Institute, Shanghai Jiao Tong
UniversityShanghai 200240China and  Xiaodong Li, Xingfan Zhu, Ziyin Zhou,
Qilong Sun, Qingyu Liu  Department of Cyber Security / Cryptography, Beijing
Electronic Science and Technology InstituteNo 7, Fufeng RoadFengtai
DistrictBeijing 100070China

(2021)

###### Abstract.

In industry, there exist plenty of scenarios where old gray photos need to be
automatically colored, such as video sites and archives. In this paper, we
present the HistoryNet focusing on historical person’s diverse high fidelity
clothing colorization based on fine grained semantic understanding and prior.
Colorization of historical persons is realistic and practical, however,
existing methods do not perform well in the regards. In this paper, a
HistoryNet including three parts, namely, classification, fine grained
semantic parsing and colorization, is proposed. Classification sub-module
supplies classifying of images according to the eras, nationalities and
garment types; Parsing sub-network supplies the semantic for person contours,
clothing and background in the image to achieve more accurate colorization of
clothes and persons and prevent color overflow. In the training process, we
integrate classification and semantic parsing features into the coloring
generation network to improve colorization. Through the design of
classification and parsing subnetwork, the accuracy of image colorization can
be improved and the boundary of each part of image can be more clearly.
Moreover, we also propose a novel Modern Historical Movies Dataset (MHMD)
containing 1,353,166 images and 42 labels of eras, nationalities, and garment
types for automatic colorization from 147 historical movies or TV series made
in modern time. Various quantitative and qualitative comparisons demonstrate
that our method outperforms the state-of-the-art colorization methods,
especially on military uniforms, which has correct colors according to the
historical literatures.

Fine grained semantic parsing, Colorization, HistoryNet, MHMD

††journalyear: 2021††copyright: acmcopyright††conference: Proceedings of the
29th ACM International Conference on Multimedia; October 20–24, 2021; Virtual
Event, China††booktitle: Proceedings of the 29th ACM International Conference
on Multimedia (MM ’21), October 20–24, 2021, Virtual Event, China††price:
15.00††doi: 10.1145/3474085.3481544††isbn: 978-1-4503-8651-7/21/10††ccs:
Computing methodologies Image segmentation Figure 1. We propose a colorization
method focusing on persons that considers fine grained semantic parsing and
correct color of images. Our method performs better on historical images.

##  1\. Introduction

Image colorization is a classic image editing problem and has always been a
research hotpot in the field of image editing. Many black-and-white military
photos were left in the war years. The color restoration of these photos can
better understand the history and have great significance. Also, automatic
colorization has a very wide range of applications in industry. There are a
large number of images that need to be colored with modern technology to
present better visual effects in some video websites such as YouTube. Many
archives and museums also have similar requirements. However, so many
colorization methods are not suitable for repairing these photos, they do not
consider the fine grained semantic parsing of military uniform and the
classification of clothing, which makes the coloring result poor. In this
paper, the superiority of HistoryNet network to the colorization of person’s
clothing is shown mainly through the colorization of military uniform, which
has more practical significance.

Traditional colorization methods (Bahng et al., 2018; Chen et al., 2018; Liu
et al., 2017; Manjunatha et al., 2018) propose methods with semantics of input
text and language description. Although these methods obtain the semantic
segmentation information of reference images, they ignore the boundary of
person and background, and also don’t consider the human parsing of each part.
With the advances of deep learning, many researchers use CNN or GAN to extract
information of grayscale images for colorization such as (Iizuka et al., 2016;
Mouzon et al., 2019; Larsson et al., 2016; Isola et al., 2017; Nazeri et al.,
2018; Cao et al., 2017; Vitoria et al., 2020a; Yoo et al., 2019). These
methods often realize the natural color matching, which means the colorization
is a subjective problem. However, the colorization of historical military
uniform is realistic and practical. In addition, most of the existing modern
color image datasets lack the old content or information of real gray
historical images, especially the colors of the garments of the historical
persons. This will also lead to the poor performance of current colorization
methods in military uniforms, as shown in the second line of Figure 1.

To address these shortcomings, we propose a new HistoryNet architecture and a
MHMD dataset. First, there are a great variety of military uniform in history
and we can obtain the eras, nationalities and garment types information of an
image. According to these, we design the labels of images and classification
subnetwork. Classification submodule supplies classifying of images according
to the eras, nationalities and garment types labels. In addition, we have
designed a classifier submodule in discriminator, which joint classification
subnetwork to constrain loss for getting more suitable colorization. Inspired
by InfoGAN (Chen et al., 2016), we have designed classifier subnetwork that
can better present the classification information. Second, we have designed
fine grained semantic parsing subnetwork, which supply the semantic
understanding of historical person’s clothing. Through this subnetwork, the
historical person’s each part (such as face, arms, hair and so on) will be
separate and obtain a clear boundary finally. In the training process, based
on U-net (Ronneberger et al., 2015), we connect the up-sample layers of image
features on the parsing subnetwork with the generator network of colorization.
And in the future, we also hope to apply relevant research methods to video
colorization. Third, we propose a new dataset called Modern Historical Movies
Dataset (MHMD) for automatic image colorization. We randomly select 2,000
images from ImageNet (Deng et al., 2009) and MHMD datasets to caculate their
average values on H channel of HSV. MHMD dataset focus on blue and red yellow
of color area and ImageNet dataset is distributed in all color areas,
especially in yellow and blue areas. This shows that MHMD dataset considers
the old content and information of real gray historical images, which are
mostly dark blue and red yellow. However, the distribution of ImageNet dataset
is more balanced in H value. Therefore, our method can perform well in
colorizing old images. Finally, the contributions of this work include:

  1. (1)

Semantic parsing subnetwork can accurately obtain the semantic information of
various parts of person, which makes the image colorization boundary and the
human semantic parsing more accurate.

  2. (2)

In HistoryNet, we have designed classifier and classification subnetworks.
Info information of classifier subnetwork and classification labels jointly
achieve HistoryNet coloring accuracy and classification labels more precise.

  3. (3)

We propose a dataset of persons colorization which is called MHMD: Modern
Historical Movies Dataset. MHMD contains 1,353,166 images and the 42 labels of
eras, nationalities, and garment types, which have great influences on the
colorization of old images.

##  2\. Related work

Reference Image-based Methods Manga also called Japanese comic is popular all
over the world. Most of them are monochrome. Therefore, many manga
colorization methods appeared which are based on a reference image of sketch
and line art. (Sato et al., 2014) propagate the colors of the reference manga
to the target manga by representing images as graphs and matching graphs.
(Zhang et al., 2017a) integrate residual U-net to apply the style to the
grayscale sketch with auxiliary classifier generative adversarial network (AC-
GAN) (Odena et al., 2017). (Ci et al., 2018) propose a novel deep conditional
adversarial architecture for scribble based anime line art colorization.
(Hensman and Aizawa, 2017) propose a manga colorization method based on
conditional Generative Adversarial Networks (cGAN) and require only a single
colorized reference image for training. (Furusawa et al., 2017) colorize a
whole page (not a single panel) semiautomatically, with the same color for the
same character across multiple panels. In addition, (Welsh et al., 2002; Xian
et al., 2018) focus on the texture and luminance information of the reference
image to achieve colorization. (Ironi et al., 2005; Sun et al., 2019; Zhang et
al., 2017b) are other methods based on reference image. (Ironi et al., 2005)
colorize images from pixel level. (Sun et al., 2019) propose a dual
conditional generative adversarial network which considers contour and color
style of images.

Semantics-based Methods Researchers have propose many semantic-based methods
to deal with the colorization problem of grayscale images. (Bahng et al.,
2018; Chen et al., 2018; Liu et al., 2017; Manjunatha et al., 2018) colorize
gray images based on semantics of input text and language description. (Zou et
al., 2019; Zou et al., 2018) both propose a method based on scene sketches and
semantic segmentation. (Zhao et al., 2019; Su et al., 2020) learn object-level
semantics to guide image colorization. (Zhao et al., 2019) propose to exploit
pixelated object semantic to guide image colorization, which also consider the
semantic categories of objects. (Deshpande et al., 2015) achieve auto image
colorization by learning from examples. (Kim et al., 2019) propose a Tag2Pix
GAN architecture which takes a grayscale line art and color tag information as
input to produce a quality colored image.

Deep Learning-based Methods Cheng et al. (Cheng et al., 2015) first propose a
neural network method for automatic colorization. With the development of CNN,
(Iizuka et al., 2016; Mouzon et al., 2019; Larsson et al., 2016) use CNN to
extract information of images. In the work of Iizuka et al. (Iizuka et al.,
2016), the colorization network can obtain both local and global features of
the image. In the research of Mouzon et al. (Mouzon et al., 2019), the
distribution statistical method is combined with the variational method to
calculate the possible color probability for each pixel of the image. (Larsson
et al., 2016) train a VGG to learn the color histogram of each pixel.

Many existing GAN have the ability to learn the probability distribution of
high dimensional spatial data, which can be applied to colorization tasks. The
method in (Isola et al., 2017) use conditional GAN to map the input grayscale
image to the output colorized image. Nazeri et al. (Nazeri et al., 2018)
attempt to fully generalize the colorization procedure using a conditional
DCGAN. (Cao et al., 2017) leverage the conditional GAN to automatically obtain
a variety of possible colorization results through multiple sampling of the
input noise. (Vitoria et al., 2020a) propose an adversarial learning
colorization approach coupled with semantic information. (Yoo et al., 2019)
present a novel memory-augmented colorization model Memo-Painter that can
produce high-quality colorization with limited data.

##  3\. Architecture and Training Losses

Figure 2. HistoryNet network structure diagram. Overview of our model, it
combines a low-level feature network $G_{0}$ (in yellow), a Generator network
$G_{1}$ (include yellow, blue, red and orange layers), a classification
network $G_{2}$ (in red), a parsing network $G_{3}$ (in orange) and a
Discriminator network. The discriminator network is divided into two parts
which are $D_{1}$ (in green) and $D_{2}$ (in purple).

According to the description of the HistoryNet network structure, we define
the total loss function as:

(1)
$L\left(G_{\theta},D_{w}\right)=L_{r}\left(G_{\theta_{1}}^{1}\right)+\lambda_{cls}L_{cls}\left(G_{\theta_{2}}^{2}\right)$
$+\lambda_{par}L_{par}\left(G_{\theta_{3}}^{3}\right)+{\lambda_{g}}{L_{g}}\left(G_{\theta_{1}}^{1},D_{w}\right)+\lambda_{info}L_{info}\left(G_{\theta_{1}}^{1}\right)$

The first three terms in the formula are the loss values of the generator, we
denote them by
$G_{\theta}=(G_{\theta_{1}}^{1},G_{\theta_{2}}^{2},G_{\theta_{3}}^{3})$, where
$\theta=(\theta_{1},\theta_{2},\theta_{3})$ stand for all the generator
parameters. The last two terms are the loss values of the discriminator which
we denote by $D_{w}$.

Generator Network The generator network mainly generates $(a,b)$ channel
images. We define its loss function as:

(2)
$L_{r}\left(G_{\theta_{1}}^{1}\right)=E_{\left(L,{a_{r}},{b_{r}}\right)\sim{P_{r}}}\left[||G_{\theta_{1}}^{1}\left(L\right)-\left(a_{r},b_{r}\right)||_{2}^{2}\right]$

Where $(L,a_{r},b_{r})$ is the representation of the color image in the CIE
$L_{ab}$ color space, and $P_{r}$ is the distribution of the color image.
$||\cdot||_{2}$ is the Euclidean distance. By calculating the Euclidean
distance between $G_{\theta_{1}}^{1}\left(L\right)$ and
$\left(a_{r},b_{r}\right)$, the resulting image can better perceive the color
difference with the real image in the $L_{ab}$ color space. $L2$ loss has
enough ability to constrain the network to obtain more realistic colorization
results.

Parsing Network While many methods consider the semantic segmentation for
colorization, they are not suitable for the historical person’s diverse
clothing colorization, thus we propose fine grained semantic understanding for
this issue. Under the guidance of human parsing as ground truth, the parsing
feature of the image is obtained by continuously up-sampling and based on
U-net (Ronneberger et al., 2015), we concatenate the up-sampling information
of parsing network with the generator network (the blue $G_{1}$). Through this
way, the generator network can obtain the fine grained semantic parsing
information of images. For example, the person’s face, hat, hands and clothes
are separated to ensure the colorization boundary is clear and accurate. As
shown in Figure 6. The parsing network loss we defined is:

(3)
$L_{par}\left(G_{\theta_{3}}^{3}\right)=E_{\left(S,{a_{r}},{b_{r}}\right)\sim{P_{r}}}\left[||G_{\theta_{3}}^{3}\left(S\right)-\left(a_{r},b_{r}\right)||_{2}^{2}\right]$

In $(S,a_{r},b_{r})$, $S$ is the image before parsing, and $(a_{r},b_{r})$ is
the parsing image. Calculating the Euclidean distance between the image
generated by the parsing network and the actual parsing image and minimize it.
In this way, the image input to the parsing network is closer to the real
image and finally the colorization result is more accurate.

Classification network As shown in red in Figure 2, classification network is
designed to obtain the high-level features of the image and the category label
information of the image colorization. The convolution of four modules are
then divided into two parts of full connection layers. The gray fully
connected layers on the right side obtain a 42-dimensional vector that
represents the 42 classification labels in the dataset we developed. 42 labels
consider the eras, nationalities and garment types of historical person’s
images. The detailed labels of classification improve the accuracy of image
colorization such as the navy clothing is mainly white. The second part (as
shown in the red part) is concatenated together with the blue $G_{1}$
convolution layer above. This part can obtain 256-dimensional vector which is
corresponding to classifier network to constrain the loss for correct color
classification of images. The loss function is defined as:

(4)
$L_{cls}\left(G_{\theta_{2}}^{2}\right)=E_{L\sim{P_{rg}}}\left[KL\left(y_{v}||G_{\theta_{2}}^{2}\left(L\right)\right)\right]$

Where $P_{rg}$ is the distribution of the input grayscale image. $y_{v}\in
R^{m}$ is the classification vector obtained by the VGG network classifying
the images in the dataset, and $m$ is the number of image classifications.
$KL$ divergence calculate the loss due to $y_{v}$ fitting
$G_{\theta_{2}}^{2}(L)$. The input grayscale image is processed by the
classification network so that the coloring network can choose color more
correctly.

Classifier Network In general colorization methods, the loss of colorization
is required to be minimized as much as possible, so that the colorization
result is closer to the real image. For example, when we want to colorize a
certain object blue sky, no matter how many images are trained, the final
average color value is blue so that the colorization image is still blue of
sky. However, due to the nationality variations, garment types and era
differences, these factors will hinder the calculation of color loss value of
historical person’s images especially military uniform. According to the
traditional method of calculating the minimum loss between the colorization
image and the real image, the color of the final colorization image will tend
to be gray after averaging. So, classifier network adopt InfoGAN (Chen et al.,
2016), which can make good use of the information of image latent code to
achieve better performance of images. After obtaining the $(a,b)$ channel of
image through the generator, we input it into the classifier network, and
finally obtain a 256-dimensional vector through the fully connected layers.
The $KL$ divergence between the 256-dimensional vector obtained in
classification network $G_{2}$ is expected to minimize the fitting loss so
that the generated image can better present the classification information.

During this way, final colorization images can have correct color for each
part of garment. In addition, the interior coloring of each part of the
garment is continuous. As shown in Figure 7. The loss we designed is:

(5)
$L_{info}\left(G_{\theta_{1}}^{1}\right)=E_{L\sim{P_{rg}}}\left[KL\left(\textit{infoGAN}||G_{\theta_{1}}^{1}\left(L\right)\right)\right]$

Discriminator Network As shown in Figure 2, $D_{1}$ is based on the Markov
discriminator architecture. The PatchGAN (Isola et al., 2017) discriminator
can track and capture the high-frequency structure of the generated image,
thereby making up for the high-frequency information loss caused by the use of
$L2$ loss in $G_{1}$. For this reason, we define each patch as true or fake.

In this paper, based on WGAN (Arjovsky et al., 2017), we design the loss of
discriminator. WGAN (Arjovsky et al., 2017) uses the Earth-Mover distance to
minimize the possible and true distribution of the generator. Using this
feature of the WGAN (Arjovsky et al., 2017) network can avoid gradient
disappearance and mode collapse during the training process and eventually
achieve stable training and obtain better-colored images. Also, we use
Kantorovich - Rubinstein duality (Kantorovitch, 1958; Villani, 2008) and add
the gradient penalty term to constrain the $L2$ norm of the discriminator
relative to its input, thus defining $D_{w}\in D$, where $D$ denotes the set
of 1-Lipschitz functions.

(6)
$\begin{split}L_{g}\left(G_{\theta_{1}}^{1},D_{w}\right)&=E_{\tilde{I}\sim{P_{r}}}\left[D_{w}\left(\tilde{I}\right)\right]\\\
&-E_{\left(a,b\right)\sim{P_{G_{\theta_{1}}^{1}}}}\left[D_{w}\left(L,a,b\right)\right]\\\
&-E_{\hat{I}\sim{P_{\hat{I}}}}\left[\left({{||\nabla_{\hat{I}}}{D_{w}}\left(\hat{I}\right)||_{2}}-1\right)^{2}\right]\end{split}$

Where $P_{G_{\theta_{1}}^{1}}$ is the model distribution in
$G_{\theta_{1}}^{1}(L)$ of L $\sim$ $P_{rg}$. As in (Gulrajani et al., 2017),
$P_{\hat{I}}$ is a straight-line uniform sampling which is between the pairs
of points sampled along the data distribution $P_{r}$ and the generator
distribution $P_{G_{\theta_{1}}^{1}}$.

According to the formula (1) (total loss function) proposed above, we train
the networks $G$ and $D$ by calculating the following expressions. During the
training process, We take the hyperparameter values
$\lambda_{cls},\lambda_{par},\lambda_{g},\lambda_{info}$ as: 0.003, 0.003,
0.1, 0.003.

(7) $\min_{G_{\theta}}\max_{D_{w}\in D}L\left(G_{\theta},D_{w}\right)$

##  4\. Datasets

The colorization of historical person’s clothing is of practical significance,
especially the colorization of historical military uniform. At present, most
of the existing modern color image datasets contain modern objects or scenes
but lack old content or information of real gray historical images, especially
the colors of the garments of the historical persons. Therefore, we build a
dataset called MHMD: Modern Historical Movies Dataset. MHMD can meet the
requirements of garment types, eras and nationalities. First of all, we search
for 147 historical movies and TV series in modern time. Second, after
preprocessing, the MHMD dataset obtains 1,353,166 images,including 1.2M images
on training dataset and 100001 images on testing dataset. We classify the
images into 42 labels according to above types, as shown in Figure 3. The 42
labels are divided by us have solved the problem of different military
uniforms of different countries in different periods. Detailed classification
of labels is helpful to obtain accurate information for network structure. On
this basis, we design the HistoryNet network structure to realize the
colorization of historical military uniforms and the restoration of old
historical photos. More details about MHMD can be found on
https://github.com/BestiVictory/MHMD.

Figure 3. The picture shows the U.S. military uniform, formal and non formal
labels and the corresponding number of pictures before, during and after World
War II in MHMD.

###  4.1. Collecting Methods

We present MHMD of approximately 1.3M images with image-level labels and
localization instructions. We mainly download TV series, movies and
documentaries from various websites. Because we are focusing on the
colorization of historical person’s images and in order to ensure the quality
of the films (such as definition, etc.), we have formulated the film selection
criteria: color films taken after the 1990s, the content of the film is mainly
about history, war, person and objects of various countries before 1990.

###  4.2. Processing Methods

First, we cut the film into images, and use the program to remove black and
white images, images with too low pixel blur. For the goal of focusing on
persons, we use Yolov3 to judge whether there is a person in the image and
delete the images without people or too many people. Through these
preprocessing, the diversity of the content and the clarity of the image are
guaranteed. Secondly, through an image, we can obtain the eras, nationalities
and garment types information of it. According to this, we have designed 42
kinds of labels and divide them into three categories: era, nationality and
garment type. The era label is divided into: before, during and after World
War II. Nationality labels are: China (divided into the Communist Party and
the Kuomintang), Japan, the United States, Germany, Britain and Russia. There
are three types of garment type: military, formal (such as suits) and
informal. Thirdly, We randomly extract 1% of the images from the dataset,
which is the same distribution as the original dataset, and then we label the
1% images manually. The 1% images and data augmentation of these images (such
as horizontal image mirroring and Gaussian blur) will be inputted to ResNet
(He et al., 2016) for training. After the training, we input other images in
the dataset into ResNet (He et al., 2016) for automatic classification to
obtain labels. The accuracy of classification can reach 98% or more. The
categories of MHMD and the comparison with other colorization datasets are
shown in table 1.

Table 1. Comparison of MHMD with other colorization datasets | The labels of the dataset |
---|---|---
Dataset | Scene | Era | Nationality | Garment Type | Total
MHMD | × | Before WWII | 66,900 | Chinese | 753,473 | Military | 707,771 | 1,353,166
American | 934,415
During WWII | 547,318 | Russian | 45,291 | Formal | 104,763
German | 59,015
After WWII | 738,948 | Japanese | 110,562 | Informal | 540,632
|  | English | 46,641 |
ImageNet (Deng et al., 2009) | ✓ | × | × | × | about 1,300,000
COCO-Stuff (Caesar et al., 2018) | ✓ | × | × | × | about 164,000
Places205 (Zhou et al., 2014) | ✓ | × | × | × | 20,500

##  5\. Experiments

Figure 4. Contrastive experimental diagram. Some qualitative results, from
left to right: Original, Gray, Ours, Deoldify (Antic, 2019), Iizuka et al.
(Iizuka et al., 2016), Larsson et al. (Larsson et al., 2016), ChromaGAN
(Vitoria et al., 2020b), Su et al. (Su et al., 2020). The results are
comparable.

In this section, we evaluate our methods quantitatively and qualitatively on
MHMD we designed. We compare our experimental results with, Deoldify (Antic,
2019), Iizuka et al. (Iizuka et al., 2016), Larsson et al. (Larsson et al.,
2016), ChromaGAN (Vitoria et al., 2020b), Su et al. (Su et al., 2020), and use
LPIPS (Zhang et al., 2018), PSNR and SSIM indicators to quantitatively compare
our experimental results with those of the most advanced methods. Finally, we
carry out ablation experiments on parsing network and classifier network, and
prove that they have positive effects on the improvement of network
performance.

Figure 5. The colorization comparison of natural scenery and person on
HistoryNet. Our method also works well in natural scenes.

###  5.1. Implementation Details

We train HistoryNet for a total of eight epochs and set the batch size to 16,
on the 1.3M images from MHMD resized to 224${\times}$224\. A single epoch
takes approximately 28 hours on a Nvidia titan X pascal GPU. We minimize our
objective loss using Adam optimizer with learning rate equal to
2${\times}$10-5 and momentum parameters $\beta_{1}=0.5$ and $\beta_{2}=0.999$.
We alternate the optimization of the generator $G_{0}$ and discriminator
$D_{1}$. The first stage of the network (displayed in yellow in Figure 2),
takes as input a grayscale image of size 224 ${\times}$ 224, and is
initialized using the pre-trained weights of the VGG-16 (Simonyan and
Zisserman, 2014) trained on ImageNet.

###  5.2. Quantitative Comparisons

We use three metrics, LPIPS (Zhang et al., 2018), PSNR and SSIM. LPIPS (Zhang
et al., 2018) is a measurement method of perceptual similarity proposed by
Zhang et al. that can achieve good perceptual judgment in challenging models
of visual prediction and other tasks. The lower the LPIPS (Zhang et al., 2018)
value, the smaller the perceived difference between the image and the original
image. PSNR and SSIM are two commonly used indexes in image quality
evaluation. PSNR is peak signal to noise ratio, which is usually used as an
evaluation index of the quality of an image before and after compression. The
higher the PSNR value is, the better the quality of the generated image will
be. SSIM is structural similarity index, which is an index to measure the
similarity between two images. Table 2 shows the comparison of our
experimental results with Deoldify (Antic, 2019), Iizuka et al. (Iizuka et
al., 2016), Larsson et al. (Larsson et al., 2016), ChromaGAN (Vitoria et al.,
2020b), Su et al. (Su et al., 2020). In the above methods, We have
successfully applied the network structures of ChromaGAN (Vitoria et al.,
2020b) and Su et al. (Su et al., 2020) to MHMD for training, and the training
details are shown in the supplementary.

Table 2. Quantitative comparison of experimental Method | LPIPS↓ | PSNR↑ | SSIM↑
---|---|---|---
Iizuka et al. (Iizuka et al., 2016) | 0.134 | 25.779 | 0.956
Larsson et al. (Larsson et al., 2016) | 0.147 | 24.527 | 0.946
Deoldify (Antic, 2019) | 0.127 | 26.321 | 0.957
ChromaGAN (Vitoria et al., 2020a) | 0.118 | 29.487 | 0.951
Su et al. (Su et al., 2020) | 0.132 | 25.951 | 0.941
HistoryNet | 0.101 | 30.638 | 0.962

As can be seen from table 2, our method have better perform in these metrics.
The lower LPIPS value indicates that our results are more similar to the
source image. The higher PSNR and SSIM values means that the quality of the
generated image is better and is similar to the original image.

###  5.3. Ablation Experiments

We have trained ChromaGAN on MHMD dataset as a baseline. As can be seen from
table 3, LPIPS, PSNR and SSIM perform better after the parsing and classifier
networks are added. This is enough to show that the parsing network plays a
positive role in image colorization and classifier network can be better used
in image colorization network after obtaining the information of image latent
layer. It can be seen from the last row of table 3 that our proposed method
can perform well on all three parameters, which fully shows that our method
has a positive effect on colorization. We also perform three ablation tests:
Baseline + Parsing, Baseline + Classifier and our method.

Table 3. Ablation experiments Method | LPIPS↓ | PSNR↑ | SSIM↑
---|---|---|---
ChromaGAN | 0.123 | 27.093 | 0.946
Baseline+Parsing | 0.121 | 28.992 | 0.948
Baseline+Classifier | 0.119 | 29.828 | 0.951
HistoryNet | 0.107 | 30.585 | 0.959

###  5.4. Qualitative comparisons

Effect of fine grained semantic parsing There exist kinds of image
segmentation methods in the literatures (Gong et al., 2018; Chen et al., 2017;
Zhou et al., 2020; Zhou et al., 2019; Li et al., 2014). In this paper, we use
Human Parsing (Gong et al., 2018) and Deeplab-v3 (Chen et al., 2017)
separately for semantic segmentation. Deeplab-v3 (Chen et al., 2017) only
separate persons and background, but can’t focus on details of persons’ each
part, such as face and hands. Therefore, we adopt instance-level human parsing
(Gong et al., 2018) for semantic segmentation, which is focus on recognizing
each semantic part for example arms and hair. Due to the limit of equipment
and time, we separately adjust 75,837 images of human parsing and Deeplab-v3
(Chen et al., 2017) manually and use them as the ground truth for parsing
network. Through training on HistoryNet, it can be seen in Figure 6 that human
parsing focus on fine grained semantic parsing so its segmentation accuracy is
better than semantic segmentation. Because of this, the result of using human
parsing as ground truth training is better than that of Deeplab-v3. For
example, in the third line of the Figure 6, the person’s hands are separated
by Human Parsing that the right hand of the person is light green, the left
one is light blue. By taking human parsing as the ground truth of parsing
network, parsing network can accurately guide the acquisition and colorization
of color information of each part. Therefore, the boundary of Parsing Result
is more clear and the colorization effect is closer to Original images.
However, Semantic Result can not achieve accurate segmentation, which leads to
the color fusion of hands and background and presents the same green of the
background.

Figure 6. The picture shows that the segmentation of human parsing is more
accurate than semantic segmentation.

Ablation experiments In HistoryNet, there are two main submodules: parsing and
classifier subnetworks, so we do the corresponding ablation experiments. As
shown in Figure 7, baseline consists of $G_{0}$, $G_{1}$, $G_{2}$ and $D_{1}$
in Figure 2 of HistoryNet structure. From the Figure 7, we can see that
parsing can better segment the boundary, so as to make the colorization more
accurate. For example, in the first column, Baseline+Parsing can accurately
separate the two clothes and the boundary of the clothes is more precise,
while Baseline+Classifier does not perform due to the lack of fine grained
semantic parsing of person. Although the parsing results have better boundary
of person, the color of the images is not correct and nature, such as the
third column in the figure. Compared with Baseline+Classifier,
Baseline+Parsing is not classified, so the color of the neck is not natural.

Figure 7. Some qualitative comparisons of ablation experiments. Parsing
submodule can obtain the clear boundary through fine grained semantic parsing;
Classifier submodule can help choose correct color for colorization.

Results on old photos We design MHMD suitable for colorizing historical
images, especially military uniforms and suits of historical images. In
addition, our method can restore old photos, remove the background noise and
colorize the yellowing background to the normal color. As shown in Figure 8.
We also colorize some legacy black and white images. As shown in the Figure 9,
we can see our method is still applicable and has good effect for black and
white photos.

Figure 8. HistoryNet can correct the color and ﬁnally achieve a better
colorization result. For example, this historical photo appears yellow and
green as a whole. Figure 9. HistoryNet also apply for some legacy black and
white images.

Comparisons with state-of-the-art Figure 4 shows the experimental results of
the five best current methods. It can be seen from the Figure 4 that our
method has a good performance on the accuracy of the image color and boundary
of each part, while other methods have problems such as inaccurate colorizing
of the images and discontinuous lumpiness of the color on the clothes. From
the first and fourth line of Figure 4, we can see that each element (such as
clothes, face etc.) in our colorization results have a clear boundary and
achieve the consistency within the region block, that is, the clothes part is
of the same color, From this comparative experiment, we can see the advantages
of designing parsing and classifier submodules in HistoryNet. Parsing
subnetwork can solve the problem of boundary segmentation and classifier
subnetwork can achieve the consistency and continuity of the overall coloring
of the persons clothing.

In addition, our method is not only suitable for the colorization of military
uniform, but also for the colorization of other natural landscapes and
characters, as shown in the Figure 5.

##  6\. Conclusions

In this paper, we propose a new HistoryNet architecture, which contains
parsing, classification and classifier subnetworks. Semantic parsing
subnetwork can help the colorization boundary more accurate. Classifier
subnetwork can help choose correct color. In addition, we propose a dataset
called MHMD that focus on the real gray historical images. To the best of our
knowledge, the proposed MHWD dataset is the largest dataset of historical
image colorization. The MHWD can be accessed by request. Through relevant
qualitative and quantitative comparison, our method is superior to the state-
of-the-art colorization network in LPIPS, PSNR, SSIM. Another purpose of our
work is to inspire more researchers to make the gray image colorization
technologies more useful in historical image/video colorization. In the
future, related research methods will also be used in video coloring.

## Acknowledgements

We thank the ACs, reviewers, and the annotators of our dataset such as Jisen
Huang and Xuntao Zhou. This work is partially supported by the National
Natural Science Foundation of China (62072014), the Beijing Natural Science
Foundation (L192040), and the Advanced Discipline Construction Project of
Beijing Universities (20210041Z0401).

## References

  * (1)
  * Antic (2019) Jason Antic. 2019\.  DeOldify.  https://github.com/jantic/DeOldify.
  * Arjovsky et al. (2017) Martin Arjovsky, Soumith Chintala, and Léon Bottou. 2017\.  Wasserstein gan.  _arXiv preprint arXiv:1701.07875_ (2017).
  * Bahng et al. (2018) Hyojin Bahng, Seungjoo Yoo, Wonwoong Cho, David Keetae Park, Ziming Wu, Xiaojuan Ma, and Jaegul Choo. 2018.  Coloring with words: Guiding image colorization through text-based palette generation. In _Proceedings of the european conference on computer vision (eccv)_. 431–447.
  * Caesar et al. (2018) Holger Caesar, Jasper Uijlings, and Vittorio Ferrari. 2018\.  Coco-stuff: Thing and stuff classes in context. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 1209–1218.
  * Cao et al. (2017) Yun Cao, Zhiming Zhou, Weinan Zhang, and Yong Yu. 2017\.  Unsupervised diverse colorization via generative adversarial networks. In _Joint European conference on machine learning and knowledge discovery in databases_. Springer, 151–166.
  * Chen et al. (2018) Jianbo Chen, Yelong Shen, Jianfeng Gao, Jingjing Liu, and Xiaodong Liu. 2018.  Language-based image editing with recurrent attentive models. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 8721–8729.
  * Chen et al. (2017) Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L Yuille. 2017\.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  _IEEE transactions on pattern analysis and machine intelligence_ 40, 4 (2017), 834–848.
  * Chen et al. (2016) X. Chen, Y. Duan, R. Houthooft, J. Schulman, I. Sutskever, and P. Abbeel. 2016\.  InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Adversarial Nets. In _Neural Information Processing Systems (NIPS)_.
  * Cheng et al. (2015) Zezhou Cheng, Qingxiong Yang, and Bin Sheng. 2015.  Deep colorization. In _Proceedings of the IEEE International Conference on Computer Vision_. 415–423.
  * Ci et al. (2018) Yuanzheng Ci, Xinzhu Ma, Zhihui Wang, Haojie Li, and Zhongxuan Luo. 2018.  User-guided deep anime line art colorization with conditional adversarial networks. In _Proceedings of the 26th ACM international conference on Multimedia_. 1536–1544.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. 2009\.  Imagenet: A large-scale hierarchical image database. In _2009 IEEE conference on computer vision and pattern recognition_. Ieee, 248–255.
  * Deshpande et al. (2015) Aditya Deshpande, Jason Rock, and David Forsyth. 2015\.  Learning large-scale automatic image colorization. In _Proceedings of the IEEE International Conference on Computer Vision_. 567–575.
  * Furusawa et al. (2017) Chie Furusawa, Kazuyuki Hiroshiba, Keisuke Ogaki, and Yuri Odagiri. 2017.  Comicolorization: semi-automatic manga colorization.  In _SIGGRAPH Asia 2017 Technical Briefs_. 1–4.
  * Gong et al. (2018) Ke Gong, Xiaodan Liang, Yicheng Li, Yimin Chen, Ming Yang, and Liang Lin. 2018\.  Instance-level human parsing via part grouping network. In _Proceedings of the European Conference on Computer Vision (ECCV)_. 770–785.
  * Gulrajani et al. (2017) Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. 2017\.  Improved training of wasserstein gans. In _Advances in neural information processing systems_. 5767–5777.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * Hensman and Aizawa (2017) Paulina Hensman and Kiyoharu Aizawa. 2017.  cGAN-based manga colorization using a single training image. In _2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR)_ , Vol. 3. IEEE, 72–77.
  * Iizuka et al. (2016) Satoshi Iizuka, Edgar Simo-Serra, and Hiroshi Ishikawa. 2016\.  Let there be color! Joint end-to-end learning of global and local image priors for automatic image colorization with simultaneous classification.  _ACM Transactions on Graphics (ToG)_ 35, 4 (2016), 1–11.
  * Ironi et al. (2005) Revital Ironi, Daniel Cohen-Or, and Dani Lischinski. 2005\.  Colorization by Example.. In _Rendering Techniques_. Citeseer, 201–210.
  * Isola et al. (2017) Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros. 2017.  Image-to-image translation with conditional adversarial networks. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 1125–1134.
  * Kantorovitch (1958) Leonid Kantorovitch. 1958\.  On the translocation of masses.  _Management Science_ 5, 1 (1958), 1–4.
  * Kim et al. (2019) Hyunsu Kim, Ho Young Jhoo, Eunhyeok Park, and Sungjoo Yoo. 2019\.  Tag2pix: Line art colorization using text tag with secat and changing loss. In _Proceedings of the IEEE International Conference on Computer Vision_. 9056–9065.
  * Larsson et al. (2016) Gustav Larsson, Michael Maire, and Gregory Shakhnarovich. 2016\.  Learning representations for automatic colorization. In _European Conference on Computer Vision_. Springer, 577–593.
  * Li et al. (2014) Qing Li, Xiaowu Chen, Yafei Song, Yu Zhang, Xin Jin, and Qinping Zhao. 2014\.  Geodesic Propagation for Semantic Labeling.  _IEEE Trans. Image Process._ 23, 11 (2014), 4812–4825.  https://doi.org/10.1109/TIP.2014.2358193
  * Liu et al. (2017) Chenxi Liu, Zhe Lin, Xiaohui Shen, Jimei Yang, Xin Lu, and Alan Yuille. 2017\.  Recurrent multimodal interaction for referring image segmentation. In _Proceedings of the IEEE International Conference on Computer Vision_. 1271–1280.
  * Manjunatha et al. (2018) Varun Manjunatha, Mohit Iyyer, Jordan Boyd-Graber, and Larry Davis. 2018.  Learning to color from language.  _arXiv preprint arXiv:1804.06026_ (2018).
  * Mouzon et al. (2019) Thomas Mouzon, Fabien Pierre, and Marie-Odile Berger. 2019\.  Joint CNN and Variational Model for Fully-automatic Image Colorization. In _International Conference on Scale Space and Variational Methods in Computer Vision_. Springer, 535–546.
  * Nazeri et al. (2018) Kamyar Nazeri, Eric Ng, and Mehran Ebrahimi. 2018.  Image colorization using generative adversarial networks. In _International conference on articulated motion and deformable objects_. Springer, 85–94.
  * Odena et al. (2017) Augustus Odena, Christopher Olah, and Jonathon Shlens. 2017\.  Conditional Image Synthesis with Auxiliary Classifier GANs _(Proceedings of Machine Learning Research, Vol. 70)_ , Doina Precup and Yee Whye Teh (Eds.). PMLR, International Convention Centre, Sydney, Australia, 2642–2651.  http://proceedings.mlr.press/v70/odena17a.html
  * Ronneberger et al. (2015) Olaf Ronneberger, Philipp Fischer, and Thomas Brox. 2015\.  U-net: Convolutional networks for biomedical image segmentation. In _International Conference on Medical image computing and computer-assisted intervention_. Springer, 234–241.
  * Sato et al. (2014) Kazuhiro Sato, Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa. 2014.  Reference-based manga colorization by graph correspondence using quadratic programming.  In _SIGGRAPH Asia 2014 Technical Briefs_. 1–4.
  * Simonyan and Zisserman (2014) Karen Simonyan and Andrew Zisserman. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ (2014).
  * Su et al. (2020) Jheng-Wei Su, Hung-Kuo Chu, and Jia-Bin Huang. 2020\.  Instance-aware Image Colorization. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 7968–7977.
  * Sun et al. (2019) Tsai-Ho Sun, Chien-Hsun Lai, Sai-Keung Wong, and Yu-Shuen Wang. 2019.  Adversarial Colorization Of Icons Based On Structure And Color Conditions.  _arXiv preprint arXiv:1910.05253_ (2019).
  * Villani (2008) Cédric Villani. 2008\.  _Optimal transport: old and new_. Vol. 338.  Springer Science & Business Media.
  * Vitoria et al. (2020a) Patricia Vitoria, Lara Raad, and Coloma Ballester. 2020a.  ChromaGAN: Adversarial Picture Colorization with Semantic Class Distribution. In _The IEEE Winter Conference on Applications of Computer Vision_. 2445–2454.
  * Vitoria et al. (2020b) Patricia Vitoria, Lara Raad, and Coloma Ballester. 2020b.  ChromaGAN: Adversarial Picture Colorization with Semantic Class Distribution. In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_.
  * Welsh et al. (2002) Tomihisa Welsh, Michael Ashikhmin, and Klaus Mueller. 2002\.  Transferring color to greyscale images. In _Proceedings of the 29th annual conference on Computer graphics and interactive techniques_. 277–280.
  * Xian et al. (2018) Wenqi Xian, Patsorn Sangkloy, Varun Agrawal, Amit Raj, Jingwan Lu, Chen Fang, Fisher Yu, and James Hays. 2018\.  Texturegan: Controlling deep image synthesis with texture patches. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 8456–8465.
  * Yoo et al. (2019) Seungjoo Yoo, Hyojin Bahng, Sunghyo Chung, Junsoo Lee, Jaehyuk Chang, and Jaegul Choo. 2019\.  Coloring with limited data: Few-shot colorization via memory augmented networks. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 11283–11292.
  * Zhang et al. (2017a) Lvmin Zhang, Yi Ji, Xin Lin, and Chunping Liu. 2017a.  Style transfer for anime sketches with enhanced residual u-net and auxiliary classifier gan. In _2017 4th IAPR Asian Conference on Pattern Recognition (ACPR)_. IEEE, 506–511.
  * Zhang et al. (2018) Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang. 2018.  The unreasonable effectiveness of deep features as a perceptual metric. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 586–595.
  * Zhang et al. (2017b) Richard Zhang, Jun-Yan Zhu, Phillip Isola, Xinyang Geng, Angela S Lin, Tianhe Yu, and Alexei A Efros. 2017b.  Real-time user-guided image colorization with learned deep priors.  _arXiv preprint arXiv:1705.02999_ (2017).
  * Zhao et al. (2019) Jiaojiao Zhao, Jungong Han, Ling Shao, and Cees GM Snoek. 2019\.  Pixelated Semantic Colorization.  _International Journal of Computer Vision_ (2019), 1–17.
  * Zhou et al. (2014) Bolei Zhou, Agata Lapedriza, Jianxiong Xiao, Antonio Torralba, and Aude Oliva. 2014\.  Learning deep features for scene recognition using places database. In _Advances in neural information processing systems_. 487–495.
  * Zhou et al. (2020) Quan Zhou, Yu Wang, Yawen Fan, Xiaofu Wu, Suofei Zhang, Bin Kang, and Longin Jan Latecki. 2020.  AGLNet: Towards real-time semantic segmentation of self-driving images via attention-guided lightweight network.  _Appl. Soft Comput._ 96 (2020), 106682.  https://doi.org/10.1016/j.asoc.2020.106682
  * Zhou et al. (2019) Quan Zhou, Yu Wang, Jia Liu, Xin Jin, and Longin Jan Latecki. 2019.  An open-source project for real-time image semantic segmentation.  _Sci. China Inf. Sci._ 62, 12 (2019), 227101.  https://doi.org/10.1007/s11432-019-2685-1
  * Zou et al. (2019) Changqing Zou, Haoran Mo, Chengying Gao, Ruofei Du, and Hongbo Fu. 2019.  Language-based colorization of scene sketches.  _ACM Transactions on Graphics (TOG)_ 38, 6 (2019), 1–16.
  * Zou et al. (2018) Changqing Zou, Qian Yu, Ruofei Du, Haoran Mo, Yi-Zhe Song, Tao Xiang, Chengying Gao, Baoquan Chen, and Hao Zhang. 2018.  Sketchyscene: Richly-annotated scene sketches. In _European Conf. on Comp. Vis. (ECCV)_. 421–436.


Indian Institute of Technology, Kanpur, India and<EMAIL_ADDRESS>Debarsho
Sannyasi [100]G.2.2 Graph Theory 1

# Improved Approximation Algorithms for
Weighted Edge Coloring of Graphs

Debarsho Sannyasi

###### Abstract

We study _weighted edge coloring of graphs_ , where we are given an undirected
edge-weighted general multi-graph $G:=(V,E)$ with weights
$w:E\rightarrow[0,1]$. The goal is to find a proper weighted coloring of the
edges with as few colors as possible. An edge coloring is called a proper
weighted coloring if the sum of the weights of the edges incident to a vertex
of any color is at most one.

In the online setting, the edges are revealed one by one and have to be
colored irrevocably as soon as they are revealed. We show that $3.39m+o(m)$
colors are enough when the maximum number of neighbors of a vertex over all
the vertices is $o(m)$ and where $m$ is the maximum over all vertices of the
minimum number of unit-sized bins needed to pack the weights of the incident
edges to that vertex. We also prove the tightness of our analysis. This
improves upon the previous best upper bound of $5m$ by Correa and Goemans
[STOC 2004].

For the offline case, we show that for a simple graph with edge disjoint
cycles, $m+1$ colors are sufficient and for a multi-graph tree, we show that
$1.693m+12$ colors are sufficient.

###### keywords:

Edge coloring, Bin packing, Clos networks, Online algorithms, Graph
algorithms.

###### category:

##  1 Introduction

Edge-coloring problem has been one of the foundational problems in graph
theory and discrete mathematics since its appearance in 1880 [21] in
connection with the four-color problem. In this paper, we study _weighted edge
coloring problem_ which generalizes both unweighted edge-coloring and
classical bin packing problem. In the online version of the _weighted edge
coloring problem_ for general undirected multi-graphs, we are given a graph
$G:=(V,E)$. At each instance, a new edge $e=(u,v)$ is revealed, and we need to
assign a color to this edge at this instant itself. Colors assigned to edges
can not be changed in future. Weight of each edge $\in[0,1]$. Let $m$ be the
maximum over all vertices of the minimum number of unit-sized bins needed to
pack the weights of the incident edges to that vertex. We need to color the
edges while maintaining the condition that the sum of weights of edges
incident to a vertex and colored with same color must not exceed 1 at any
moment. This is called a _proper_ coloring of the graph. Our overall objective
is to minimize the number of colors used.

The problem specially finds prominence in 3-stage Clos networks [7] which
reduces to _weighted edge coloring of bipartite graphs_. We refer the reader
to Correa and Goemans [9] for detailed discussion of this reduction and
connection with Clos networks.

For a given edge weighted undirected graph $G:=(V,E)$ with all edge weights
$\in[0,1]$, consider the following notations which will be followed in this
paper-

  * •

m := $\max_{v\in V}\left\\{\textit{Minimum number of unit sized bins required
to pack all the edges incident to $v$}\right\\}$

  * •

n := $\max_{v\in V}\left\\{\textit{Sum of weights of all edges incident to
$v$}\right\\}$

For the offline weighted edge coloring problem, Feige and Singh [11] proved a
$\lceil 2.25n\rceil$ upper bound for bipartite graphs. Later Khan and Singh
[18] proved an upper bound of $\lceil 2.2223m\rceil$ for bipartite graphs.
Khan [17] also showed that $2.2m$ colors are sufficient when all items have
weights $>1/4$. The current best lower bound for the offline version is
$1.25m$ for bipartite graphs. For online weighted edge coloring, Correa and
Goemans [9] proved an upper bound of $5m$ which improved upon $5.75m$ by Gao
and Hwang [13]. The best known lower bound for the online version is $3m-2$ by
Tsai, Wang, and Hwang [22].

###  1.1 Our contributions

We design a new algorithm for this problem and prove that $3.39m+o(m)$ colors
are sufficient if the maximum number of neighbors of a vertex over all
vertices is $o(m)$. This asymptotically improves upon the previous best $5m$
[9]. We achieve this improvement using _HARMONIC M_ (with $M=12$) online bin
packing algorithm [19] as a routine in our main algorithm. Most of the
previous results, both in the offline and online settings used $FIRST$-$FIT$
instead. Along with that, we present an instance to show that our analysis is
tight for our algorithm.
For the offline version of the problem, we prove that $m+1$ colors are
sufficient for an undirected simple (no multi-edges between 2 vertices) graph
with edge disjoint cycles and $1.693m+12$ colors are sufficient for undirected
multi-graph trees.

###  1.2 Related Works

When all the graph is a bipartite graph with only two vertices then the
problem reduces to classical bin packing problem, which is well-studied in
both offline [10, 16, 14] and online setting [3, 1, 2]. There are many other
related generalizations of bin packing [5, 4, 12]. We refer the readers to [8,
6] for a survey on bin packing. For results on edge-coloring, we refer the
readers to [20, 15].

##  2 Preliminaries

In our algorithms presented in this paper, we either use the _NEXT-FIT_ or the
$HARMONIC_{M}$ online bin packing algorithms to assign colors to the edges. We
present these subroutines briefly here along with few results which will be
used in our analysis.

###  2.1 NEXT-FIT algorithm

$NEXT$-$FIT$ is an online bin packing algorithm in which items of weight
$\in[0,1]$ arrive one by one and we need to fit it into an unit-sized bin at
the instant of arriving itself. We fit items of size $\rightarrow[0,1]$ into
unit-sized bins, in which at any instant we have a single open/active bin
where we can place the incoming items. Also, let $m$ be the optimal number of
unit-sized bins required for all the items known at hindsight. Let at an
instant, item $i$ appear and we have an open bin $b$. If $i$ fits into $b$,
then fit $i$ in $b$. Else, close the bin $b$ and take a new fresh bin as the
current open bin. Closed bins are never used again. Place $i$ into the new
bin.

######  Lemma 2.1.

$2m-1$ bins are sufficient using $NEXT$-$FIT$.

######  Proof 2.2.

Let the current open bin be $b_{1}$ which already has $c$ weight in it and at
this instant a new item $i$ of weight $w_{i}$ arrives. If a new bin is
required for accommodating item $i$, then we must have $c+w_{i}>1$, else a new
bin won’t be required. Let the new bin be $b_{2}$. We then close the current
bin $b_{1}$ and we fit the item $i$ in $b_{2}$. The final weight in $b_{2}$
will be $\geq w_{i}$. So, the sum of weights in $b_{1}$ and $b_{2}$ is atleast
$c+w_{i}>1$. In the same way, in general the sum of final weights of any 2
consecutive bins is greater than 1. Now assume on contradiction, that at some
instant, there is a requirement for opening the $2m^{th}$ bin, then the total
weight of all the items which have already arrived will be greater than $m$,
which is a contradiction.

###  2.2 HARMONICM algorithm

We refer reader to [19] to know more about _HARMONIC M_ algorithm.
Essentially, here we have $M$ types/categories of items based on their size
and at any instant we have $M$ open/active bins, one for each type to place
the incoming items of that type. If the incoming item belongs to type $i$,
then it is placed in the bin designated for type $i$ items. If it can not be
placed, then the current bin of type $i$ is closed and a new bin of type $i$
is formed and the item is placed in it. Any closed bins are never used again.

######  Lemma 2.3.

If $M=12$, then $1.6926m\approx 1.693m$ bins are sufficient [19].

###  2.3 Definitions

Now we define some terminologies which we would use in our algorithms and
their analysis. From now we always take $M=12$ if we talk about the algorithm
which uses _HARMONIC M_. Also, terms like bins and colors are used
interchangeably. Coloring an edge with a color is analogous to fitting an item
in a bin.

######  Definition 2.4.

(Simple graphs and Multi-graphs): An undirected graph $G$ is called a simple
graph if there is atmost 1 edge between any pair of vertices. An undirected
multi-graph $G$ can have multiple edges between any pair of vertices.

######  Definition 2.5.

(Open, Closed and Empty colors):

When using _NEXT-FIT_ , we maintain a single active color between any pair of
neighbouring vertices at all time. So, if a vertex has $r$ neighbours at an
instant, then it will have $r$ active colors, one with each neighbour. This
active color is also called the open color between a pair of neighbouring
vertices. Let at an instant, an edge $e$ arrive between vertices $u$ and $v$.
We first try to color $e$ with the current open color between $u$ and $v$. If
it violates the condition of proper coloring, then we close the current open
color between $u$ and $v$ and create a new open color between them. If $e$ is
the first edge between $u$ and $v$, then we introduce a new open color between
them and assign that color to $e$. The colors which are closed in this manner
are called closed colors and they are never used again. We can say that all
these colors are taken from a set/palette. Our main goal is to provide an
upper bound to the sufficient size of the palette. Colors which are neither
open nor closed are called empty colors. Empty colors are part of the palette
and act like candidates for being an open color in the future.

When using _HARMONIC M_, the definitions are very similar as above. The only
change is that now at any instant, between any two neighbouring vertices, we
have $M=12$ open colors between them corresponding to each type/category
instead of just 1 open color as in _NEXT-FIT_. So, if a vertex has $r$
neighbours at an instant, then it will have $Mr$ active colors, $M$ with each
neighbour. Let at an instant, edge $e=(u,v)$ arrive which is a type $i$ edge.
We first try to color $e$ with the type $i$ open color between $u$ and $v$. If
this violates the condition for proper coloring, then we close the type $i$
color between $u$ and $v$ and introduce a new type $i$ color between $u$ and
$v$. If edge $e$ is the first type $i$ edge between $u$ and $v$, then we
introduce a type $i$ color between $u$ and $v$ in order to color the edges of
type $i$ between $u$ and $v$.

##  3 Online Weighted Edge Coloring

Reiterating the online _Weighted edge coloring problem_ , let $G:=(V,E)$ be
the underlying undirected multi-graph. Each edge appear/arrive one by one in
an online manner. Each edge has weight $w\rightarrow[0,1]$. $m$ is the maximum
over all vertices of the minumum number of unit-sized bins needed to pack the
weights of the incident edges to that vertex. At an instant, let edge $e\in E$
of weight $w_{e}$ arrive. We need to color $e$ such that the
invariant/condition that sum of weights of edges incident to any vertex and
colored with the same color must not exceed $1$ is maintained at all times. We
wish to find an upper bound for the sufficient number of colors required for
the above procedure. Essentially, we present $two$ algorithms. One uses _NEXT-
FIT_ online bin packing procedure in which we show that $4m+2t$ colors are
enough, where $t$ is the maximum number of neighbors of a vertex over all
vertices. The other algorithm uses _HARMONIC M_ online bin packing procedure
in which we show that $3.39m+24t$ colors are enough (taking $M=12$),
definition of $t$ being the same. So, if $t=o(m)$ we can achieve an asymptotic
competitive ratio of $4$ and $3.39$ respectively beating the previous best 5
as mentioned before. In our analysis we take value of $M$ to be $12$. As we
will see both the algorithms and their analysis are very similar.

###  3.1 Algorithm

We first present our algorithm which uses $NEXT$-$FIT$. Let $t$ be the maximum
number of neighbours of a vertex over all vertices. We have a palette $P$ of
$4m+2t$ colors numbered from 1 to $4m+2t$.

Algorithm 1 Algorithm for online weighted edge coloring for undirected multi-
graphs using _NEXT-FIT_

Let at an instant, edge $e=(u,v)$ arrive. If $e$ is the first edge appearing
between $u$ and $v$, then choose the least numbered color $c^{\prime}$ from
palette $P$ which is empty for both $u$ and $v$ and designate it as the open
color between them. Color $e$ with $c^{\prime}$. Else, let the current open
color between vertices $u$ and $v$ at this instant be $c$.

1: If color $c$ is the current open color between $u$ and $v$, and edge
$(u,v)$ can be colored with $c$, then color edge $(u,v)$ with $c$.

2: Else, close color $c$. Find the least numbered color $c^{\prime}$ from
palette $P$ which is an empty color of both $u$ and $v$. It is now the open
color between $u$ and $v$. Color $(u,v)$ with $c^{\prime}$.

Now we present our algorithm which uses $HARMONIC_{M}$. Let $t$ be the maximum
number of neighbours of a vertex over all vertices. We have a palette $P$ of
$3.39m+24t$ colors numbered from 1 to $3.39m+24t$. This algorithm is very
similar to the previous algorithm. The only difference is that now we have $M$
types/categories of edges based on its weight which we have to take into
account. For each type we have an open color between a pair of neighbouring
vertices.

Algorithm 2 Algorithm for online weighted edge coloring for undirected multi-
graphs using _HARMONIC M_

Let at an instant, edge $e=(u,v)$ of type $i$ arrive. If $e$ is the first edge
of type $i$ appearing between $u$ and $v$, then choose the least numbered
color $c^{\prime}$ from palette $P$ which is empty for both $u$ and $v$ and
designate it as the open color of type $i$ between them. Color $e$ with
$c^{\prime}$. Else, let the current open color of type $i$ between vertices
$u$ and $v$ at this instant be $c$.

1: If color $c$ is the current open color of type $i$ between $u$ and $v$, and
edge $(u,v)$ can be colored with $c$, then color edge $(u,v)$ with $c$.

2: Else, close color $c$. Find the least numbered color $c^{\prime}$ from
palette $P$ which is an empty color of both $u$ and $v$. It is now the open
color of type $i$ between $u$ and $v$. Color $(u,v)$ with $c^{\prime}$.

In the next section, we would prove that palette size of $4m+2t$ and
$3.39m+24t$ is sufficient for the algorithms using $NEXT$-$FIT$ and
$HARMONIC_{M}$ respectively.

###  3.2 Analysis

Consider the following lemmas.

######  Lemma 3.1.

In an online bin packing instance, if we partition all items into $t$ non-
empty types, and introduce a requirement that two items of different types
cannot be packed in a single bin, then $2m-1+t$ bins are sufficient using
NEXT-FIT. Also, at all times, we have exactly $t$ open bins, thus there can be
at most $2m-1$ closed bins at any instant.

######  Proof 3.2.

Assign $t$ open bins at the start, named $c_{1},c_{2},...,c_{t}$, where bin
$c_{i}$ would accommodate items of type $i$. On the arrival of an item of type
$i$, if the current bin $c_{i}$ is unable to fit the item, then close the bin
$c_{i}$, and replace it with another new bin, which will now be named $c_{i}$.
Place the item in this new bin of type $i$. Carry on this procedure for all
items.
At last there will be $t$ open bins, and the number of closed bins will be
$<2m$. Otherwise, if number of closed bins is $\geq 2m$, then it would be a
contradiction to the $2m-1$ bound guaranteed by Lemma 2.1. This is because
here we are essentially following the same rules as standard _NEXT-FIT_ , the
only difference is upon arrival of an item of type $i$, we are checking the
bin $c_{i}$ instead of a common open bin for all items in standard _NEXT-FIT_.
Using the standard _NEXT-FIT_ , first produce the items of type 1, then type 2
and so on till type $t$. So, if $\geq 2m$ closed bins are required, then in
this case also $\geq 2m$ will be required contradicting Lemma 2.1. Thus,
overall we need at most $2m-1+t$ different bins for all items under this
scenario. In other words, at most $2m-1$ closed bins as we have exactly $t$
open bins.

######  Corollary 3.3.

Using $HARMONIC_{M}$ (with $M=12$) in the same scenario of Lemma 3.1,
$1.693m+12t$ bins are sufficient. More specifically, there would be $12t$ open
bins at any instant, and there would be at most $1.693m$ closed bins at any
instant using Lemma 2.3.

Let $t$ be the maximum number of neighbors of a vertex over all vertices of
$G:=(V,E)$. Now we will first present the analysis for the algorithm which
uses $NEXT$-$FIT$ and prove our claim that $4m+2t$ colors are sufficient. The
bound using $HARMONIC_{M}$ would easily follow by just replacing $2m$ with
$1.693m$ and $t$ with $12t$ in the following analysis.

######  Lemma 3.4.

For any vertex $w$ of the graph, the number of closed bins used by $w$ is at
most $2m-1$ at any instant.

######  Proof 3.5.

The number of open bins is clearly at most $t$ because $w$ has at most $t$
neighbours. So, specifically, we need to show that number of closed bins used
by $w$ is at most $2m-1$. Actually, this follows directly from Lemma 3.1. We
can relate the $t$ types in Lemma 3.1 with $t$ neighbours here, and the items
with the edges.

We will prove it by contradiction. Let at an instant, edge $e$ incident to $w$
arrive which causes it’s $2m^{th}$ bin to close in order to fit edge $e$. The
claim is that such an instant can $never$ occur. Let suppose such an incident
indeed occur. Now, take all the items which were previously packed in the $2m$
closed bins and the item $e$. Then, imagine producing all these items (i.e.
edges) in the same order as they arrive in the original graph scenario, and
try to pack these items using _NEXT-FIT_ along with the condition that there
are $t$ types (corresponding to $t$ neighbour vertices) and items of 2
different types cannot be placed together. We would then have to close the
$2m^{th}$ when the item $e$ arrives leading to $2m$ closed bins, which is a
contradiction to Lemma 3.1.

Now we arrive at our main theorem.

######  Theorem 3.6.

For online edge arrival scenario of proper weighted coloring of graphs,
$1.693\cdot 2m+24t$ colors are sufficient using $HARMONIC_{M}$ (with $M=12$)
and $4m+2t$ colors are sufficient using $NEXT$-$FIT$ algorithm for a proper
coloring solution. $t$ is the maximum number of neighbours over all the
vertices of the graph and $m$ is the maximum over all vertices of minimum
number of bins required to pack all edges incident to a vertex such that sum
of weights packed in each bin $\leq 1$.

######  Proof 3.7.

When using _NEXT-FIT_ , let at an instant, edge $e=(u,v)$ arrive, and let
$g_{1}$ = number of closed bins used by $u$ and $g_{2}$ = number of closed
bins used by $v$ and let bin $c$ be the current open bin between $u$ and $v$,
all just before arrival of edge $e$.

If edge $e$ is able to fit in bin $c$, then fit edge $e$ in bin $c$ and
continue. Else, close bin $c$. Replace it with a new bin and fit edge $e$ in
the new bin.

Now, we need to prove that if we have a palette of $4m+2t$ colors, then the
new bin can be found from this palette without any violations. In other words,
$4m+2t$ colors are sufficient. From Lemma 3.4, we have $g_{1}$ $<$ $2m$ and
$g_{2}$ $<$ $2m$. Vertex $u$ has at most $t$ open bins and vertex $v$ has at
most $t$ open bins just before arrival of $e$. So, just before arrival of $e$,
the sum of closed and open bins for both vertices $u$ and $v$ is
$g_{1}+g_{2}+2t$ $\leq$ $2m-1+2m-1+2t=4m-2+2t$ (It is indeed $4m-2+2t-1$
because of the common open bin between $u$ and $v$). So, given our pool of
$4m+2t$ colors, we will always be able to find a new color without any
violations to either vertices. Also, $u$ and $v$ are the only vertices where a
violation can occur at this step and thus we care about only these.

If a new bin is selected, then $g_{1}$ and $g_{2}$ both increments by $1$ but
the number of open bins for both remains at most $t$. Though $g_{1}$ and
$g_{2}$ increase by $1$, it is guaranteed that they never reach $2m$. Because
it would be a violation to Lemma 3.4 as then $g_{1}=2m$ $>$ $2m-1$,
contradicting Lemma 3.4.

In other words, the above arguments imply that if a specific vertex has $2m-1$
closed bins, then none of it’s $t$ open bins will be forced to close. Because
a bin is closed only when another new bin in opened and thus leading to a
contradiction of Lemma 3.4.

Finally, we can say that $4m+2t$ colors are enough (indeed $4m-1+2t$ colors
are enough). The bound $1.693\cdot 2m-1+24t$ directly follows for
$HARMONIC_{M}$ (with $M=12$) with the exact same arguments as above, just
replace $t$ with $12t$ and $2m$ with $1.693m$. Also as described in Algorithm
2, take into account the type of edge arriving. An edge $e=(u,v)$ of type $i$
must be fit into the open bin of type $i$ between $u$ and $v$.

######  Corollary 3.8.

From Theorem 3.6 we get, if $t=o(m)$, we have a competitive ratio of
$1.693\cdot 2<3.39$ using $HARMONIC_{M}$ (with $M=12$) and $4$ using
$NEXT$-$FIT$.
In other words, the new best asymptotic competitive ratio is $3.39$, an
improvement over previous best of $5$.

###  3.3 Tightness of Analysis

The number $1.6910$ is the greatest lower bound for the worst-case performance
ratio of any $O(1)$-space online bin packing algorithm [19]. For $M=12$, the
best bound is $\approx 1.6926<1.693$ [19]. Now, we would be constructing an
example where at least $1.693\cdot 2=3.386m\approx 3.39m$ colors are required
when using our $HARMONIC_{M}$ coloring algorithm with $M=12$. In other words,
where the competitive ratio is $3.39$. $3.39$ is chosen for simplicity in
expressing the procedure, else following the below construction idea,
competitive ratio very close to $1.691\cdot 2$ can be achieved by increasing
the value of $M$.

Choose positive integers $\epsilon$ and $m$ such that $m\approx 10^{20}$,
$\frac{m}{\epsilon}\approx 10^{10}$, $\frac{\epsilon}{12}\approx 10^{10}$ and
$1.693m,\frac{1.693m}{\epsilon}$ are integers. One thing to note here is that
on the arrival of an edge $e=(u,v)$, if $e$ can not fit in the current open
bin between $u$ and $v$, then the algorithm should provide a deterministic way
of choosing the next open bin between them. The way is that the algorithm
chooses the least numbered bin possible as the next new open bin between $u$
and $v$. Below are the steps of construction of the tight example taking
$M=12$.

  * •

Let $u_{1}$ and $v_{1}$ be the first two vertices. Introduce edges only
between them such that the number of closed bins for them be
$1.693m-\epsilon$. Choose these bins in a contiguous manner starting from the
first bin. This can be achieved because we have the bound equal to $1.693m$ as
stated above. Also note that due to the lower bound, the number of closed bins
for a vertex can be at least up to $1.691m-1$. (may be even more depending
upon the value of $M$).

  * •

Like this form another $\frac{1.693m}{\epsilon}-1$ pairs of vertices $u_{i}$
and $v_{i}$ for $i=2,3,4...,\frac{1.693m}{\epsilon}$. So, now we have
$\frac{1.693m}{\epsilon}$ pairs of vertices, with each pair having the first
$1.693m-\epsilon$ bins as closed bins between them.

  * •

Now we introduce a new vertex $w$ with multiple edges between vertices $u_{1}$
and $w$ such that the number of closed bins needed by $w$ is $\epsilon$. Now
$w$ can not choose these $\epsilon$ bins from the first $1.693m-\epsilon$ bins
as then it would create a clash with vertex $u_{1}$. So, $w$ chooses bins from
$1.693m-\epsilon$ to $1.693m$. Then, introduce multiple edges between vertices
$u_{2}$ and $w$ such that $\epsilon$ closed bins are required. With similar
reasoning as before, $w$ chooses these bins to be from $1.693m$ to
$1.693m+\epsilon$. Then, introduce multiple edges between vertices $u_{3}$ and
$w$ such that $\epsilon$ closed bins are required. With similar reasoning as
before, $w$ chooses these bins to be from $1.693m+\epsilon$ to
$1.693m+2\cdot\epsilon$. Carry on this procedure for all $u_{i}$ for
$i=4,5,...,\frac{1.693m}{\epsilon}$.

  * •

Thus now vertex $w$ has used bins from $1.693m-\epsilon$ to
$1.693m+(\frac{1.693m}{\epsilon}-1)\cdot\epsilon=3.386m-\epsilon$. So, in
total $3.386m-\epsilon$ bins are used in the whole algorithm leading to a
competitive ratio of $3.386\approx 3.39$ (because $m\gg\epsilon$).

Note that here the number of neighbours of $w=\frac{1.693m}{\epsilon}\approx
10^{10}\approx m^{0.5}\approx o(m)$. Also, $\epsilon\gg 12$ is chosen so that
we don’t care about the $12$ open bins between any pair of neighbour vertices
in any of the above steps.

##  4 Offline Weighted Edge Coloring

In the offline version of the problem, we are given the whole undirected graph
upfront. We need to assign colors to each edge maintaining the condition of
proper coloring. The current best upper bound is $\lceil 2.2223m\rceil$ given
by Khan and Singh [18] for bipartite graphs. We will present improved
algorithms with better upper bounds for some special graphs.

###  4.1 Simple graph with edge disjoint cycles

######  Theorem 4.1.

Given an undirected simple graph (no multi-edges between 2 vertices)
$G:=(V,E)$ with edge disjoint cycles, it can colored using $m+1$ colors.

######  Proof 4.2.

We have a palette $P$ of $m+1$ colors numbered from 1 to $m+1$. Consider a
simpler example where we are given an undirected simple graph $T$ with no
cycles that is $T$ is a undirected simple tree. Let vertex $r$ be the root
vertex (if not given, choose any vertex as $r$). We will traverse $T$ in a BFS
manner starting from the root node $r$. Whenever visiting a node $u$, we will
color the edges incident to it.

Consider any step of this traversal where we visit node $u$. Let the $k$ child
nodes of $u$ be $v_{1},v_{2},\dots,v_{k}$ and let $w$ be the parent node of
$u$ (if $u\neq r$). As we are traversing in a BFS manner, the edge $(w,u)$
must have been already colored and none of the edges
$(u,v_{1}),(u,v_{2}),\dots,(u,v_{k})$ are colored (which we have to color in
this step). So, with respect to $u$, its only one of the incident edges have
been colored. So, by the definition of $m$, all the remaining edges incident
to $u$ can be colored taking at most $m$ colors in total from palette $P$.
This will not create any violations in any of the child nodes, as only one of
the edges of each child node is colored in this step. Carry on this procedure
for each node visited and eventually we have colored all the edges of the
tree. Thus, we can properly color a undirected simple tree in $m$ colors.

Now if we also have edge disjoint cycles, then this case is very similar to
the above. The only difference is that when visiting a node $u$, it might
happen that two of its edges have already been assigned different colors. But
it might happen that the optimal packing of edges incident to $u$ in $m$ unit-
sized bins assign same colors to these two already colored edges or vice-
versa. It might also happen that when we color the edges between the current
vertex and any of its child node, a clash might occur at the child node. This
is because now 2 edges of a child node may be colored before visiting that
child node which may create a violation. Thus we place an extra color in
palette $P$ to overcome this violation. Thus, $m+1$ colors are sufficient in
this case.

This result can be further generalised. If we are given an undirected simple
graph $G$. Let $y$ be the maximum number of cycles an edge is a part of taken
over all the edges. Then while traversing the graph in a BFS manner, it may
happen that $y+1$ edges have already been colored. So, in the worst case
scenario, we would require $m+y$ colors for properly coloring all the edges in
this case.

###  4.2 Multi-graph tree

######  Theorem 4.3.

Given an undirected multi-graph tree $G:=(V,E)$, it can be properly colored
using $2m$ colors using _NEXT-FIT_ and using $1.693m+12$ colors using
_HARMONIC M_ (with $M=12$). Below we present the algorithms and their
analysis.

######  Proof 4.4.

Let $r$ be the root vertex (assign any of the vertex as root vertex randomly
if $r$ not specified). Below we present the algorithms achieving the above
upper bounds along with their analysis. The algorithm starts from the root
vertex and visits all the nodes in a BFS manner. When visiting a node, it
colors the edges incident to it.

First let us consider when we use _NEXT-FIT_. Let there be a palette $P$
having $2m$ colors numbered from 1 to $2m$. Whenever a new color is required
from $P$, we chose the least numbered color which does not create any
violations. We claim that the size of $P$ is sufficient to properly color all
the edges. When visiting a node $u$. Let the $k$ child nodes of $u$ be
$v_{1},v_{2},\dots,v_{k}$ and let vertex $w$ be the parent node of $u$ if $u$
is not the root vertex. As we are traversing in a BFS manner, none of the
edges between $u$ and its child node $v_{i}$ will be colored (they have to be
colored in this step) whereas the edges between $u$ and parent node $w$ must
have already been colored when $w$ was visited.

We will color the edges between $u$ and its child nodes in a specific order in
which we consider one child node at a time and color the edges between them.
First color the edges between $u$ and $v_{1}$ in a _NEXT-FIT_ manner. This
means that at any moment there is an active/open color between $u$ and $v_{1}$
and present the edges between them in an online fashion (though we have all
the edges beforehand) and color them using _NEXT-FIT_. As the edges between
$u$ and $w$ have already been colored, let the colors used for them be
numbered from $c_{1}$ to $c_{2}$. Note that it would a continuous range of
colors due to the way we are coloring the edges each child node at a time, and
the way of choosing the new color when required from palette $P$. Keep $c_{2}$
as the initial open color between $u$ and $v_{1}$ and carry on the procedure
as explained above. When all the edges between $u$ and $v_{1}$ have been
colored, let the colors used for this be numbered from $c_{2}$ to $c_{3}$. Now
move on to the next child node $v_{2}$ with $c_{3}$ as the initial open color
between them. Carry on the this procedure for all the child nodes of $u$.

We claim that if the above algorithm is followed, then the number of colors
used by $u$ will be atmost $2m$ which are taken from palette $P$ without
creating any violations. This can be seen with the help of Lemma 2.1. Lemma
2.1 claims that when items are presented in an online manner and we pack them
using _NEXT-FIT_ , then atmost $2m-1$ bins are required. It is an easy
observation that we are doing the same thing here when visiting vertex $u$.
The items are the edges and the bins are the colors. As $w$ is the parent node
of $u$, $w$ must have been visited earlier than $u$. At that step when
considering the edges between $w$ and $u$, following the above algorithm,
these edges are presented in an online manner and colored using _NEXT-FIT_.
So, when we visit $u$ in the current step, some of its edges have already been
colored using _NEXT-FIT_ , and now we color the remaining incident edges again
using _NEXT-FIT_. Thus, the overall effect with respect to $u$ is that all its
incident edges are colored in a _NEXT-FIT_ manner thus taking atmost $2m-1+1$
colors. The $+1$ term is there because the first color ($c_{1}$ in the above
example) might not be fully utilized with respect to $u$. This holds true for
any node $u$ visited during BFS traversal. And thus by induction, all the
edges of $G$ can be colored properly using only the colors from palette $P$.

Finally for the case when we use $HARMONIC_{M}$ (with $M=12$), the algorithm
and analysis is very similar to the above. The only differences are that now
we follow $HARMONIC_{M}$ packing, by taking into consideration the $M$ types
of items/edges. So, at any moment there would be $M=12$ open bins instead of
just 1, each corresponding to a unique type. From Lemma 2.3, the upper bound
guarantee is $1.693m$. So, the palette size of $1.693m+12$ will be sufficient
for properly coloring all the edges without any violations. Below we present
both the algorithms in a concise form.

Algorithm 3 Algorithm for proper coloring of multi-graph trees using _NEXT-
FIT_

Let $P$ be a palette/set of $2m$ colors. Graph $G$ will use colors only from
the palette $P$. Also, let $Q$ be a FIFO queue. It is empty initially. Insert
root vertex $r$ into $Q$. Now repeat the below step until $Q$ is empty.

1: Dequeue a vertex from $Q$. Let it be $u$. If $u=r$, then color the edges
between $r$ and its child nodes taking one child node at a time as explained
above. Take color number 1 as the first open color between $r$ and the first
child node.

2: Else if $u\neq r$, then let vertex $w$ be the parent of $u$. Let the colors
used for coloring the edges between $w$ and $u$ be from $c_{1}$ to $c_{2}$.
Now color the edges between $u$ and its child nodes taking one child node at a
time as explained before. Take $c_{2}$ as the initial open color between $u$
and the first child node $v_{1}$.

3: Insert into $Q$ all the child nodes of $u$ if any.

If the given graph has multiple connected components, do the above procedure
for each connected component.

Algorithm 4 Algorithm for proper coloring of multi-graph trees using _HARMONIC
M_ with $M=12$

Let $P$ be a palette/set of $1.693m+12$ colors. Graph $G$ will use colors only
from the palette $P$. Also, let $Q$ be a FIFO queue. It is empty initially.
Insert root vertex $r$ into $Q$. Now repeat the below step until $Q$ is empty.

1: Dequeue a vertex from $Q$. Let it be $u$. If $u=r$, then color the edges
between $r$ and its child nodes taking one child node at a time as explained
above. Take color number 1 to 12 as the first open colors for each type
between $r$ and the first child node.

2: Else if $u\neq r$, then let vertex $w$ be the parent of $u$. Let the open
colors for each type be $c_{1},c_{2},\dots,c_{12}$ at the moment when all the
edges between $u$ and $w$ were finished assigning colors. Use these same 12
colors as the initial open colors of each type between $u$ and the first child
node $v_{1}$. Carry on the coloring using $HARMONIC_{M}$ as explained before.

3: Insert into $Q$ all the child nodes of $u$ if any.

If the given graph has multiple connected components, do the above procedure
for each connected component.

##  5 Conclusion

  * •

In all the algorithms above, we have used either _NEXT-FIT_ or $HARMONIC_{M}$.
The only differences between them is that there is a single open bin/color in
case of _NEXT-FIT_ whereas there are 12 open bins/colors in case of
$HARMONIC_{M}$ each for each type of items. Due to this distinction, the upper
bound guarantees are different as we saw in Lemma 2.1 and Lemma 2.3. Because
of this the algorithms and their analysis when using both are very similar. We
just need to take into consideration the type of items when using
$HARMONIC_{M}$ and we replace the upper bound $2m-1$ with $1.693m$ in the
analysis along with replacing $1$ open color with $M=12$ open colors at any
moment.

  * •

Note that the _weighted edge coloring problem_ with its condition of proper
coloring is a kind of global constraint as for a connected component,
assigning a color to an edge might depend on or might affect the colors
assigned to edges incident to some distant vertex. But in the above
algorithms, we just considered any arbitrary step, and we show that there
won’t be any violations in that step for which we only have to consider the
local neighbourhood. Then as this is true for any step, there is no violations
occurring in the whole algorithm by induction.

  * •

In Section 3, we presented better upper bounds for _offline weighted edge
coloring_ using _online bin packing algorithms_ like _NEXT-FIT_ and
$HARMONIC_{M}$. Thus, though its an offline problem, still online heuristics
can help to come up with better bounds.

##  6 Acknowledgment

The author wants to thank Prof. Arindam Khan, IISc Bangalore, for his
continuous support, guidance and regular feedback.

## References

  * [1] Susanne Albers, Arindam Khan, and Leon Ladewig.  Improved online algorithms for knapsack and GAP in the random order model.  In APPROX/RANDOM, pages 22:1–22:23, 2019.
  * [2] Susanne Albers, Arindam Khan, and Leon Ladewig.  Best fit bin packing with random order revisited.  In MFCS, pages 7:1–7:15, 2020.
  * [3] János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin.  A new and improved algorithm for online bin packing.  In ESA, pages 5:1–5:14, 2018.
  * [4] Nikhil Bansal, Marek Eliás, and Arindam Khan.  Improved approximation for vector bin packing.  In SODA, pages 1561–1579, 2016.
  * [5] Nikhil Bansal and Arindam Khan.  Improved approximation algorithm for two-dimensional bin packing.  In SODA, pages 13–25, 2014.
  * [6] Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali.  Approximation and online algorithms for multidimensional bin packing: A survey.  Computer Science Review, 24:63–79, 2017.
  * [7] Charles Clos.  A study of non-blocking switching networks.  Bell System Technical Journal, 32(2):406–424, 1953.
  * [8] Edward G Coffman, János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo.  Bin packing approximation algorithms: survey and classification.  In Handbook of combinatorial optimization, pages 455–531. Springer New York, 2013.
  * [9] José R Correa and Michel X Goemans.  Improved bounds on nonblocking 3-stage clos networks.  SIAM Journal on Computing, 37(3):870–894, 2007.
  * [10] W Fernandez De La Vega and George S. Lueker.  Bin packing can be solved within 1+ $\varepsilon$ in linear time.  Combinatorica, 1(4):349–355, 1981.
  * [11] Uriel Feige and Mohit Singh.  Edge coloring and decompositions of weighted graphs.  In European Symposium on Algorithms, pages 405–416. Springer, 2008\.
  * [12] Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau.  A tight (3/2+$\epsilon$) approximation for skewed strip packing.  In APPROX/RANDOM, pages 44:1–44:18, 2020.
  * [13] Biao Gao and Frank K Hwang.  Wide-sense nonblocking for multirate 3-stage clos networks.  Theoretical Computer Science, 182(1-2):171–182, 1997.
  * [14] Rebecca Hoberg and Thomas Rothvoss.  A logarithmic additive integrality gap for bin packing.  In SODA, pages 2616–2625, 2017.
  * [15] Tommy R Jensen and Bjarne Toft.  Graph coloring problems, volume 39.  John Wiley & Sons, 2011.
  * [16] Narendra Karmarkar and Richard M Karp.  An efficient approximation scheme for the one-dimensional bin-packing problem.  In FOCS, pages 312–320, 1982.
  * [17] Arindam Khan.  Approximation algorithms for multidimensional bin packing.  PhD thesis, Georgia Institute of Technology, Atlanta, GA, USA, 2016\.
  * [18] Arindam Khan and Mohit Singh.  On weighted bipartite edge coloring.  In FSTTCS, pages 136–150, 2015.
  * [19] Chan C Lee and Der-Tsai Lee.  A simple on-line bin-packing algorithm.  Journal of the ACM (JACM), 32(3):562–572, 1985.
  * [20] Michael Stiebitz, Diego Scheide, Bjarne Toft, and Lene M Favrholdt.  Graph edge coloring: Vizing’s theorem and Goldberg’s conjecture, volume 75.  John Wiley & Sons, 2012.
  * [21] Peter Guthrie Tait.  Remarks on the colouring of maps.  In Proc. Roy. Soc. Edinburgh, volume 10, pages 501–503, 1880.
  * [22] Kuo-Hui Tsai, Da-Wei Wang, and Frank Hwang.  Lower bounds for wide-sense nonblocking clos network.  Theoretical computer science, 261(2):323–328, 2001.