# Composition-Diamond Lemma for Tensor Product of Free Algebras111Supported by
the NNSF of China (No.10771077) and the NSF of Guangdong Province
(No.06025062).

L. A. Bokut222Supported by the RFBR and the Integration Grant of the SB RAS
(No. 1.9).
School of Mathematical Sciences, South China Normal University
Guangzhou 510631, P. R. China
Sobolev Institute of Mathematics, Russian Academy of Sciences
Siberian Branch, Novosibirsk 630090, Russia
Email<EMAIL_ADDRESS>

Yuqun Chen333Corresponding author. and Yongshan Chen
School of Mathematical Sciences, South China Normal University
Guangzhou 510631, P. R. China
Email<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
Abstract: In this paper, we establish Composition-Diamond lemma for tensor
product $k\langle X\rangle\otimes k\langle Y\rangle$ of two free algebras over
a field. As an application, we construct a Gröbner-Shirshov basis in $k\langle
X\rangle\otimes k\langle Y\rangle$ by lifting a Gröbner-Shirshov basis in
$k[X]\otimes k\langle Y\rangle$, where $k[X]$ is a commutative algebra.

Key words: Gröbner-Shirshov basis, Gröbner basis, free algebra, polynomial
algebra, tensor product.

AMS Mathematics Subject Classification(2000): 16S10, 16S15, 13P10

##  1 Introduction

In 1962, A. I. Shirshov [29] invented a theory of one-relator Lie algebras
$Lie(X|s=0)$ that was in a full analogy, by statements, but not the method, of
celebrated Magnus’s theory of one-relater groups [20] and [21], see also [22]
and [19]. In particular, A. I. Shirshov proved the algorithmic decidality of
the word problem for any one-relator Lie algebra. To do it, he created a
theory that is now called the Gröbner-Shirshov bases theory for Lie algebras
$Lie(X|S)$ presented by generators and defining relations. The main technical
notion of the latter Shirshov’s theory was a notion of composition $(f,g)_{w}$
of two Lie polynomials, $f,g\in Lie(X)$ relative to some associative word $w$.
Based on it, he defined an infinite algorithm of adding to some set $S$ of Lie
polynomials all non-trivial compositions until one will get a set $S^{*}$ that
is closed under compositions, i.e., any non-trivial composition of two
polynomials from $S^{*}$ belongs to $S^{*}$ (and leading associative words
$\bar{s}$ of polynomials $s\in S^{*}$ do not contain each others as subwords).
In addition, $S$ and $S^{*}$ generated the same ideal, i.e.,
$Id(S)=Id(S^{*})$. $S^{*}$ is now called a Gröbner-Shirshov basis of $Id(S)$.
Then he proved the following lemma.

_Let $Lie(X)\subset k\langle X\rangle$ be a free Lie algebra over a field $k$
viewed as the algebra of Lie polynomials in the free algebra $k\langle
X\rangle$, and $S$ a subset in $Lie(X)$. If $f\in Id(S)$, then
$\bar{f}=u\bar{s}v$, where $s\in S^{*},\ u,v\in X^{*},\ \bar{f},\bar{s}$ are
leading associative words of Lie polynomials $f,s$ correspondingly, and
$X^{*}$ the free monoid generated by $X$._

He used the following easy corollary of his lemma.

_$Irr(S)=\\{[u]\ |\ u\neq{a\bar{s}b},\ s\in{S},\ a,b\in{X^{*}}\\}$ is a linear
basis of the algebra $Lie(X|S)=Lie(X)/Id(S)$, where $u$ is an associative
Lyndon-Shirshov word in $X^{*}$ and $[u]$ the corresponding non-associative
Lyndon-Shirshov word under Lie brackets $[xy]=xy-yx$._

To define the Lie composition $(f,g)_{w}$ of two, say, monic Lie polynomials,
where $\bar{f}=ac,\ \bar{g}=cb,\ c\neq 1,\ a,b,c$ are associative words, and
$w=acb$, A. I. Shirshov defines first the associative composition $fb-ag$.
Then he puts on $fb$ and $ag$ special brackets $[fb],[ag]$ in according with
his paper [27]. The result is $(f,g)_{w}=[fc]-[cg]$. Following [29], one can
easily get the same lemma for a free associative algebra: Let $S\subset
k\langle X\rangle$ and $S^{*}$ be as before. If $f\in Id(S)$, then
$\bar{f}=a\bar{s}b$ for some $s\in S^{*},\ a,b\in X^{*}$. It was formulated
lately by L. A. Bokut [3] as an analogy of Shirshov’s Lie composition lemma,
and by G. Bergman [1] under the name “Diamond lemma” after celebrated Newman’s
Diamond Lemma for graphs [26].

Shirshov’s lemma is now called the Composition-Diamond lemma for Lie and
associative algebras. Its nowadays formulation see, for example, in the next
section in this paper.

Independently this kind of ideas were discovered by H. Hironaka [14] for the
power series algebras and by B. Buchberger [8], [9] for the polynomial
algebras. B. Buchberger suggested the name “Gröbner bases”. It is well known
and well recognized that applications of Gröbner bases in mathematics
(particulary, in algebraic geometry), computer science and informatics are
innumerable large.

At present, there are quite a few Compositions-Diamond lemmas (CD-lemma for
short) for different classes of non-commutative and non-associative algebras.
Let us mention some.

A. I. Shirshov [28] proved himself CD-lemma for commutative (anti-commutative)
non-associative algebras, and mentioned that this lemma is also valid for non-
associative algebras. It gives solution of the word problems for these classes
of algebras. For non-associative algebras, this (but not CD-lemma) was known,
see A. I. Zhukov [31].

A. A. Mikhalev [23] proved a CD-lemma for Lie super-algebras.

T. Stokes [30] proved a CD-lemma for left ideals of an algebra $k[X]\otimes
E_{k}(Y)$, the tensor product of Exterier (Grassman) algebra and a polynomial
algebra.

A. A. Mikhalev and E. A. Vasilieva [24] proved a CD-lemma for the free
supercommutative polynomial algebras.

A. A. Mikhalev and A. A. Zolotykh [25] proved a CD-lemma for $k[X]\otimes
k\langle Y\rangle$, the tensor product of a polynomial algebra and a free
algebra.

L. A. Bokut, Y. Fong and W. F. Ke [6] proved a CD-lemma for associative
conformal algebras.

L. Hellström [15] proved a CD-lemma for a non-commutative power series
algebra.

S.-J. Kang and K.-H. and Lee [16], [17] and E. S. Chibrikov [11] proved a CD-
lemma for a module over an algebra.

D. R. Farkas, C. D. Feustel and E. L. Green [13] proved a CD-lemma for path
algebras.

L. A. Bokut and K. P. Shum [7] proved a CD-lemma for $\Gamma$-algebras.

Y. Kobayashi [18] proved a CD-lemma for algebras based on well-ordered
semigroups, and L. A. Bokut, Yuqun Chen and Cihua Liu [5] proved a CD-lemma
for dialgebras (see also [4]).

Let $X$ and $Y$ be sets and $k\langle X\rangle\otimes k\langle Y\rangle$ the
tensor product algebra. In this paper, we give the Composition-Diamond lemma
for the algebra $k\langle X\rangle\otimes k\langle Y\rangle$. Also we will
prove a theorem on the pair of algebras $(k[X]\otimes k\langle
Y\rangle,k\langle X\rangle\otimes k\langle Y\rangle)$ in spirit of Eisenbud,
Peeva and Sturmfels theorem [12] on $(k[X],k\langle X\rangle)$.

##  2 Preliminaries

We cite some concepts and results from the literature ([29], [2], [3])
concerning with the Gröbner-Shirshov bases theory of associative algebras.

Let $k$ be a field, $k\langle X\rangle$ the free associative algebra over $k$
generated by $X$ and $X^{*}$ the free monoid generated by $X$, where the empty
word is the identity which is denoted by 1. For a word $w\in X^{*}$, we denote
the length of $w$ by $|w|$.

A well order $>$ on $X^{*}$ is monomial if it is compatible with the
multiplication of words, that is, for $u,v\in X^{*}$, we have

$u>v\Rightarrow w_{1}uw_{2}>w_{1}vw_{2},\ for\ all\ w_{1},\ w_{2}\in X^{*}.$

A standard example of monomial order on $X^{*}$ is the deg-lex order to
compare two words first by degree and then lexicographically, where $X$ is a
linearly ordered set.

Let $f\in k\langle X\rangle$ with the leading word $\bar{f}$. We say that $f$
is monic if $\bar{f}$ has coefficient 1.

Let $f$ and $g$ be two monic polynomials in k$\langle X\rangle$ and $<$ a well
order on $X^{*}$. Then, there are two kinds of compositions:

$(1)$ If $w$ is a word such that $w=\bar{f}b=a\bar{g}$ for some $a,b\in X^{*}$
with $|\bar{f}|+|\bar{g}|>|w|$, then the polynomial $(f,g)_{w}=fb-ag$ is
called the intersection composition of $f$ and $g$ with respect to $w$.

$(2)$ If $w=\bar{f}=a\bar{g}b$ for some $a,b\in X^{*}$, then the polynomial
$(f,g)_{w}=f-agb$ is called the inclusion composition of $f$ and $g$ with
respect to $w$.

Let $S\subset$ $\textmd{k}\langle X\rangle$ with each $s\in S$ monic. Then the
composition $(f,g)_{w}$ is called trivial modulo $(S,w)$ if
$(f,g)_{w}=\sum\alpha_{i}a_{i}s_{i}b_{i}$, where each $\alpha_{i}\in k,\
a_{i},b_{i}\in X^{*},\ s_{i}\in S$ and $\overline{a_{i}s_{i}b_{i}}<w$. If this
is the case, then we write

$(f,g)_{w}\equiv 0\quad mod(S,w).$

In general, for $p,q\in k\langle X\rangle$, we write $p\equiv q\quad mod(S,w)$
which means that $p-q\equiv 0\quad mod(S,w)$.

We call the set $S$ with respect to the monomial order $<$ a Gröbner-Shirshov
basis in $k\langle X\rangle$ if any composition of polynomials in $S$ is
trivial modulo $S$.

###### Lemma 2.1

(Composition-Diamond lemma for associative algebras) Let $S\subset k\langle
X\rangle$ be a set of monic polynomials and $<$ a monomial order on $X^{*}$.
Then the following statements are equivalent:

  1. (1)

$S$ is a Gröbner-Shirshov basis in $k\langle X\rangle$.

  2. (2)

$f\in Id(S)\Rightarrow\bar{f}=a\bar{s}b$ for some $s\in S$ and $a,b\in X^{*}$,
where $Id(S)$ is the ideal of $k\langle X\rangle$ generated by $S$.

  3. (3)

$Irr(S)=\\{u\in X^{*}|u\neq a\bar{s}b,s\in S,a,b\in X^{*}\\}$ is a basis of
the algebra $A=k\langle X|S\rangle$.

##  3 Composition-Diamond Lemma for Tensor Product

Let $X$ and $Y$ be linearly ordered sets, $T=\\{yx=xy|x\in X,\ y\in Y\\}$.
With the deg-lex order ($y>x$ for any $x\in X,\ y\in Y$) on $(X\cup Y)^{*}$,
$T$ is a Gröbner-Shirshov basis in $k\langle X\cup Y\rangle$. Then, by Lemma
2.1, the set

$N=X^{*}Y^{*}=Irr(T)=\\{u=u^{X}u^{Y}|u^{X}\in X^{*}\ and\ u^{Y}\in Y^{*}\\}$

is the normal words of the tensor product

$k\langle X\rangle\otimes k\langle Y\rangle=k\langle X\cup Y\ |\ T\rangle.$

Let $kN$ be a $k$-space spanned by $N$. For any $u=u^{X}u^{Y},v=v^{X}v^{Y}\in
N$, we define the multiplication of the normal words as follows

$uv=u^{X}v^{X}u^{Y}v^{Y}\in N.$

Then, $kN$ is exactly tensor product algebra $k\langle X\rangle\otimes
k\langle Y\rangle$, that is, $kN=k\langle X\cup Y|T\rangle=k\langle
X\rangle\otimes k\langle Y\rangle$.

Let $``>_{X}"$ and $``>_{Y}"$ be any monomial orders on $X^{*}$ and $Y^{*}$
respectively. Now, we order the set $N$. For any $u=u^{X}u^{Y},v=v^{X}v^{Y}\in
N$,

$u>v\Leftrightarrow u^{X}>_{X}v^{X}\ or\ (u^{X}=v^{X}\ and\ u^{Y}>_{Y}v^{Y}).$

It is obvious that $>$ is a monomial order on $N$. Such an order is also
called the deg-lex order on $N=X^{*}Y^{*}$. We will use this order in the
sequel unless others stated.

For any polynomial $f\in k\langle X\rangle\otimes k\langle Y\rangle$, $f$ has
a unique presentation of the form

$f=\alpha_{\bar{f}}\bar{f}+\sum\alpha_{i}u_{i},$

where $\bar{f},u_{i}\in N,\bar{f}>u_{i},\alpha_{\bar{f}},\alpha_{i}\in k.$

The proof of the following lemma are straightforward.

###### Lemma 3.1

Let $f\in k\langle X\rangle\otimes k\langle Y\rangle$ be a monic polynomial.
Then $\overline{ufv}=u\bar{f}v$ for any $u,v\in N$.

Now, we give the definition of compositions. Let $f$ and $g$ be monic
polynomials of $k\langle X\rangle\otimes k\langle Y\rangle$ and
$w=w^{X}w^{Y}\in N$. Then we have the following compositions.

$1.$ Inclusion

$1.1$ $X$-inclusion only

Suppose that $w^{X}=\bar{f}^{X}=a\bar{g}^{X}b$ for some $a,b\in X^{*}$, and
$\bar{f}^{Y},\ \bar{g}^{Y}$ are disjoint. Then there are two compositions
according to $w^{Y}=\bar{f}^{Y}c\bar{g}^{Y}$ and
$w^{Y}=\bar{g}^{Y}c\bar{f}^{Y}$ for $c\in Y^{*}$, respectively:

$(f,g)_{w_{1}}=fc\bar{g}^{Y}-\bar{f}^{Y}cagb,\ \
w_{1}=f^{X}\bar{f}^{Y}c\bar{g}^{Y}$

and

$(f,g)_{w_{2}}=\bar{g}^{Y}cf-agbc\bar{f}^{Y},\ \
w_{2}=f^{X}\bar{g}^{Y}c\bar{f}^{Y}.$

$1.2$ $Y$-inclusion only

Suppose that $w^{Y}=\bar{f}^{Y}=c\bar{g}^{Y}d$ for $c,d\in Y^{*}$, and
$\bar{f}^{X},\ \bar{g}^{X}$ are disjoint. Then there are two compositions
according to $w^{X}=\bar{f}^{X}a\bar{g}^{X}$ and
$w^{X}=\bar{g}^{X}a\bar{f}^{X}$ for $a\in X^{*}$, respectively:

$(f,g)_{w_{1}}=fa\bar{g}^{X}-\bar{f}^{X}acgd,\ \
w_{1}=\bar{f}^{X}a\bar{g}^{X}f^{Y}$

and

$(f,g)_{w_{2}}=\bar{g}^{X}af-cgda\bar{f}^{X}\ \
w_{2}=\bar{g}^{X}a\bar{f}^{X}f^{Y}.$

$1.3$ $X,Y$-inclusion

Suppose that $w^{X}=\bar{f}^{X}=a\bar{g}^{X}b$ for some $a,b\in X^{*}$ and
$w^{Y}=\bar{f}^{Y}=c\bar{g}^{Y}d$ for some $c,d\in Y^{*}$. Then

$(f,g)_{w}=f-acgbd.$

The transformation $f\mapsto(f,g)_{w}=f-acgbd$ is called the _elimination of
the leading word_ (ELW) of $g$ in $f$.

$1.4$ $X,Y$-skew-inclusion

Suppose that $w^{X}=\bar{f}^{X}=a\bar{g}^{X}b$ for some $a,b\in X^{*}$ and
$w^{Y}=\bar{g}^{Y}=c\bar{f}^{Y}d$ for some $c,d\in Y^{*}$. Then

$(f,g)_{w}=cfd-agb.$

$2.$ Intersection

$2.1$ $X$-intersection only

Suppose that $w^{X}=\bar{f}^{X}a=b\bar{g}^{X}$ for some $a,b\in X^{*}$ with
$|\bar{f}^{X}|+|\bar{g}^{X}|>|w^{X}|$, and $\bar{f}^{Y},\ \bar{g}^{Y}$ are
disjoint. Then there are two compositions according to
$w^{Y}=\bar{f}^{Y}c\bar{g}^{Y}$ and $w^{Y}=\bar{g}^{Y}c\bar{f}^{Y}$ for $c\in
Y^{*}$, respectively:

$(f,g)_{w_{1}}=fac\bar{g}^{Y}-\bar{f}^{Y}cbg,\ \
w_{1}=w^{X}\bar{f}^{Y}c\bar{g}^{Y}$

and

$(f,g)_{w_{2}}=\bar{g}^{Y}cfa-bgc\bar{f}^{Y},\ \
w_{2}=w^{X}\bar{g}^{Y}c\bar{f}^{Y}.$

$2.2$ $Y$-intersection only

Suppose that $w^{Y}=\bar{f}^{Y}c=d\bar{g}^{X}$ for some $c,d\in Y^{*}$ with
$|\bar{f}^{Y}|+|\bar{g}^{Y}|>|w^{Y}|$, and $\bar{f}^{X},\ \bar{g}^{X}$ are
disjoint. Then there are two compositions according to
$w^{X}=\bar{f}^{X}a\bar{g}^{X}$ and $w^{X}=\bar{g}^{X}a\bar{f}^{X}$ for $a\in
X^{*}$, respectively:

$(f,g)_{w_{1}}=fca\bar{g}^{X}-\bar{f}^{X}adg,\ \
w_{1}=\bar{f}^{X}a\bar{g}^{X}w^{Y}$

and

$(f,g)_{w_{2}}=\bar{g}^{X}afc-dga\bar{f}^{X},\ \
w_{2}=\bar{g}^{X}a\bar{f}^{X}w^{Y}.$

$2.3$ $X,Y$-intersection

If $w^{X}=\bar{f}^{X}a=b\bar{g}^{X}$ for some $a,b\in X^{*}$ and
$w^{Y}=\bar{f}^{Y}c=d\bar{g}^{Y}$ for some $c,d\in Y^{*}$ together with
$|\bar{f}^{X}|+|\bar{g}^{X}|>|w^{X}|$ and
$|\bar{f}^{Y}|+|\bar{g}^{Y}|>|w^{Y}|$, then

$(f,g)_{w}=fac-bdg.$

$2.4$ $X,Y$-skew-intersection

If $w^{X}=\bar{f}^{X}a=b\bar{g}^{X}$ for some $a,b\in X^{*}$ and
$w^{Y}=c\bar{f}^{Y}=\bar{g}^{Y}d$ for some $c,d\in Y^{*}$ together with
$|\bar{f}^{X}|+|\bar{g}^{X}|>|w^{X}|$ and
$|\bar{f}^{Y}|+|\bar{g}^{Y}|>|w^{Y}|$, then

$(f,g)_{w}=cfa-bgd.$

$3.$ Both inclusion and intersection

$3.1$ $X$-inclusion and $Y$-intersection

There are two cases to consider.

If $w^{X}=\bar{f}^{X}=a\bar{g}^{X}b$ for some $a,b\in X^{*}$ and
$w^{Y}=\bar{f}^{Y}c=d\bar{g}^{Y}$ for some $c,d\in Y^{*}$ with
$|\bar{f}^{Y}|+|\bar{g}^{Y}|>|w^{Y}|$, then

$(f,g)_{w}=fc-adgb.$

If $w^{X}=\bar{f}^{X}=a\bar{g}^{X}b$ for some $a,b\in X^{*}$ and
$w^{Y}=c\bar{f}^{Y}=\bar{g}^{Y}d$ for some $c,d\in Y^{*}$ with
$|\bar{f}^{Y}|+|\bar{g}^{Y}|>|w^{Y}|$, then

$(f,g)_{w}=cf-agbd.$

$3.2$ $X$-intersection and $Y$-inclusion

There are two cases to consider.

If $w^{X}=\bar{f}^{X}a=b\bar{g}^{X}$ for some $a,b\in X^{*}$ with
$|\bar{f}^{X}|+|\bar{g}^{X}|>|w^{X}|$ and $w^{Y}=\bar{f}^{Y}=c\bar{g}^{Y}d$
for some $c,d\in Y^{*}$, then

$(f,g)_{w}=fa-bcgd.$

If $w^{X}=\bar{f}^{X}a=b\bar{g}^{X}$ for some $a,b\in X^{*}$ with
$|\bar{f}^{X}|+|\bar{g}^{X}|>|w^{X}|$ and $w^{Y}=c\bar{f}^{Y}d=\bar{g}^{Y}$
for some $c,d\in Y^{*}$, then

$(f,g)_{w}=cfad-bg.$

From Lemma 3.1, it follows that for any case of compositions

$\overline{(f,g)_{w}}<w.$

If $Y=\emptyset$, then the compositions of $f,g$ are the same in $k\langle
X\rangle$.

Let $S$ be a monic subset of $k\langle X\rangle\otimes k\langle Y\rangle$ and
$f,g\in S$. A composition $(f,g)_{w}$ is said to be _trivial modulo_ $(S,w)$,
denoted by

$(f,g)_{w}\equiv 0\ \ mod(S,w),\ \mbox{ if }\
(f,g)_{w}=\sum_{i}\alpha_{i}a_{i}s_{i}b_{i},$

where $a_{i},b_{i}\in N,\ s_{i}\in S,\ \alpha_{i}\in k$ and
$a_{i}\bar{s_{i}}b_{i}<w$ for any $i$.

Generally, for any $p,q\in k\langle X\rangle\otimes k\langle Y\rangle,\
p\equiv q\ \ mod(S,w)$ if and only if $p-q\equiv 0\ \ mod(S,w).$

$S$ is called a _Gröbner-Shirshov basis_ in $k\langle X\rangle\otimes k\langle
Y\rangle$ if all compositions of elements in $S$ are trivial modulo $S$ and
corresponding to $w$.

###### Lemma 3.2

Let $S$ be a Gröbner-Shirshov basis in $k\langle X\rangle\otimes k\langle
Y\rangle$ and $s_{1},s_{2}\in S$. If
$w=a_{1}\bar{s_{1}}b_{1}=a_{2}\bar{s_{2}}b_{2}$ for some $a_{i},b_{i}\in N,\
i=1,2$, then $a_{1}s_{1}b_{1}\equiv a_{2}s_{2}b_{2}\ mod(S,w)$.

Proof: There are four cases to consider.

_Case 1_ Inclusion

_(1.1)_ $X$-inclusion only

Suppose that $w_{1}^{X}=\bar{s_{1}}^{X}=a\bar{s_{2}}^{X}b,\ a,b\in X^{*}$ and
$\bar{s_{1}}^{Y},\ \bar{s_{2}}^{Y}$ are disjoint. Then $a_{2}^{X}=a_{1}^{X}a$
and $b_{2}^{X}=bb_{1}^{X}$. There are two cases to consider:
$w_{1}^{Y}=\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y}$ and
$w_{1}^{Y}=\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y}$, where $c\in Y^{*}$.

For $w_{1}^{Y}=\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y}$, we have
$w_{1}=s_{1}^{X}\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y},\
a_{2}^{Y}=a_{1}^{Y}\bar{s_{1}}^{Y}c$, $b_{1}^{Y}=c\bar{s_{2}}^{Y}b_{2}^{Y}$,
$w=a_{1}w_{1}b_{1}^{X}b_{2}^{Y}=a_{1}\bar{s_{1}}ac\bar{s_{2}}b_{2}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}s_{1}b_{1}^{X}c\bar{s_{2}}^{Y}b_{2}^{Y}-a_{1}^{X}aa_{1}^{Y}\bar{s_{1}}^{Y}cs_{2}bb_{1}^{X}b_{2}^{Y}$
$\displaystyle=$ $\displaystyle
a_{1}(s_{1}c\bar{s_{2}}^{Y}-\bar{s_{1}}^{Y}cas_{2}b)b_{1}^{X}b_{2}^{Y}$
$\displaystyle=$ $\displaystyle a_{1}(s_{1},s_{2})_{w_{1}}b_{1}^{X}b_{2}^{Y}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S,w).$

For $w_{1}^{Y}=\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y}$, we have
$w_{1}=s_{1}^{X}\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y},\
a_{1}^{Y}=a_{2}^{Y}\bar{s_{2}}^{Y}c$, $b_{2}^{Y}=c\bar{s_{1}}^{Y}b_{1}^{Y}$,
$w=a_{1}^{X}a_{2}^{Y}w_{1}b_{1}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}^{X}a_{2}^{Y}\bar{s_{2}}^{Y}cs_{1}b_{1}-a_{1}^{X}aa_{2}^{Y}s_{2}bb_{1}^{X}c\bar{s_{1}}^{Y}b_{1}^{Y}$
$\displaystyle=$ $\displaystyle
a_{1}^{X}a_{2}^{Y}(\bar{s_{2}}^{Y}cs_{1}-as_{2}bc\bar{s_{1}}^{Y})b_{1}$
$\displaystyle=$ $\displaystyle a_{1}^{X}a_{2}^{Y}(s_{1},s_{2})_{w_{1}}b_{1}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S,w).$

_(1.2)_ $Y$-inclusion only

This case is similar to (1.1).

_(1.3)_ $X,Y$-inclusion

We may assume that $\bar{s_{2}}$ is a subword of $\bar{s_{1}}$, i.e.,
$w_{1}=\bar{s_{1}}=ac\bar{s_{2}}bd$, $a,b\in X^{*}$, $c,d\in Y^{*}$,
$a_{2}^{X}=a_{1}^{X}a$, $b_{2}^{X}=bb_{1}^{X}$, $a_{2}^{Y}=a_{1}^{Y}c$ and
$b_{2}^{Y}=db_{1}^{Y}$. Thus, $a_{2}=a_{1}ac,\ b_{2}=bdb_{1},\
w=a_{1}w_{1}b_{1}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle a_{1}s_{1}b_{1}-a_{1}acs_{2}bdb_{1}$ $\displaystyle=$
$\displaystyle a_{1}(s_{1}-acs_{2}bd)b_{1}$ $\displaystyle=$ $\displaystyle
a_{1}(s_{1},s_{2})_{w_{1}}b_{1}$ $\displaystyle\equiv$ $\displaystyle 0\ \ \ \
\ mod(S,w).$

_(1.4)_ $X,Y$-skew-inclusion

Assume that $w_{1}^{X}=\bar{s_{1}}^{X}=a\bar{s_{2}}^{X}b,\ a,b\in X^{*}$ and
$w_{1}^{Y}=\bar{s_{2}}^{Y}=c\bar{s_{1}}^{Y}d,\ c,d\in Y^{*}$. Then
$a_{2}^{X}=a_{1}^{X}a$, $b_{2}^{X}=bb_{1}^{X}$, $a_{1}^{Y}=a_{2}^{Y}c$ and
$b_{1}^{Y}=db_{2}^{Y}$. Thus, $w=a_{1}^{X}a_{2}^{Y}w_{1}b_{1}^{X}b_{2}^{Y}$
and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}^{X}a_{2}^{Y}cs_{1}b_{1}^{X}db_{2}^{Y}-a_{1}^{X}aa_{2}^{Y}s_{2}bb_{1}^{X}b_{2}^{Y}$
$\displaystyle=$ $\displaystyle
a_{1}^{X}a_{2}^{Y}(cs_{1}d-as_{2}b)b_{1}^{X}b_{2}^{Y}$ $\displaystyle=$
$\displaystyle a_{1}^{X}a_{2}^{Y}(s_{1},s_{2})_{w_{1}}b_{1}^{X}b_{2}^{Y}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ mod(S,w).$

_Case 2_ Intersection

_(2.1)_ $X$-intersection only

We may assume that $\bar{s_{1}}^{X}$ is at the left of $\bar{s_{2}}^{X}$,
i.e., $w_{1}^{X}=\bar{s_{1}}^{X}b=a\bar{s_{2}}^{X}$, $a,b\in X^{*}$ and
$|\bar{s_{1}}^{X}|+|\bar{s_{2}}^{X}|>|w_{1}^{X}|$. Then $a_{2}^{X}=a_{1}^{X}a$
and $b_{1}^{X}=bb_{2}^{X}$. There are two cases to be consider:
$w_{1}^{Y}=\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y}$ and
$w_{1}^{Y}=\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y},\ c\in Y^{*}.$

For $w_{1}^{Y}=\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y}$, i.e.,
$w_{1}=\bar{s_{1}}bc\bar{s_{2}}^{Y}$, we have
$a_{2}^{Y}=a_{1}^{Y}\bar{s_{1}}^{Y}c$, $b_{1}^{Y}=c\bar{s_{2}}^{Y}b_{2}^{Y}$,
$w=a_{1}\bar{s_{1}}ac\bar{s_{2}}b_{2}=a_{1}w_{1}b_{2}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}s_{1}bb_{2}^{X}c\bar{s_{2}}^{Y}b_{2}^{Y}-a_{1}^{X}aa_{1}^{Y}\bar{s_{2}}^{Y}cs_{2}b_{2}$
$\displaystyle=$ $\displaystyle
a_{1}(s_{1}bc\bar{s_{2}}^{Y}-a\bar{s_{2}}^{Y}cs_{2})b_{2}$ $\displaystyle=$
$\displaystyle a_{1}(s_{1},s_{2})_{w_{1}}b_{2}$ $\displaystyle\equiv$
$\displaystyle 0\ \ \ \ \ \ \ mod(S,w).$

For $w_{1}^{Y}=\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y}$, i.e.,
$w_{1}=\bar{s_{2}}^{Y}c\bar{s_{1}}b$, we have
$a_{1}^{Y}=a_{2}^{Y}\bar{s_{2}}^{Y}c$, $b_{2}^{Y}=c\bar{s_{1}}^{Y}b_{1}^{Y},\
w=a_{1}^{X}a_{2}^{Y}w_{1}b_{2}^{X}b_{1}^{Y}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}^{X}a_{2}^{Y}\bar{s_{2}}^{Y}cs_{1}bb_{2}^{X}b_{1}^{Y}-a_{1}^{X}aa_{2}^{Y}s_{2}b_{2}^{X}c\bar{s_{1}}^{Y}b_{1}^{Y}$
$\displaystyle=$ $\displaystyle
a_{1}^{X}a_{2}^{Y}(\bar{s_{2}}^{Y}cs_{1}b-as_{2}c\bar{s_{1}}^{Y})b_{2}^{X}b_{1}^{Y}$
$\displaystyle=$ $\displaystyle
a_{1}^{X}a_{2}^{Y}(s_{1},s_{2})_{w_{1}}b_{2}^{X}b_{1}^{Y}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S,w).$

_(2.2)_ $Y$-intersection only

This case is similar to (2.1).

_(2.3)_ $X,Y$-intersection

Assume that $w_{1}^{X}=\bar{s_{1}}^{X}b=a\bar{s_{2}}^{X}$,
$w_{1}^{Y}=\bar{s_{1}}^{Y}d=c\bar{s_{2}}^{Y}$, $a,b\in X^{*},\ c,d\in Y^{*}$,
$|\bar{s_{1}}^{X}|+|\bar{s_{2}}^{X}|>|w_{1}^{X}|$ and
$|\bar{s_{1}}^{Y}|+|\bar{s_{2}}^{Y}|>|w_{1}^{Y}|$. Then
$a_{2}^{X}=a_{1}^{X}a$, $b_{1}^{X}=bb_{2}^{X}$, $a_{2}^{Y}=a_{1}^{Y}c$,
$b_{1}^{Y}=db_{2}^{Y}$, $w=a_{1}w_{1}b_{2}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle a_{1}s_{1}bb_{2}^{X}db_{2}^{Y}-a_{1}^{X}aa_{1}^{Y}cs_{2}b_{2}$
$\displaystyle=$ $\displaystyle a_{1}(s_{1}bd-acs_{2})b_{2}$ $\displaystyle=$
$\displaystyle a_{1}(s_{1},s_{2})_{w_{1}}b_{2}$ $\displaystyle\equiv$
$\displaystyle 0\ \ \ \ \ mod(S,w).$

_(2.4)_ $X,Y$-skew-intersection

Assume that $w_{1}^{X}=\bar{s_{1}}^{X}b=a\bar{s_{2}}^{X}$,
$w_{1}^{Y}=c\bar{s_{1}}^{Y}=\bar{s_{2}}^{Y}d$,
$|\bar{s_{1}}^{X}|+|\bar{s_{2}}^{X}|>|w_{1}^{X}|$,
$|\bar{s_{1}}^{Y}|+|\bar{s_{2}}^{Y}|>|w_{1}^{Y}|$, $a,b\in X^{*},\ c,d\in
Y^{*}$. Then $a_{2}^{X}=a_{1}^{X}a$, $b_{1}^{X}=bb_{2}^{X}$,
$a_{1}^{Y}=a_{2}^{Y}c$, $b_{2}^{Y}=db_{1}^{Y}$,
$w=a_{1}^{X}a_{2}^{Y}w_{1}b_{2}^{X}b_{1}^{Y}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}^{X}a_{2}^{Y}cs_{1}bb_{2}^{X}b_{1}^{Y}-a_{1}^{X}aa_{2}^{Y}s_{2}b_{2}^{X}db_{1}^{Y}$
$\displaystyle=$ $\displaystyle
a_{1}^{X}a_{2}^{Y}(cs_{1}b-as_{2}d)b_{2}^{X}b_{1}^{Y}$ $\displaystyle=$
$\displaystyle a_{1}^{X}a_{2}^{Y}(s_{1},s_{2})_{w_{1}}b_{2}^{X}b_{1}^{Y}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S,w).$

_Case 3_ Both inclusion and intersection

_(3.1)_ $X$-inclusion and $Y$-intersection

We may assume that $w_{1}^{X}=\bar{s_{1}}^{X}=a\bar{s_{2}}^{X}b$, $a,b\in
X^{*}$. Then $a_{2}^{X}=a_{1}^{X}a$ and $b_{2}^{X}=bb_{1}^{X}$. There two
cases to consider: $w_{1}^{Y}=\bar{s_{1}}^{Y}d=c\bar{s_{2}}^{Y}$ and
$w_{1}^{Y}=c\bar{s_{1}}^{Y}=\bar{s_{2}}^{Y}d$, where $c,d\in Y^{*}$,
$|\bar{s_{1}}^{Y}|+|\bar{s_{2}}^{Y}|>|w_{1}^{Y}|$.

For $w_{1}^{Y}=\bar{s_{1}}^{Y}d=c\bar{s_{2}}^{Y}$, we have
$a_{2}^{Y}=a_{1}^{Y}c$, $b_{1}^{Y}=db_{2}^{Y},\
w=a_{1}w_{1}b_{1}^{X}b_{2}^{Y}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}s_{1}b_{1}^{X}db_{2}^{Y}-a_{1}^{X}aa_{1}^{Y}cs_{2}bb_{1}^{X}b_{2}^{Y}$
$\displaystyle=$ $\displaystyle a_{1}(s_{1}d-acs_{2}b)b_{1}^{X}b_{2}^{Y}$
$\displaystyle=$ $\displaystyle a_{1}(s_{1},s_{2})_{w_{1}}b_{2}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ mod(S,w).$

For $w_{1}^{Y}=c\bar{s_{1}}^{Y}=\bar{s_{2}}^{Y}d$, we have
$a_{1}^{Y}=a_{2}^{Y}c$, $b_{2}^{Y}=db_{1}^{Y}$,
$w=a_{1}^{X}a_{2}^{Y}w_{1}b_{2}^{X}db_{1}^{Y}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}^{X}a_{2}^{Y}cs_{1}b_{1}-a_{1}^{X}aa_{2}^{Y}s_{2}bb_{1}^{X}db_{1}^{Y}$
$\displaystyle=$ $\displaystyle a_{1}^{X}a_{2}^{Y}(cs_{1}-as_{2}bd)b_{1}$
$\displaystyle=$ $\displaystyle a_{1}^{X}a_{2}^{Y}(s_{1},s_{2})_{w_{1}}b_{1}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S,w).$

_(3.2)_ $X$-intersection and $Y$-inclusion

Assume that $w_{1}^{X}=\bar{s_{1}}^{X}b=a\bar{s_{2}}^{X}$, $a,b\in Y^{*}$ with
$|\bar{s_{1}}^{X}|+|\bar{s_{2}}^{X}|>|w_{1}^{X}|$. Then
$a_{2}^{X}=a_{1}^{X}a$, $b_{1}^{X}=bb_{2}^{X}$. There are two cases to
consider: $w_{1}^{Y}=\bar{s_{1}}^{Y}=c\bar{s_{2}}^{Y}d$ and
$\bar{s_{2}}^{Y}=c\bar{s_{1}}^{Y}d$, where $c,d\in Y^{*}$.

For $w_{1}^{Y}=\bar{s_{1}}^{Y}=c\bar{s_{2}}^{Y}d$, we have
$a_{2}^{Y}=a_{1}^{Y}c$, $b_{2}^{Y}=db_{1}^{Y}$,
$w=a_{1}w_{1}b_{2}^{X}b_{1}^{Y}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle a_{1}s_{1}bb_{2}^{X}b_{1}^{Y}-a_{1}acs_{2}b_{2}^{X}db_{1}^{Y}$
$\displaystyle=$ $\displaystyle a_{1}(s_{1}b-acs_{2}d)b_{2}^{X}b_{1}^{Y}$
$\displaystyle=$ $\displaystyle a_{1}(s_{1},s_{2})_{w_{1}}b_{2}^{X}b_{1}^{Y}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ mod(S,w).$

For $w_{1}^{Y}=\bar{s_{2}}^{Y}=c\bar{s_{1}}^{Y}d$, we have
$a_{1}^{Y}=a_{2}^{Y}c$, $b_{1}^{Y}=db_{2}^{Y}$,
$w=a_{1}^{X}a_{2}^{Y}w_{1}b_{2}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}^{X}a_{2}^{Y}cs_{1}bb_{2}^{X}db_{2}^{Y}-a_{1}^{X}aa_{2}^{Y}s_{2}b_{2}$
$\displaystyle=$ $\displaystyle a_{1}^{X}a_{2}^{Y}(cs_{1}bd-as_{2})b_{2}$
$\displaystyle=$ $\displaystyle a_{1}^{X}a_{2}^{Y}(s_{1},s_{2})_{w_{1}}b_{2}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ mod(S,w).$

_Case 4_. $\bar{s_{1}}$ and $\bar{s_{2}}$ disjoint

For $w=w^{X}w^{Y}$, by symmetry, there are two cases to consider:
$w^{Y}=a_{1}^{Y}\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y}b_{2}^{Y}$ and
$w^{Y}=a_{2}^{Y}\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y}b_{1}^{Y}$, where
$w^{X}=a_{1}^{X}\bar{s_{1}}^{X}a\bar{s_{2}}^{X}b_{2}^{X},\ a\in X^{*},\
a_{2}^{X}=a_{1}^{X}\bar{s_{1}}^{X}a,\ b_{1}^{X}=a\bar{s_{2}}^{X}b_{2}^{X}$ and
$c\in Y^{*}$.

For
$w=a_{1}^{X}\bar{s_{1}}^{X}a\bar{s_{2}}^{X}b_{2}^{X}a_{1}^{Y}\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y}b_{2}^{Y}=a_{1}\bar{s_{1}}ac\bar{s_{2}}b_{2}$,
we have $a_{2}=a_{1}\bar{s_{1}}ac,\ b_{1}=ac\bar{s_{2}}b_{2}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle a_{1}s_{1}ac\bar{s_{2}}b_{2}-a_{1}\bar{s_{1}}acs_{2}b_{2}$
$\displaystyle=$ $\displaystyle
a_{1}(s_{1}-\bar{s_{1}})acs_{2}b_{2}-a_{1}s_{1}ac(s_{2}-\bar{s_{2}})b_{2}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S,w).$

For
$w=a_{1}^{X}\bar{s_{1}}^{X}a\bar{s_{2}}^{X}b_{2}^{X}a_{2}^{Y}\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y}b_{1}^{Y}$,
we have $a_{1}^{Y}=a_{2}^{Y}\bar{s_{2}}^{Y}c,\
b_{2}^{Y}=c\bar{s_{1}}^{Y}b_{1}^{Y}$ and

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}^{X}a_{2}^{Y}\bar{s_{2}}^{Y}cs_{1}a\bar{s_{2}}^{X}b_{2}^{X}b_{1}^{Y}-a_{1}^{X}\bar{s_{1}}^{X}aa_{2}^{Y}s_{2}b_{2}^{X}c\bar{s_{1}}^{Y}b_{1}^{Y}$
$\displaystyle=$ $\displaystyle
a_{1}^{X}a_{2}^{Y}(\bar{s_{2}}^{Y}cs_{1}a\bar{s_{2}}^{X}-\bar{s_{1}}^{X}as_{2}c\bar{s_{1}}^{Y})b_{2}^{X}b_{1}^{Y}.$

Let $s_{1}=\sum_{i=1}^{n}\alpha_{i}u_{1i}^{X}u_{1i}^{Y}$ and
$s_{2}=\sum_{j=1}^{m}\beta_{j}u_{2j}^{X}u_{2j}^{Y}$, where
$\alpha_{1}=\beta_{1}=1.$ Then

$\displaystyle\bar{s_{2}}^{Y}cs_{1}a\bar{s_{2}}^{X}-\bar{s_{1}}^{X}as_{2}c\bar{s_{1}}^{Y}$
$\displaystyle=$
$\displaystyle\sum_{i=2}^{n}\alpha_{i}u_{1i}^{X}a\bar{s_{2}}cu_{1i}^{Y}-\sum_{j=2}^{m}\beta_{i}u_{2j}^{Y}c\bar{s_{1}}au_{2j}^{X}$
$\displaystyle=$
$\displaystyle\sum_{i=2}^{n}\alpha_{i}u_{1i}^{X}a(\bar{s_{2}}-s_{2})cu_{1i}^{Y}+\sum_{j=2}^{m}\beta_{j}u_{2j}^{Y}c(s_{1}-\bar{s_{1}})au_{2j}^{X}$
$\displaystyle+\sum_{i=2}^{n}\alpha_{i}u_{1i}^{X}as_{2}cu_{1i}^{Y}-\sum_{j=2}^{m}\beta_{j}u_{2j}^{Y}cs_{1}au_{2j}^{X}$
$\displaystyle\equiv$
$\displaystyle\sum_{i=2}^{n}\sum_{j=2}^{m}\alpha_{i}\beta_{j}u_{1i}^{X}au_{2j}^{X}u_{2j}^{Y}cu_{1i}^{Y}-\sum_{j=2}^{m}\sum_{i=2}^{n}\alpha_{i}\beta_{j}u_{2j}^{Y}cu_{1i}^{Y}u_{1i}^{X}au_{2j}^{X}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S,w_{1}),$

where
$w_{1}=\bar{s_{2}}^{Y}c\bar{s_{1}}a\bar{s_{2}}^{X}=\bar{s_{1}}^{X}a\bar{s_{2}}c\bar{s_{1}}^{Y}$.
Since $w=a_{1}^{X}a_{2}^{Y}w_{1}b_{2}^{X}b_{1}^{Y}$, we have

$\displaystyle a_{1}s_{1}b_{1}-a_{2}s_{2}b_{2}$ $\displaystyle=$
$\displaystyle
a_{1}^{X}a_{2}^{Y}(\bar{s_{2}}^{Y}cs_{1}a\bar{s_{2}}^{X}-\bar{s_{1}}^{X}as_{2}c\bar{s_{1}}^{Y})b_{2}^{X}b_{1}^{Y}$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S,w).$

This completes the proof. $\square$

###### Lemma 3.3

Let $S\subset k\langle X\rangle\otimes k\langle Y\rangle$ with each $s\in S$
monic and $Irr(S)=\\{w\in N|w\neq a\overline{s}b,\ a,b\in N,\ s\in S\\}$. Then
for any $f\in k\langle X\rangle\otimes k\langle Y\rangle$,

$f=\sum_{a_{i}\bar{s_{i}}b_{i}\leq\bar{f}}\alpha_{i}a_{i}s_{i}b_{i}+\sum_{u_{j}\leq\bar{f}}\beta_{j}u_{j},$

where $\alpha_{i},\ \beta_{j}\in k,\ a_{i},b_{i}\in N,\ s_{i}\in S\
\mbox{and}\ u_{j}\in Irr(S)$.

Proof. Let $f=\sum\limits_{i}\alpha_{i}u_{i}\in k\langle X\rangle\otimes
k\langle Y\rangle$, where $0\neq{\alpha_{i}\in{k}}$ and $u_{1}>u_{2}>\cdots$.
If $u_{1}\in{Irr(S)}$, then let $f_{1}=f-\alpha_{1}u_{1}$. If
$u_{1}\not\in{Irr(S)}$, then there exist some $s\in{S}$ and $a_{1},b_{1}\in
N$, such that $\bar{f}=a_{1}\bar{s_{1}}b_{1}$. Let
$f_{1}=f-\alpha_{1}a_{1}s_{1}b_{1}$. In both cases, we have
$\bar{f_{1}}<\bar{f}$. Then the result follows from the induction on
$\bar{f}$. $\square$

From the above lemmas, we reach the following theorem:

###### Theorem 3.4

(Composition-Diamond lemma for tensor product $k\langle X\rangle\otimes
k\langle Y\rangle$) Let $S\subset k\langle X\rangle\otimes k\langle Y\rangle$
with each $s\in S$ monic and $<$ the order on $N=X^{*}Y^{*}$ as before. Then
the following statements are equivalent:

  1. (1)

$S$ is a Gröbner-Shirshov basis in $k\langle X\cup Y|T\rangle$.

  2. (2)

$f\in Id(S)\Rightarrow\overline{f}=a\overline{s}b$ for some $a,b\in N,\ s\in
S$.

  3. (3)

$Irr(S)=\\{w\in N|w\neq a\overline{s}b,\ a,b\in N,\ s\in S\\}$ is a $k$-linear
basis for the factor $k\langle X\cup Y|T\rangle/Id(S)$.

Proof: $(1)\Rightarrow(2)$. Suppose that $0\neq f\in Id(S)$. Then
$f=\sum\alpha_{i}a_{i}s_{i}b_{i}$ for some $\alpha_{i}\in k,\ a_{i},b_{i}\in
N,\ s_{i}\in S$. Let $w_{i}=a_{i}\overline{s}_{i}b_{i}$ and
$w_{1}=w_{2}=\cdots=w_{l}>w_{l+1}\geq\cdots$. We will prove that
$\overline{f}=a\overline{s}b$ for some $a,b\in N,\ s\in S$, by using induction
on $l$ and $w_{1}$. If $l=1$, then the result is clear. If $l>1$, then
$w_{1}=a_{1}\bar{s_{1}}b_{1}=a_{2}\bar{s_{2}}b_{2}$. Now, by (1) and Lemma
3.2, $a_{1}s_{1}b_{1}\equiv a_{2}s_{2}b_{2}\ \ mod(S,w_{1})$. Thus,

$\displaystyle\alpha_{1}a_{1}s_{1}b_{1}+\alpha_{2}a_{2}s_{2}b_{2}$
$\displaystyle=$
$\displaystyle(\alpha_{1}+\alpha_{2})a_{1}s_{1}b_{1}+\alpha_{2}(a_{2}s_{2}b_{2}-a_{1}s_{1}b_{1})$
$\displaystyle\equiv$ $\displaystyle(\alpha_{1}+\alpha_{2})a_{1}s_{1}b_{1}\ \
\ \ \ \ mod(S,w_{1}).$

By induction on $l$ and $w_{1}$, we have the result.

$(2)\Rightarrow(3)$. For any $0\neq f\in k\langle X\cup Y|T\rangle$, by Lemma
3.3, we can express $f$ as

$f=\sum\alpha_{i}a_{i}s_{i}b_{i}+\sum\beta_{j}u_{j},$

where $\alpha_{i},\ \beta_{j}\in k,\ a_{i},b_{i}\in N,\ s_{i}\in S\
\mbox{and}\ u_{j}\in Irr(S)$. Then $Irr(S)$ generates the factor algebra.
Moreover, if $0\neq h=\sum\beta_{j}u_{j}\in Id(S)$, $u_{j}\in
Irr(S),u_{1}>u_{2}>\cdots\ and\ \beta_{1}\neq 0$, then
$u_{1}=\bar{h}=a\bar{s}b$ for some $a,b\in N,\ s\in S$ by (2), a
contradiction. This shows that $Irr(S)$ is a linear basis of the factor
algebra.

$(3)\Rightarrow(1)$. For any $f,\ g\in S$, we have $h=(f,g)_{w}\in Id(S)$. The
result is trivial if $(f,g)_{w}=0$. Assume that $(f,g)_{w}\neq 0$. Then, by
Lemma 3.3 and (3), we have

$h=\sum_{a_{i}\bar{s_{i}}b_{i}\leq\bar{h}}\alpha_{i}a_{i}s_{i}b_{i}.$

Now, by noting that $\bar{h}=\overline{(f,g)_{w}}<w$, we know that (1) holds.
$\square$

Remark: Theorem 3.4 is valid for any monomial order on $X^{*}Y^{*}$.

Remark: Theorem 3.4 is exact the Composition-Diamond lemma for associative
algebras (Lemma 2.1) when $Y=\emptyset$.

##  4 Applications

Now, we give some applications of Theorem 3.4.

###### Example 4.1

Suppose that for the deg-lex order, $S_{1}$ and $S_{2}$ are Gröbner-Shirshov
bases in $k\langle X\rangle$ and $k\langle Y\rangle$ respectively. Then for
the deg-lex order on $X^{*}Y^{*}$, $S_{1}\cup S_{2}$ is a Gröbner-Shirshov
basis in $k\langle X\cup Y|T\rangle=k\langle X\rangle\otimes k\langle
Y\rangle$. It follows that $k\langle X|S_{1}\rangle\otimes k\langle
Y|S_{2}\rangle=k\langle X\cup Y|T\cup S_{1}\cup S_{2}\rangle$.

Proof:  The possible compositions in $S_{1}\cup S_{2}$ are $X$-including only,
$X$-intersection only, $Y$-including only and $Y$-intersection only. Suppose
$f,g\in S_{1}$ and $(f,g)_{w_{1}}\equiv 0\ \ mod(S_{1},w_{1})$ in $k\langle
X\rangle$. Then in $k\langle X\cup Y|T\rangle$, $(f,g)_{w}=(f,g)_{w_{1}}c$,
where $w=w_{1}c$ for any $c\in Y^{*}$. From this it follows that each
composition in $S_{1}\cup S_{2}$ is trivial modulo $S_{1}\cup S_{2}$.
$\square$

A special case of Example 4.1 is the following.

###### Example 4.2

Let $X,Y$ be linearly ordered sets, $k[X]$ the free commutative associative
algebra generated by $X$. Then
$S=\\{x_{i}x_{j}=x_{j}x_{i}|x_{i}>x_{j},x_{i},x_{j}\in X\\}$ is a Gröbner-
Shirshov basis in $k\langle X\rangle\otimes k\langle Y\rangle$ with respect to
the deg-lex order. Therefore, $k[X]\otimes k\langle Y\rangle=k\langle X\cup
Y|T\cup S\rangle$.

In [12], a Gröbner-Shirshov basis in $k\langle X\rangle$ is constructed by
lifting a commutative Gröbner basis and adding commutators. Let $X$ be a well-
ordered set, $[X]$ the free commutative monoid generated by $X$ and $k[X]$ the
polynomial ring. Let $S_{1}=\\{h_{ij}=x_{i}x_{j}-x_{j}x_{i}|\ i>j\\}\subset
k\langle X\rangle$. Consider the natural map $\gamma:k\langle
X\rangle\rightarrow k[X]$ taking $x_{i}$ to $x_{i}$ and the _lexicographic
splitting_ of $\gamma$, which is defined as the $k$-linear map

$\delta:k[X]\rightarrow k\langle X\rangle,\ \ x_{i_{1}}x_{i_{2}}\cdots
x_{i_{r}}\mapsto x_{i_{1}}x_{i_{2}}\cdots x_{i_{r}}\ \ if\ \ i_{1}\leq
i_{2}\cdots\leq i_{r}.$

For any $u\in[X]$, we present $u=x_{1}^{l_{1}}x_{2}^{l_{2}}\cdots
x_{n}^{l_{n}}$, where $l_{i}\geq 0$. We use any monomial order on $[X]$. For
any $f\in k[X]$, $\bar{f}$ means the leading monomial of $f$.

Following [12], we define an order on $X^{*}$ using the order
$x_{1}<x_{2}<\cdots<x_{n}$ as follows: for any $u,v\in X^{*}$,

$u>v\Leftrightarrow\gamma(u)>\gamma(v)\ \mbox{ in }\ [X]\ \mbox{ or }\
(\gamma(u)=\gamma(v)\ and\ u>_{lex}v).$

It is easy to check that this order is monomial on $X^{*}$ and
$\overline{\delta(s)}=\delta(\bar{s})$ where $s\in k[X]$. Moreover, for any
$v\in\gamma^{-1}(u)$, $v\geq\delta(u)$.

For any $m=x_{i_{1}}x_{i_{2}}\cdots x_{i_{r}}\in[X],\ i_{1}\leq
i_{2}\cdots\leq i_{r}$, denote the set of all the monomials
$u\in[x_{i_{1}+1},\cdots,x_{i_{r}-1}]$ by $U(m)$.

The proofs of the following lemmas are straightforward.

###### Lemma 4.3

Let $a,b\in X^{*},\ a=\delta(\gamma(a)),\ b=\delta(\gamma(b))$ and $s\in
k[X]$. If $w=a\delta(\bar{s})b=\delta(\gamma(ab)\bar{s})$, then, in $k\langle
X\rangle$,

$a\delta(s)b\equiv\delta(\gamma(ab)s)\ \ \ \ mod(S_{1},w).$

Proof: Suppose that $s=\bar{s}+s^{\prime}$ and
$h=a\delta(s)b-\delta(\gamma(ab)s)$. Since
$a\delta(\bar{s})b=\delta(\gamma(ab)\bar{s})$, we have
$h=a\delta(s^{\prime})b-\delta(\gamma(ab)s^{\prime})$, and $\bar{h}<w$. By
noting that
$\gamma(\delta(\gamma(ab)s^{\prime})=\gamma(\delta(\gamma(ab)s^{\prime}))$,
$h\equiv 0\ \ \ mod(S_{1},w)$. $\square$

###### Lemma 4.4

Let $f,g\in k[X],\ \bar{g}=x_{i_{1}}x_{i_{2}}\cdots x_{i_{r}}\ (i_{1}\leq
i_{2}\leq\cdots\leq i_{r})\ and\ w=\delta(\bar{f}\bar{g}).$ Then, in $k\langle
X\rangle$,

$\delta((f-\bar{f})g)\equiv\sum\alpha_{i}a_{i}\delta(u_{i}g)b_{i}\ \ \
mod(S_{1},w)$

where $\alpha_{i}\in k,\ a_{i}\in[x\in X|x\leq x_{i_{1}}],\ b_{i}\in[x\in
X|x\geq x_{i_{r}}],\ u_{i}\in U(\bar{g})$ and
$\gamma(\sum\alpha_{i}a_{i}u_{i}b_{i})=f-\bar{f}$.

###### Theorem 4.5

([12]) Let the orders on $[X]$ and $X^{*}$ be defined as above. If $S$ is a
minimal Gröbner basis in $k[X]$, then $S^{\prime}=\\{\delta(us)|s\in S,u\in
U(\bar{s})\\}\cup S_{1}$ is a Gröbner-Shirshov basis in $k\langle X\rangle$.

Proof: We will show that all the possible compositions of elements in
$S^{\prime}$ are trivial. Let $f=\delta(us_{1}),\ g=\delta(vs_{2})$ and
$h_{ij}=x_{i}x_{j}-x_{j}x_{i}\in S^{\prime}$.

$(1)$ $f\wedge g$

Case 1. $f$ and $g$ have a composition of including, i.e.,
$w=\delta(u\bar{s_{1}})=a\delta(v\bar{s_{2}})b$ for some $a,b\in X^{*}$ and
$a=\delta(\gamma(a)),b=\delta(\gamma(b))$.

If $s_{1}$ and $s_{2}$ have no composition in $k[X]$, i.e.,
$lcm(\bar{s_{1}}\bar{s_{2}})=\bar{s_{1}}\bar{s_{2}}$, then
$u=u^{\prime}\bar{s_{2}},\ \gamma(ab)v=u^{\prime}\bar{s_{1}}$ for some
$u^{\prime}\in[X]$. By Lemma 4.3 and Lemma 4.4, we have

$\displaystyle(f,g)_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})-a\delta(vs_{2})b$ $\displaystyle\equiv$
$\displaystyle\delta(us_{1})-\delta(\gamma(ab)vs_{2})$ $\displaystyle\equiv$
$\displaystyle\delta(u^{\prime}\bar{s_{2}}s_{1})-\delta(u^{\prime}\bar{s_{1}}s_{2})$
$\displaystyle\equiv$
$\displaystyle\delta(u^{\prime}(s_{1}-\bar{s_{1}})s_{2})-\delta(u^{\prime}(s_{2}-\bar{s_{2}})s_{1})$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w).$

Since, in $k[X]$, $S$ is a minimal Gröbner basis, the possible compositions
are only intersection. If $s_{1}$ and $s_{2}$ have composition of intersection
in $k[X]$, i.e., $(s_{1},s_{2})_{w^{\prime}}=a^{\prime}s_{1}-b^{\prime}s_{2}$,
where $a^{\prime},b^{\prime}\in[X],\
w^{\prime}=a^{\prime}\bar{s_{1}}=b^{\prime}\bar{s_{2}}$ and
$|w^{\prime}|<|\bar{s_{1}}|+|\bar{s_{2}}|$, then $w^{\prime}$ is a subword of
$\gamma(w)$. Therefore, we have
$w=\delta(tw^{\prime})=\delta(ta^{\prime}\bar{s_{1}})=\delta(tb^{\prime}\bar{s_{2}})$
and $u=ta^{\prime},\gamma(ab)v=tb^{\prime}$ for some $t\in[X]$. Then

$\displaystyle(f,g)_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})-a\delta(vs_{2})b$ $\displaystyle\equiv$
$\displaystyle\delta(us_{1})-\delta(\gamma(ab)vs_{2})$ $\displaystyle\equiv$
$\displaystyle\delta(ta^{\prime}s_{1})-\delta(tb^{\prime}s_{2})$
$\displaystyle\equiv$
$\displaystyle\delta(t(a^{\prime}s_{1}-b^{\prime}s_{2}))$
$\displaystyle\equiv$ $\displaystyle\delta(t(s_{1},s_{2})_{w^{\prime}})$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w)$

since $t\overline{(s_{1},s_{2})_{w^{\prime}}}<tw^{\prime}=\gamma(w).$

Case 2. If $f$ and $g$ have a composition of intersection, we may assume that
$\bar{f}$ is on the left of $\bar{g}$, i.e.,
$w=\delta(u\bar{s_{1}})a=b\delta(v\bar{s_{2}})$ for some $a,b\in X^{*}$ and
$a=\delta\gamma(a),b=\delta\gamma(b)$. Similarly to Case 1, we have to
consider whether $s_{1}$ and $s_{2}$ have compositions in $k[X]$ or not. One
can check that both cases are trivial mod$(S^{\prime},w)$ by Lemma 4.3 and
Lemma 4.4.

$(2)$ $f\wedge h_{ij}$

By noting that $\overline{h_{ij}}=x_{i}x_{j}$ can not be a subword of
$\bar{f}=\delta(u\bar{s_{1}})$ since $i>j$, only possible compositions are
intersection. Suppose that $\bar{s_{1}}=x_{i_{1}}\cdots x_{i_{r}}x_{i},\
(i_{1}\leq i_{2}\leq\cdots\leq i_{r}\leq i)$. Then
$\bar{f}=\delta(u\bar{s_{1}})=x_{i_{1}}vx_{i}$ for some $v\in k\langle
X\rangle,\ v=\delta\gamma(v)$ and $w=\delta(u\bar{s_{1}})x_{j}$.

If $j\leq i_{1}$, then

$\displaystyle(f,h_{ij})_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})x_{j}-x_{i_{1}}v(x_{i}x_{j}-x_{j}x_{i})$
$\displaystyle=$
$\displaystyle\delta(u(s_{1}-\bar{s_{1}}))x_{j}+x_{i_{1}}vx_{j}x_{i}$
$\displaystyle\equiv$ $\displaystyle
x_{j}\delta(u(s_{1}-\bar{s_{1}}))+x_{j}x_{i_{1}}vx_{i}$ $\displaystyle\equiv$
$\displaystyle x_{j}(\delta(u(s_{1}-\bar{s_{1}}))+\delta(u\bar{s_{1}}))$
$\displaystyle\equiv$ $\displaystyle x_{j}\delta(us_{1})$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w).$

If $j>i_{1}$, then $ux_{j}\in U(\bar{s_{1}})$ and

$\displaystyle(f,h_{ij})_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})x_{j}-x_{i_{1}}v(x_{i}x_{j}-x_{j}x_{i})$
$\displaystyle=$
$\displaystyle\delta(u(s_{1}-\bar{s_{1}}))x_{j}+x_{i_{1}}vx_{j}x_{i}$
$\displaystyle\equiv$
$\displaystyle\delta(ux_{j}(s_{1}-\bar{s_{1}}))+\delta(x_{i_{1}}vx_{i}x_{j})$
$\displaystyle\equiv$
$\displaystyle\delta(ux_{j}(s_{1}-\bar{s_{1}}))+\delta(ux_{j}\bar{s_{1}})$
$\displaystyle\equiv$ $\displaystyle\delta(ux_{j}s_{1})$ $\displaystyle\equiv$
$\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w).$

Then we complete the proof. $\square$

Now we extend $\gamma$ and $\delta$ as follows.

$\displaystyle\gamma\otimes\mathbf{1}:\ k\langle X\rangle\otimes k\langle
Y\rangle$ $\displaystyle\rightarrow$ $\displaystyle k[X]\otimes k\langle
Y\rangle,\ u^{X}u^{Y}\mapsto\gamma(u^{X})u^{Y},$
$\displaystyle\delta\otimes\mathbf{1}:\ k[X]\otimes k\langle Y\rangle$
$\displaystyle\rightarrow$ $\displaystyle k\langle X\rangle\otimes k\langle
Y\rangle,\ u^{X}u^{Y}\mapsto\delta(u^{X})u^{Y}.$

Any polynomial $f\in k[X]\otimes k\langle Y\rangle$ has a presentation
$f=\sum\alpha_{i}u^{X}_{i}u^{Y}_{i}$, where $\alpha_{i}\in k,u^{X}_{i}\in[X]\
and\ u^{Y}_{i}\in Y^{*}$.

Let the orders on $[X]$ and $Y^{*}$ be any monomial oeders respectively. We
order the set $[X]Y^{*}=\\{u=u^{X}u^{Y}|u^{X}\in[X],\ u^{Y}\in Y^{*}\\}$ as
follows. For any $u,v\in[X]Y^{*}$,

$u>v\Leftrightarrow u^{Y}>v^{Y}\ or\ (u^{Y}=v^{Y}\ \mbox{and}\ \
u^{X}>v^{X}).$

Now, we order $X^{*}Y^{*}$: for any $u,v\in X^{*}Y^{*}$,

$u>v\Leftrightarrow\gamma(u^{X})u^{Y}>\gamma(v^{X})v^{Y}\ \mbox{or}\
(\gamma(u^{X})u^{Y}=\gamma(v^{X})v^{Y}\ \mbox{and}\ u^{X}>_{lex}v^{X}).$

This order is clearly a monomial order on $X^{*}Y^{*}$.

The following definitions of compositions and Gröbner-Shirshov bases are
essentially from [25].

Let $f,g$ be monic polynomials of $k[X]\otimes k\langle Y\rangle$, $L$ the
least common multiple of $\bar{f}^{X}$ and $\bar{g}^{X}$.

$1.$ Inclusion

Let $\bar{g}^{Y}$ be a subword of $\bar{f}^{Y}$, say,
$\bar{f}^{Y}=c\bar{g}^{Y}d$ for some $c,d\in Y^{*}$. If
$\bar{f}^{Y}=\bar{g}^{Y}$ then $\bar{f}^{X}\geq\bar{g}^{X}$ and if
$\bar{g}^{Y}=1$ then we set $c=1$. Let $w=L\bar{f}^{Y}=Lc\bar{g}^{Y}d$. We
define the composition

$C_{1}(f,g,c)_{w}=\frac{L}{\bar{f}^{X}}f-\frac{L}{\bar{g}^{X}}cgd.$

$2.$ Overlap

Let a non-empty beginning of $\bar{g}^{Y}$ be a non-empty ending of
$\bar{f}^{Y}$, say,
$\bar{f}^{Y}=cc_{0},\bar{g}^{Y}=c_{0}d,\bar{f}^{Y}d=c\bar{g}^{Y}$ for some
$c,d,c_{0}\in Y^{*}$ and $c_{0}\neq 1$. Let $w=L\bar{f}^{Y}d=Lc\bar{g}^{Y}$.
We define the composition

$C_{2}(f,g,c_{0})_{w}=\frac{L}{\bar{f}^{X}}fd-\frac{L}{\bar{g}^{X}}cg.$

$3.$ External

Let $c_{0}\in Y^{*}$ be any associative word (possibly empty). In the case
that the greatest common divisor of $\bar{f}^{X}$ and $\bar{g}^{X}$ is non-
empty and $\bar{f}^{Y},\bar{g}^{Y}$ are non-empty, we define the composition

$C_{3}(f,g,c_{0})_{w}=\frac{L}{\bar{f}^{X}}fc_{0}\bar{g}^{Y}-\frac{L}{\bar{g}^{X}}\bar{f}^{Y}c_{0}g,$

where $w=L\bar{f}^{Y}c_{0}\bar{g}^{Y}$.

Let $S$ be a monic subset of $k[X]\otimes k\langle Y\rangle$. Then $S$ is
called a Gröbner-Shirshov basis (standard basis) if for any element $f\in
Id(S)$, $\bar{f}$ contains $\bar{s}$ as its subword for some $s\in S$.

It is defined as usual that a composition is trivial modulo $S$ and
corresponding $w$. We also have that $S$ is a Gröbner-Shirshov basis in
$k[X]\otimes k\langle Y\rangle$ if and only if all the possible compositions
of its elements are trivial. A Gröbner-Shirshov basis in $k[X]\otimes k\langle
Y\rangle$ is called minimal if for any $s\in S$ and all $s_{i}\in
S\setminus\\{s\\}$, $\bar{s_{i}}$ is not a subword of $\bar{s}$.

Similar to the proof of Theorem 4.5, we have the following theorem.

###### Theorem 4.6

Let the orders on $[X]Y^{*}$ and $X^{*}Y^{*}$ be defined as before. If $S$ is
a minimal Gröbner-Shirshov basis in $k[X]\otimes k\langle Y\rangle$, then
$S^{\prime}=\\{\delta(us)|s\in S,u\in U(\bar{s}^{X})\\}\cup S_{1}$ is a
Gröbner-Shirshov basis in $k\langle X\rangle\otimes k\langle Y\rangle$, where
$S_{1}=\\{h_{ij}=x_{i}x_{j}-x_{j}x_{i}|\ i>j\\}$.

Proof: We will show that all the possible compositions of elements in
$S^{\prime}$ are trivial.

For $s_{1},s_{2}\in S$, let $f=\delta(us_{1}),\ g=\delta(vs_{2}),\
h_{ij}=x_{i}x_{j}-x_{j}x_{i}\in S^{\prime}$ and
$L=lcm(\bar{s_{1}}^{X},\bar{s_{2}}^{X})$.

$1.$ $f\wedge g$

In this case, all the possible compositions of $f\wedge g$ are related the
ambiguities $w$’s (in the following, $a,b\in X^{*},\ c,d\in Y^{*}$).

_(1.1)_ $X$-inclusion only

$w^{X}=\delta(u\bar{s_{1}}^{X})=a\delta(v\bar{s_{2}}^{X})b$,
$w^{Y}=\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y}$ or
$w^{Y}=\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y}$.

_(1.2)_ $Y$-inclusion only

$w^{X}=\delta(u\bar{s_{1}}^{X})a\delta(v\bar{s_{2}}^{X})$ or
$w^{X}=\delta(v\bar{s_{2}}^{X})a\delta(u\bar{s_{1}}^{X})$,
$w^{Y}=\bar{s_{1}}^{Y}=c\bar{s_{2}}^{Y}d$.

_(1.3)_ $X,Y$-inclusion

$w=\delta(u\bar{s_{1}})=ac\delta(v\bar{s_{2}})bd$.

_(1.4)_ $X,Y$-skew-inclusion

$w^{X}=\delta(u\bar{s_{1}})^{X}=a\delta(v\bar{s_{2}}^{X})b$,
$w^{Y}=\bar{s_{2}}^{Y}=c\bar{s_{1}}^{Y}d$.

_(2.1)_ $X$-intersection only

$w^{X}=\delta(u\bar{s_{1}})^{X}a=b\delta(v\bar{s_{2}}^{X})$,
$w^{Y}=\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y}$ or
$w^{Y}=\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y}$.

_(2.2)_ $Y$-intersection only

$w^{X}=\delta(u\bar{s_{1}})^{X}a\delta(v\bar{s_{2}}^{X})$ or
$w^{X}=\delta(u\bar{s_{2}})^{X}a\delta(v\bar{s_{1}}^{X})$,
$w^{Y}=\bar{s_{1}}^{Y}c=d\bar{s_{2}}^{Y}$.

_(2.3)_ $X,Y$-intersection

$w^{X}=\delta(u\bar{s_{1}})^{X}a=b\delta(v\bar{s_{2}}^{X})$,
$w^{Y}=\bar{s_{1}}^{Y}c=d\bar{s_{2}}^{Y}$.

_(2.4)_ $X,Y$-skew-intersection

$w^{X}=\delta(u\bar{s_{1}})^{X}a=b\delta(v\bar{s_{2}}^{X})$,
$w^{Y}=c\bar{s_{1}}^{Y}=\bar{s_{2}}^{Y}d$.

_(3.1)_ $X$-inclusion and $Y$-intersection

$w^{X}=\delta(u\bar{s_{1}})^{X}=a\delta(v\bar{s_{2}}^{X})b$,
$w^{Y}=\bar{s_{1}}^{Y}c=d\bar{s_{2}}^{Y}$ or
$w^{Y}=c\bar{s_{1}}^{Y}=\bar{s_{2}}^{Y}d$.

_(3.2)_ $X$-intersection and $Y$-inclusion

$w^{X}=\delta(u\bar{s_{1}})^{X}a=b\delta(v\bar{s_{2}}^{X})$,
$w^{Y}=\bar{s_{1}}^{Y}=c\bar{s_{2}}^{Y}d$ or
$w^{Y}=\bar{s_{2}}^{Y}=c\bar{s_{1}}^{Y}d$.

We only check the cases of (1.1), (1.2) and (1.3). Other cases are similarly
checked.

_(1.1)_ $X$-inclusion only

Suppose that $w^{X}=\delta(u\bar{s_{1}}^{X})=a\delta(v\bar{s_{2}}^{X})b,\
a,b\in X^{*}$ and $\bar{s_{1}}^{Y},\ \bar{s_{2}}^{Y}$ are disjoint. There are
two cases to consider: $w^{Y}=\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y}$ and
$w^{Y}=\bar{s_{2}}^{Y}c\bar{s_{1}}^{Y}$, where $c\in Y^{*}$. We will only
prove the first case and the second is similar.

If $s_{1}$ and $s_{2}$ have no composition in $k[X]\otimes k\langle Y\rangle$,
i.e., $lcm(\bar{s_{1}},\bar{s_{2}})=\bar{s_{1}}\bar{s_{2}}$, then
$u=u^{\prime}\bar{s_{2}^{X}},\ \gamma(ab)v=u^{\prime}\bar{s_{1}^{X}}$ for some
$u^{\prime}\in[X]$. By the proof of Theorem 4.5, we have

$\displaystyle(f,g)_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})c\bar{s_{2}}^{Y}-\bar{s_{1}}^{Y}ca\delta(vs_{2})b$
$\displaystyle\equiv$
$\displaystyle\delta(us_{1}\gamma(c\bar{s_{2}}^{Y}))-\delta(\gamma(\bar{s_{1}}^{Y}c)\gamma(ab)vs_{2})$
$\displaystyle\equiv$
$\displaystyle\delta(u^{\prime}\bar{s_{2}}^{X}s_{1}c\bar{s_{2}}^{Y})-\delta(\bar{s_{1}}^{Y}cu^{\prime}\bar{s_{1}}^{X}s_{2})$
$\displaystyle\equiv$
$\displaystyle\delta(u^{\prime}s_{1}c\bar{s_{2}})-\delta(u^{\prime}\bar{s_{1}}cs_{2})$
$\displaystyle\equiv$
$\displaystyle\delta(u^{\prime}(s_{1}-\bar{s_{1}})cs_{2})-\delta(u^{\prime}s_{1}c(s_{2}-\bar{s_{2}}))$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w).$

If $s_{1}$ and $s_{2}$ have composition of external (the elements of $S$ have
no composition of inclusion because $S$ is minimal and $s_{1}$ and $s_{2}$
have no composition of overlap because $s_{1}^{Y}$ and $s_{2}^{Y}$ are
disjoint ) in $k[X]\otimes k\langle Y\rangle$, i.e.,
$C_{3}(s_{1},s_{2},c)_{w^{\prime}}=\frac{L}{\bar{s_{1}}^{X}}s_{1}\gamma(c\bar{s_{2}}^{Y})-\frac{L}{\bar{s_{2}}^{X}}\gamma(\bar{s_{1}}^{Y}c)s_{2}=t_{2}s_{1}\gamma(c\bar{s_{2}}^{Y})-t_{1}\gamma(\bar{s_{1}}^{Y}c)s_{2}$
where $gcd(\bar{s_{1}}^{X},\bar{s_{2}}^{X})=t\neq
1,\bar{s_{1}}^{X}=tt_{1},\bar{s_{2}}^{X}=tt_{2}$ and $L=tt_{1}t_{2},\
w^{\prime}=L\gamma(\bar{s_{1}}^{Y}c\bar{s_{2}}^{Y})$, then $w^{\prime}$ is a
subword of $\gamma(w)$. Therefore, we have $w=\delta(mw^{\prime})$ and
$u=mt_{2},\gamma(ab)v=mt_{1}$ since $ut_{1}=\gamma(ab)vt_{2}$ and
$gcd(t_{1},t_{2})=1$. Then

$\displaystyle(f,g)_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})c\bar{s_{2}}^{Y}-\bar{s_{1}}^{Y}ca\delta(vs_{2})b$
$\displaystyle\equiv$
$\displaystyle\delta(us_{1}\gamma(c\bar{s_{2}}^{Y}))-\delta(\gamma(\bar{s_{1}}^{Y}c)\gamma(ab)vs_{2})$
$\displaystyle\equiv$
$\displaystyle\delta(mt_{2}s_{1}\gamma(c\bar{s_{2}}^{Y}))-\delta(mt_{1}\gamma(\bar{s_{1}}^{Y}c)s_{2})$
$\displaystyle\equiv$
$\displaystyle\delta(mC_{3}(s_{1},s_{2},c)_{w^{\prime}})$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w)$

since $m\overline{C_{3}(s_{1},s_{2},c)_{w^{\prime}}}<mw^{\prime}=\gamma(w).$

_(1.2)_ $Y$-inclusion only

Suppose that $w^{Y}=\bar{s_{1}}^{Y}=c\bar{s_{2}}^{Y}d,\ c,d\in Y^{*}$ and
$\delta(u\bar{s_{1}}^{X}),\ \delta(v\bar{s_{2}}^{X})$ are disjoint. Then there
are two compositions according to
$w^{X}=\delta(u\bar{s_{1}}^{X})a\delta(v\bar{s_{2}}^{X})$ and
$w^{X}=\delta(v\bar{s_{2}}^{X})a\delta(u\bar{s_{1}}^{X})$ for $a\in X^{*}$. We
only prove the first.

$\displaystyle(f,g)_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})a\delta(v\bar{s_{2}}^{X})-\delta(u\bar{s_{1}}^{X})ac\delta(vs_{2})d$
$\displaystyle\equiv$
$\displaystyle\delta(us_{1}\gamma(a)v\bar{s_{2}}^{X}-u\bar{s_{1}}^{X}\gamma(a)v\gamma(c)s_{2}\gamma(d))$
$\displaystyle\equiv$
$\displaystyle\delta(u\gamma(a)v(s_{1}\bar{s_{2}}^{X}-\bar{s_{1}}^{X}\gamma(c)s_{2}\gamma(d)))$
$\displaystyle\equiv$
$\displaystyle\delta(u\gamma(a)vC_{1}(s_{1},s_{2},\gamma(c))_{w^{\prime}})$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w),$

where
$w^{\prime}=\bar{s_{1}}^{X}\bar{s_{2}}^{X}\bar{s_{1}}^{Y}=\bar{s_{1}}^{X}\bar{s_{2}}^{X}\gamma(c)\bar{s_{2}}^{Y}\gamma(d)$
and
$\overline{u\gamma(a)vC_{1}(s_{1},s_{2},\gamma(c))_{w^{\prime}}}<u\gamma(a)vw^{\prime}=\gamma(w)$.

_(1.3)_ $X,Y$-inclusion

We may assume that $\bar{g}$ is a subword of $\bar{f}$, i.e.,
$w=\delta(u\bar{s_{1}})=ac\delta(v\bar{s_{2}})bd$, $a,b\in X^{*}$, $c,d\in
Y^{*}$. Then $u\bar{s_{1}}^{X}=\gamma(ab)v\bar{s_{2}}^{X}=mL$ for some
$m\in[X]$, $u\bar{s_{1}}^{Y}=\gamma(c)\bar{s_{2}}^{Y}\gamma(d)$.

$\displaystyle(f,g)_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})-ac\delta(vs_{2})bd$ $\displaystyle\equiv$
$\displaystyle\delta(us_{1}-\gamma(ac)vs_{2}\gamma(bd))$ $\displaystyle\equiv$
$\displaystyle\delta(m\frac{L}{\bar{s_{1}}^{X}}s_{1}-m\frac{L}{\bar{s_{2}}^{X}}\gamma(c)s_{2}\gamma(d))$
$\displaystyle\equiv$
$\displaystyle\delta(mC_{1}(s_{1},s_{2},\gamma(c))_{w^{\prime}})$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w),$

where $w^{\prime}=L\gamma(c)\bar{s_{2}}^{Y}\gamma(d)$ and
$\overline{mC_{1}(s_{1},s_{2},c)_{w^{\prime}}}<mw^{\prime}=\gamma(w)$.

$(2)$ $f\wedge h_{ij}$

Similar to the proof of Theorem 4.5, they only have compositions of
$X$-intersection. Suppose that $\bar{s_{1}}^{X}=x_{i_{1}}\cdots
x_{i_{r}}x_{i},\ (i_{1}\leq i_{2}\leq\cdots\leq i_{r}\leq i)$. Then
$\bar{f}=\delta(u\bar{s_{1}})=x_{i_{1}}vx_{i}\bar{s_{1}}^{Y}$ for some $v\in
k\langle X\rangle,\ and\ v=\delta\gamma(v)$ and
$w=\delta(u\bar{s_{1}})x_{j}\bar{s_{1}}^{Y}.$

If $j\leq i_{1}$, then

$\displaystyle(f,h_{ij})_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})x_{j}-x_{i_{1}}v\bar{s_{1}}^{Y}(x_{i}x_{j}-x_{j}x_{i})$
$\displaystyle=$
$\displaystyle\delta(u(s_{1}-\bar{s_{1}}))x_{j}+x_{i_{1}}vx_{j}x_{i}\bar{s_{1}}^{Y}$
$\displaystyle\equiv$ $\displaystyle
x_{j}\delta(u(s_{1}-\bar{s_{1}}))+x_{j}x_{i_{1}}vx_{i}\bar{s_{1}}^{Y}$
$\displaystyle\equiv$ $\displaystyle
x_{j}(\delta(u(s_{1}-\bar{s_{1}}))+\delta(u\bar{s_{1}}))$
$\displaystyle\equiv$ $\displaystyle x_{j}\delta(us_{1})$
$\displaystyle\equiv$ $\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w).$

If $j>i_{1}$, then $ux_{j}\in U(\bar{s_{1}})$ and

$\displaystyle(f,h_{ij})_{w}$ $\displaystyle=$
$\displaystyle\delta(us_{1})x_{j}-x_{i_{1}}v\bar{s_{1}}^{Y}(x_{i}x_{j}-x_{j}x_{i})$
$\displaystyle=$
$\displaystyle\delta(u(s_{1}-\bar{s_{1}}))x_{j}+x_{i_{1}}vx_{j}x_{i}\bar{s_{1}}^{Y}$
$\displaystyle\equiv$
$\displaystyle\delta(ux_{j}(s_{1}-\bar{s_{1}}))+\delta(x_{i_{1}}vx_{i}x_{j}\bar{s_{1}}^{Y})$
$\displaystyle\equiv$
$\displaystyle\delta(ux_{j}(s_{1}-\bar{s_{1}}))+\delta(ux_{j}\bar{s_{1}})$
$\displaystyle\equiv$ $\displaystyle\delta(ux_{j}s_{1})$ $\displaystyle\equiv$
$\displaystyle 0\ \ \ \ \ \ \ mod(S^{\prime},w).$

This completes the proof. $\square$

## References

  * [1] G. M. Bergman, The diamond lemma for ring theory, Adv. in Math., 29, 178-218(1978).
  * [2] L. A. Bokut, Unsolvability of the word problem, and subalgebras of finitely presented Lie algebras, Izv. Akad. Nauk. SSSR Ser. Mat., 36, 1173-1219(1972).
  * [3] L. A. Bokut, Imbeddings into simple associative algebras, Algebra i Logika, 15, 117-142(1976).
  * [4] L. A. Bokut, Yuqun Chen, Gröbner-Shirshov bases: some new results, Proceedings of the 2nd International Congress of Algebras and Combinations, Scientific World, 2008, 35-56.
  * [5] L. A. Bokut, Yuqun Chen and Cihua Liu, Gröbner-Shirshov bases for dialgebras, submitted.
  * [6] L. A. Bokut, Y. Fong and W. F. Ke, Composition Diamond Lemma for associative conformal algebras. J. Algebra, 272, 739-774(2004).
  * [7] L. A. Bokut and K. P. Shum, Relative Gröbner-Shirshov bases for algebras and groups, Algebra and Analisis, 19(6), 1-12(2007). (in Russian)
  * [8] B. Buchberger, An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal , Ph.D. thesis, University of Innsbruck, Austria, (1965). (in German)
  * [9] B. Buchberger, An algorithmical criteria for the solvability of algebraic systems of equations, Aequationes Math., 4, 374-383(1970). (in German)
  * [10] Chen, K. T. Fox and R. C. Lyndon, Free differential calculus, IV. Ann. of Math., 63, 294-397(1958).
  * [11] E. S. Chibrikov, On free Lie conformal algebras,Vestnik Novosibirsk State University, 4(1), 65-83(2004).
  * [12] D. Eisenbud, I. Peeva and B. Sturmfels, Non-commutative Gröbner bases for commutative algebras, Proc. Amer. Math. Soc., 126(3), 687-691(1998).
  * [13] D. R. Farkas, C. D. Feustel and E. L. Green, Synergy in the theories of Gröbner bases and path algebras, Can. J. Math., 45, 727-739(1993).
  * [14] H. Hironaka, Resolution of singulatities of an algebraic variety over a field if characteristic zero, I, II. Ann. Math., 79, 109-203, 205-326(1964).
  * [15] L. Hellström, The Diamond Lemma for Power Series Algebras, (doctorate thesis), 2002.
  * [16] S.-J. Kang and K.-H. Lee, Gröbner-Shirshov bases for representation theory, J. Korean Math. Soc., 37, 55-72(2000).
  * [17] S.-J. Kang and K.-H. Lee, Linear algebraic approach to Gröbner-Shirshov basis theory, J. Algebra, 313, 988-1004(2007).
  * [18] Y. Kobayashi, Gröbner bases on algebras based on well-ordered semigroups, Math. Appl. Sci. Tech., to appear.
  * [19] R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977.
  * [20] W. Magnus, Über diskontinuierliche Gruppen mit einer definierenden Relation (Der Freiheitssatz), J. Reine Angew. Math., 163, 141-165(1930).
  * [21] W. Magnus, Das Identitäts problem für Gruppen mit einer definierenden Relation, Math. Ann., 106, 295-307(1932).
  * [22] W. Magnus, A. Karrass and D. Solitar, Combinatorial group theory, Dover Publications, Inc. New Youk, 1976.
  * [23] A. A. Mikhalev, Shirshov’s composition techniques in Lie superalgebras (non-commutative Gröbner bases), Trudy Sem. Petrovsk. 18, 277-289(1995). English translation: J. Math. Sci., 80, 2153-2160(1996).
  * [24] A. A. Mikhalev and E. A. Vasilieva, Standard bases of ideals of free supercommutative polynomial algebra ($\varepsilon$-Grobner bases), Proc. Second International Taiwan-Moscow Algebra Workshop, Springer-Verlag, 2003.
  * [25] A. A. Mikhalev and A. A. Zolotykh, Standard Gröbner-Shirshov bases of free algebras over rings, I. Free associative algebras, International Journal of Algebra and Computation, 8(6), 689-726(1998).
  * [26] M. H. A. Newman, On theories with a combinatorial definition of “equivalence.” Ann. of Math., 43, 223-243(1942).
  * [27] A. I. Shirshov, On free Lie rings, Mat. Sb., 45(87), 113-122(1958). (in Russian)
  * [28] A. I. Shirshov, Some algorithmic problem for $\varepsilon$-algebras, Sibirsk. Mat. Z., 3, 132-137(1962). (in Russian)
  * [29] A. I. Shirshov, Some algorithmic problem for Lie algebras, Sibirsk. Mat. Z., 3, 292-296(1962) (in Russian); English translation in SIGSAM Bull., 33(2), 3-6(1999).
  * [30] T. Stokes, Gröbner-Shirshov bases in exterior algebras, J. Automated Reasoing, 6, 233-250(1990).
  * [31] A. I. Zhukov, Complete systems of defining relations in noassociative algebras, Mat. Sbornik, 69(27), 267-280(1950).


11institutetext<EMAIL_ADDRESS>
# Maximum-Profit Routing Problem with Multiple Vehicles per Site

Bogdan Armaselu

###### Abstract

We consider the Maximum-Profit Routing Problem (MPRP), a variant of pick-up
routing problem introduced in [1, 3], in which the goal is to maximize total
profit. The original MPRP restricts vehicles to visit a site at most once. In
this paper, we consider extensions of MPRP, in which a site may be visited by
a vehicle multiple times. Specifically, we consider two versions: one in which
the quantity to be picked up at each site is constant in time (MPRP-M), and
one with time-varying supplied quantities, which increase linearly in time
(MPRP-VS). For each of these versions, we come up with a constant-factor
polynomial-time approximaltion scheme.

###### Keywords:

routing, maximum-profit, pick-up, variable supply, multiple vehicles

##  1 Introduction

Consider a set of $n$ points in the plane, called sites. Each site $S_{i}$
supplies a quantity $q_{i}$ of a certain unit-priced product that needs to be
collected and has an operating time window of $[s_{i},e_{i}]$, where $0\leq
s_{i}\leq e_{i}\leq T$, for some constant $T>0$, $\forall{i=1,\dots,n}$. The
distance $d_{i,j}$ between sites $s_{i}$ and $s_{j}$ is the euclidean
distance. We are also given a fleet of $m$ vehicles
$V=\\{v_{1},\dots,v_{m}\\}$, each having the same capacity $Q$. All vehicles
are assumed to travel at unit speed and have unit fuel consumption per
distance travelled. Only one vehicle may visit any given site and all vehicles
must start and end their tour at the same given depot $D(x_{D},y_{D})$. The
goal is to compute, for every vehicle $v_{k}$, a route $r_{k}$ that collects a
quantity $q^{k}_{i}$ of the good such that the total profit of all routes is
maximized, where the profit of a route $r_{k}$ is the total quantity collected
$\sum_{s_{i}\in r_{k}}{q^{k}_{i}}$ (called reward) minus the total distance
travelled via $r_{k}$ (called costs). We call this problem the Maximum Profit
pick-up Routing Problem (MPRP).

MPRP was introduced in [1, 3], which focuses on the case with fixed quantities
and only one vehicle per site. In this paper, we consider the case where
multiple vehicles may visit one site. We first study the MPRP problem with
Multiple Vehicles Per Site and fixed quantities (MPRP-M), in which $q_{i}$’s
are constant in time. We also consider the MPRP problem with Multiple Vehicles
Per Site and Time-Variable Quantities supplied (MPRP-MVS), in which
$q_{i}(t)$’s are 0 for $t\notin[s_{i},e_{i}]$ and linearly increasing in time
for $t\in[s_{i},e_{i}]$. Compared to the single vehicle versions, this adds
the availability constraint that $\sum_{j,u\leq t}{q_{iju}}\leq
q_{i}(t),\forall{i,t}$. However, a vehicle may not visit a site more than
once.

MPRP is known to be strongly NP-hard [3]. By extensions, all the variants
proposed above are also strongly NP-hard. That is, they have no algorithm
running in time polynomial in the value of the input unless P = NP.

Applications of the results presented in this paper include public
transportation in various settings, such as cities [3], inter-city railway
transportation, domestic or international flight, etc. Another important
application is in for-profit waste pick-up, in which the reward is
proportional to the amount of waste collected.

###  1.1 Related work

General graph TSP is proven to be hard to approximate within any constant
factor [16]. However, TSP on special graphs, such as complete graphs with
metric distances ane euclidean distances, do have approximation algorithms.
For instance, general metric TSP has a $O(n^{3})$ time $1.5$-approximation
algorithm by Christofides [9]. Euclidean metric TSP even has a PTAS achieving
$1+\epsilon$ performance ratio via Arora’s $O(n(\log n)^{O(1/\epsilon)})$ time
algorithm [4]. On the other hand, metric TSP was shown to be APX-complete by
Papadimitriou et. al [15] and, to date, the best known lower bound is
$123/122$ by Karpinski et. al [14].

Various generalizations of TSP have also been considered. Bansal et. al
introduced the Deadline-TSP and the Time Window-TSP problems [5]. In Deadline-
TSP, every site $S_{i}$ has a deadline $D_{i}$, while in Time Window-TSP,
every site $S_{i}$ has a time window $[s_{i},e_{i}]$. Both of these problems
associate every site $S_{i}$ with a reward $q_{i}$ and ask for a single tour
that maximized the total reward collected. For Deadline-TSP, they provide an
$O(\log n)$-approximation algorithm, while for Time Window-TSP they describe
an $O(\log^{2}n)$-approximation.

There are also variants involving multiple vehicles. Fisher introduced the
Vehicle Routing Problem with capacity constraint (VRP), in which a fleet of
$m$ vehicles is given, and each customer $S_{i}$ has a demand $q_{i}$ of a
certain product [11]. Their solution uses an iterative lagrangian relaxation
of the constraints. Later, Fisher et. al introduced the Vehicle Routing
Problem with Time Windows and capacity constraints (VRPTW), in which customers
have a demand $q_{i}$ of the product, as well as operating time windows, and
the $m$ vehicles have non-uniform capacity constraints [12]. They solve this
problem using a linear programming approach.

Golden et. al studied the Capacitated Arc Routing Problem (CARP) with uniform
vehicle capacity where edges, rather than vertices, have customer demands, and
the goal is to minimize the travelled distance subject to meeting all demands.
They prove that CARP can be approximated within a constant factor when the
triangle inequality is satisfied [13]. Later, van Bevern extended the result
to general undirected graphs [6].

Wang et. al considered the Multi-Depot Vehicle Routing Problem (MDVRPTW) with
Timw Windows and Multi-type Vehicle Number Limits [17]. The main difference to
our problem is that the goal is to minimize the number of vehicles used (if
feasible) or maximize the number of visited customers (if infeasible).
Although they solve the problem using a genetic algorithm approach, their
algorithm is iterative and has no performance guarantee with respect to the
approximation factor.

Versions of vehicle routing with multiple vehicles per customer have also been
considered. In [10], Drexl does a comprehensive survey of variations of
vehicle routing with multiple synchronization constraints (VRPMS), e.g. in
which a customer may be visited by two vehicles (VRPTT) [7], or by 3 or more
vehicles [8].

Armaselu and Daescu solved the fixed-supply, single vehicle version of MPRP
[1, 3]. They provide two APXs for MPRP, both running in $O(n^{11})$ time,
assuming $q_{i}(l_{i})\leq\alpha q_{j}(l_{j}),\forall{i,j=1,\dots,n}$, for
some constant $\alpha>1$. The best performance ratio, $15\log T$, among the
two algorithms, is achieved by an approach involving well-separated pair
decompositions.

###  1.2 Our contributions

We give a constant-factor approximation algorithm for MPRP-M and MPRP-MVS,
which uses clever reductions to some known problems. Specifically, we solve
MPRP-M in $O(n^{11})$ time for an approximation ratio of $\simeq 44\log T$ and
MPRP-MVS in $O((\frac{n}{\epsilon})^{11})$ time within an approximation ratio
of $44\log T(1+\epsilon)(1+\frac{1}{1+\sqrt{m}})^{2}$.

The rest of the paper is structured as follows. In Section 2, we describe our
MPRP-M algorthm, and then, in Section 3, we describe our solution to MPRP-MVS.
Finally, in Section 4, we conclude and list some future directions.

##  2 MPRP-M

We come up with a reduction from MPRP-M to MPRP.

Let $d(0,i)=d(i,0)$ be the distance from the depot to site
$S_{i},\forall{i:1\leq i\leq n}$.

An instance $I$ of MPRP (or MPRP-M) can be described as a set
$I=(S=\\{S_{i}:1\leq i\leq n\\},D=(x_{0},y_{0}),d=\\{d(i,j):0\leq i<j\leq
n\\},T,Q,m)$, where $S_{i}=(x_{i},y_{i},s_{i},e_{i},q_{i})$.

A solution $Sol$ to $I$ is a set $Sol=(R,P)$. Here $R$ is a routing function
assigning, to every pair of sites or depot $(i,j),0\leq i,j\leq n$, a number
$k(i,j):0\leq k(i,j)\leq m$, denoting the index of the vehicle operating the
path from $S_{i}$ to $S_{j}$, or 0 if no such vehicle exists. $P$ is a pickup
function assigning, to every site $S_{i}$ on vehicle $v_{k}$’s route, a
quantity $q_{k,i}\leq q_{i},Q$ to be picked up by $v_{k}$.

A solution $Sol^{\prime}$ to $I^{\prime}$ is a routing function with the same
properties as the function $R$ in$Sol$.

Denote by $MPRP$ (resp., $MPRP-M$) the set of MPRP (resp., MPRP-M) instances.

Starting from $I=(\\{(x_{i},y_{i},s_{i},e_{i},q_{i}):1\leq i\leq
n\\},(x_{0},y_{0}),\\{d_{i,j}:0\leq i<j\leq n\\},T,Q,m)\in MPRP-M$, let
$I^{\prime}=(\\{(x_{i},y_{i},s_{i},e_{i},q_{i}):1\leq i\leq
n\\},(x_{0},y_{0}),\\{d_{i,j}:0\leq i<j\leq n\\},T,Q,m)\in MPRP$. That is,
$I^{\prime}$ has the same nodes and distances as $I$. We solve $I^{\prime}$
using the algorithm in [3] and denote by $Sol^{\prime}$ the solution.

We transform the solution $Sol^{\prime}$ to an MPRP instance $I^{\prime}$,
into a solution $Sol$ to an MPRP-M instance $I$, as follows. For every vehicle
$v_{k}$ of $I^{\prime}$, let $Q_{k}$ be the total quantity collected by
$v_{k}$ from its assigned tour $\tau^{\prime}_{k}\in Sol^{\prime}$. It may be
possible that some sites in $\tau^{\prime}_{k}$ need to be visited multiple
times in $I$, producing a new tour $\tau_{k}\in Sol$. To figure out which ones
need to, we look at tuples of sites
$(S_{u},S_{u^{\prime}},S_{i},S_{i^{\prime}},S_{j},S_{j^{\prime}})\in
S^{2}\times(S\cup D)^{4}$ in $I^{\prime}$ where

$\begin{cases}S_{u}\in\tau^{\prime}_{k}\\\
S_{u^{\prime}}\in\tau^{\prime}_{k^{\prime}}\\\ S_{i},S_{j}$ consecutive in
$\tau^{\prime}_{k}\\\ S_{i^{\prime}},S_{j^{\prime}}$ consecutive in
$\tau^{\prime}_{k^{\prime}}\end{cases}$ (1)

The goal is to maximize the total amount picked up from $\tau^{\prime}_{k}$
and $\tau^{\prime}_{k^{\prime}}\cup\\{S_{u}\\}$. Denote by
$q_{u^{\prime},k^{\prime}}$ the quanity assigned to be picked up by
$v_{k^{\prime}}$ from $S_{u^{\prime}}$, by $q_{u^{\prime},k}$ the quanity
assigned to be picked up by $v_{k}$ from $S_{u^{\prime}}$, and by $q_{u,k}$
the quanity assigned to be picked up by $v_{k}$ from $S_{u}$. We have

$\begin{cases}Q_{k}+q_{u,k}+q_{u^{\prime},k}-q_{u^{\prime}}\leq Q\\\
Q_{k^{\prime}}+q_{u^{\prime},k^{\prime}}\leq Q\\\
q_{u^{\prime},k}+q_{u^{\prime},k^{\prime}}\leq q_{u^{\prime}}\\\ q_{u,k}\leq
q_{u}\end{cases}$ (2)

and our goal is to maximize
$q_{u^{\prime},k}+q_{u^{\prime},k^{\prime}}+q_{u,k}$. To do that, we set
$x=q_{u,k},y=q_{u^{\prime},k},z=q_{u^{\prime},k^{\prime}}$, and we come to the
following linear program.

Minimize $x+y+z$ s.t.

$\begin{cases}x\leq q_{u}\\\ y+z\leq q_{u^{\prime}}\\\ z\leq
Q-Q_{k^{\prime}}\end{cases}$ (3)

After solving the linear program, we check the additional constraint $x+y\leq
Q-Q_{k}+q_{u^{\prime}}$. If it is satisfied, we assign $v_{k^{\prime}}$ to
pickup $z^{*}$ from $S_{u^{\prime}}$, and $v_{k}$ to pickup $x^{*}$ from
$S_{u}$ and $y^{*}$ from $S_{u^{\prime}}$ in $Sol$, where
$(x^{*},y^{*},z^{*})$ is a solution to the linear program. In order for $Sol$
to achieve a better profit than $Sol^{\prime}$ through this re-assignment, the
following need to hold. Let $S_{u}<S_{v}$ denote that $S_{u}$ is visited
before $S_{v}$ in $\tau^{\prime}_{k^{\prime}}$.

$\begin{cases}x^{*}+y^{*}+z^{*}-q_{u^{\prime}}>d(i^{\prime},i)+d(i,i^{\prime\prime})-d(i^{\prime},i^{\prime\prime})\\\
d(i^{\prime},i)+d(i,i^{\prime\prime})-d(i^{\prime},i^{\prime\prime})\leq\min\\{t_{k^{\prime},v^{\prime}}-s_{v^{\prime}}:S_{v^{\prime}}<S_{i^{\prime}}\\}+\min\\{e_{w^{\prime}}-t_{k^{\prime},w^{\prime}}:S_{j^{\prime}}<S_{w^{\prime}}\\}\end{cases}$
(4)

where $t_{k,i}$ is the time when $v_{k}$ visits $S_{i}$. That is, insertion of
$S_{i}$ into $\tau_{k^{\prime}}$ in $Sol$ does not introduce time window
violations

See Figure 2 for an illustration of this re-assignment.

Figure 1: Tours of $Sol^{\prime}$ are depicted in solid lines and tours of
$Sol$ are depicted using dashed lines. $v_{k}$ is assigned to pickup 35 from
$S_{u}$ and 20 from $S_{u^{\prime}}$, while $v_{k^{\prime}}$ is assigned to
pickup 35 from $S_{u^{\prime}}$. Since time windows are not violated, $Sol$ is
more profitable than $Sol^{\prime}$.

‘

For each vehicle $v_{k}$ and site $S_{u^{\prime}}\in\tau^{\prime}_{k}$, we
look at all possible tuples
$(S_{u},S_{i},S_{i^{\prime}},S_{j},S_{j^{\prime}})\in S\times(S\cup D)^{4}$
satisfying the abovementioned additional constraints and solve the linear
program to find the optimal quantities to pickup, then select the tuples that
maximize the profit gain after re-assignment, and then perform the re-
assignment.

One arising concern is that the order in which the pairs
$(v_{k},S_{u^{\prime}})$ are selected produces different results. However,
while this may happen, it may not impact the optmiality of the re-assignment
by more than a constant factor, as we shall see below.

###### Lemma 1

Let $O$ be an ordering of the pairs $(v_{k},S_{u^{\prime}})$ and let
$\Delta(k,u^{\prime})$ be the gain obtained through re-assignment when
selecting pair $(v_{k},S_{u^{\prime}})$ (or 0, if re-assignment is
infeasible). Then
$\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\Delta(k,u^{\prime})=\Delta\in[C,4C]$,
where $C$ does not depend on $O$.

###### Proof

From (4), it follows that

$\Delta(k,u^{\prime})=\max\\{0,x^{*}+y^{*}+z^{*}-q_{u^{\prime}}-d(i^{\prime},i)-d(i,i^{\prime\prime})+d(i^{\prime},i^{\prime\prime})\\}$
$\geq\max\\{0,x^{*}+y^{*}+z^{*}-q_{u^{\prime}}\\}$
$+\max\\{-t_{k^{\prime},v^{\prime}}+s_{v^{\prime}}:S_{v^{\prime}}<S_{i^{\prime}}\\}$
$+\max\\{-e_{w^{\prime}}+t_{k^{\prime},w^{\prime}}:S_{w^{\prime}}>S_{j^{\prime}}\\}$

where $S_{i}<S_{j}$ indicates that $S_{i}$ is before $S_{j}$ in
$\tau^{\prime}_{k^{\prime}}$.

Since $x^{*}=q_{u,k},y^{*}=q_{u^{\prime},k},z^{*}=q_{u^{\prime},k^{\prime}}$,
we get

$\Delta=\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\Delta(k,u^{\prime})$
$\geq\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{0,q_{u,k}+q_{u^{\prime},k}+q_{u^{\prime},k^{\prime}}-q_{u^{\prime}}\\}$
$+\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{-t_{k^{\prime},v^{\prime}}+s_{v^{\prime}}:S_{v^{\prime}}<S_{i^{\prime}}\\}$
$+\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{-e_{w^{\prime}}+t_{k^{\prime},w^{\prime}}:S_{w^{\prime}}>S_{j^{\prime}}\\}$

We have

$\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}q_{u^{\prime},k}=\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}q_{u^{\prime}}=\sum_{k,S_{i}\in\tau^{\prime}_{k}}q_{i},$
$\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{-t_{k^{\prime},v^{\prime}}+s_{v^{\prime}}:S_{v^{\prime}}<S_{i^{\prime}}\\}\geq\sum_{k}(s_{i}-t_{k,i}:i\in\tau_{k}),$
$\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{-e_{w^{\prime}}+t_{k^{\prime},w^{\prime}}:S_{w^{\prime}}>S_{j^{\prime}}\\}\geq\sum_{k}(t_{k,i}-e_{i}:i\in\tau_{k}).$

Let

$Q^{*}=\sum_{\tau^{\prime}_{k},S_{i}\in\tau^{\prime}_{k}}q_{i},Q^{s}=\sum_{k}(s_{i}-t_{k,i}:i\in\tau_{k}),Q^{e}=\sum_{k}(t_{k,i}-e_{i}:i\in\tau_{k})$.

Since
$\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{0,q_{u,k}+q_{u^{\prime},k}\\}\geq
Q^{*}$, it follows that

$\Delta\geq Q^{*}+Q^{s}+Q^{e}.$

Moreover, note that
$Q^{s}+Q^{e}=\sum_{k}(s_{i}-t_{k,i}+t_{k,i}-e_{i})=\sum_{k}(s_{i}-e_{i})$.

That is, $\Delta\geq C=Q^{*}-\sum_{k}(e_{i}-s_{i})$, where $C$ does not depend
on $O$.

Note that

$x^{*}+y^{*}+z^{*}-q_{u^{\prime}}\leq
2(d(i^{\prime},i)-d(i,i^{\prime\prime})+d(i^{\prime},i^{\prime\prime})),\forall{u^{\prime},i,i^{\prime},i^{\prime\prime}},$

since otherwise one would be able to create an optimal metric-space MST-based
tour of cost $>2C$, which is a contradiction of the result in [9].

Thus,

$\Delta\leq
2(\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{0,q_{u,k}+q_{u^{\prime},k}+q_{u^{\prime},k^{\prime}}-q_{u^{\prime}}\\}$
$+\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{-t_{k^{\prime},v^{\prime}}+s_{v^{\prime}}:S_{v^{\prime}}<S_{i^{\prime}}\\}$
$+\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{-e_{w^{\prime}}+t_{k^{\prime},w^{\prime}}:S_{w^{\prime}}>S_{j^{\prime}}\\}).$

Since

$\max\\{-t_{k^{\prime},v^{\prime}}+s_{v^{\prime}}:S_{v^{\prime}}<S_{i^{\prime}}\\}+\max\\{-e_{w^{\prime}}+t_{k^{\prime},w^{\prime}}:S_{w^{\prime}}>S_{j^{\prime}}\\}$
$\leq 2\max{s_{v^{\prime}}-e_{w^{\prime}}}\leq 2T,$

for sufficiently large $\frac{\min{q_{i}}}{2T}$, which is reasonable since $T$
is constant, we get

$\Delta\leq
4\sum_{k,S_{u^{\prime}}\in\tau^{\prime}_{k}}\max\\{0,q_{u,k}+q_{u^{\prime},k}+q_{u^{\prime},k^{\prime}}-q_{u^{\prime}}\\}$
$\leq 4(Q^{*}+Q^{s}+Q^{e}).$

That is, $\Delta\leq 4C$.

Thus, we first run a MPRP solver to obtain a routing $\tau^{\prime}$ and then
select the pairs $(v_{k},S_{u^{\prime}})$ in the order given by each
$\tau^{\prime}_{k}$ for every $k$. For each of the $O(mn)$ pairs, we inspect
all possible $O(n^{5})$ tuples in $O(n)$ time per tuple, which is the time
required to verify constraint 2. That is, our reduction is done in $O(mn^{7})$
time.

As for the correctness of the reduction, suppose there exists a routing
$\tau^{\prime\prime}$ for $I^{\prime}$ yielding a profit increased by more
than a factor of 4 compared to $\tau^{\prime}$. In order to do that,
$\tau^{\prime\prime}$ must pickup a quantity
$q^{\prime\prime}_{u^{\prime}}>4q_{u^{\prime}}$ from some $S_{u^{\prime}}$.
However, this implies that either $S_{u^{\prime}}$ is not re-assigned in
$\tau$ and thus gives an increased profit for $I^{\prime}$, or is re-assigned
to one of $S_{u},S_{i},S_{i^{\prime}},S_{j},S_{j^{\prime}}$ and thus gives an
increased profit for one of these sites. Both options lead to a contradiction.
Now suppose there exists a routing $\tau^{\prime\prime}$ for $I$ yielding an
increased profit compared to $\tau$. In order for that to happen, either some
site $S_{u^{\prime}}$ that was never added or involved in a re-assignment
picks up a quantity $q^{\prime\prime}_{u^{\prime},k}>q_{u^{\prime},k}$ ,
implying an increased profit for
$q^{\prime\prime}_{u^{\prime}}>4q^{\prime}_{u^{\prime}}$ for $S_{u^{\prime}}$
in $\tau^{\prime}$, or some site $S_{u^{\prime}}$ involved in a re-assignment
with $(S_{u},S_{i},S_{i^{\prime}},S_{j},S_{j^{\prime}})$ picks up a quantity
$q^{\prime\prime}_{u^{\prime},k}>4q_{u^{\prime},k}$ , implying a quantity was
picked up from some site (wlog assumed to be $S_{u}$) in $\tau^{\prime\prime}$
which is more than 4 times the one picked from the samee site in
$\tau^{\prime}$. In both cases, a contradiction follows due to Lemma 1. Hence,
we have reduced MPRP-M to MPRP within an approximation ratio of 4 in
$O(mn^{7})$ time.

By using the $\simeq 11\log T$-approximation for MPRP in [3] for $O(n^{11})$
time, we thus solve MPRP-M in $O(n^{11})$ time.

We have proved the following result.

###### Theorem 2.1

MPRP-M can be solved in $O(n^{11})$ time for an approximation ratio of $\simeq
44\log T$.

##  3 MPRP-MVS

In MPRP-MVS, quantities $q_{i}$ supplied at sites vary linearly as a function
of time, i.e. $q_{i}(t)=q_{i}(e_{i})\frac{t-s_{i}}{e_{i}-s_{i}}$.

We adapt the algorithm in [2] for solving MPRP-VS, to work in our case, by
using a similar reduction as the one from MPRP-M to MPRP described in the
previous section, to reduce MPRP-MVS to MPRP-VS.

Given an instance $I=(S=\\{S_{i}:1\leq i\leq
n\\},D=(x_{0},y_{0}),d=\\{d(i,j):0\leq i<j\leq n\\},T,Q,m)$ of MPRP-MVS, we
apply the reduction in [2] to obtain an instance $I^{\prime\prime}\in MPRP-M$,
and then solve MPRP-M using the algorithm in Section 2. Again, this is not
straightforward since the approach in [2] depends on single vehicle assignment
which is not the case here. Thus, we need a more insightful construction of
$I^{\prime\prime}$ than directly applying the algorithm in [2].

For each site $S_{i}$, we split $[s_{i},e_{i}]$ into
$N=1+\frac{\ln(1/\alpha)}{\epsilon}$ intervals, for some $\epsilon>0$, where
$\alpha>1$ is the smallest constant such that $q_{i}(e_{i})\leq\alpha
q_{j}(e_{j}),\forall{i,j}$. Denote these intervals by $L_{i,l}:1\leq l\leq N$,
i.e.
$L_{i,l}=[s_{i}+\frac{e_{i}-s_{i}}{(1+\epsilon)^{N-l+1}},s_{i}+\frac{e_{i}-s_{i}}{(1+\epsilon)^{N-l}}]$.
After performing this split, we construct a set of sites $S^{\prime}$ where,
for each original site $S_{i}$, $S^{\prime}$ contains $N$ sites
$S^{\prime\prime}_{i,\tau},1\leq\tau\leq N$. To each newly constructed site
$S^{\prime\prime}_{i,l}$, we assign a quantity
$q^{\prime}_{i,l}=q_{i}(e_{i})\frac{l-0.5}{N-1}$ and a time window $I_{i,l}$.
We then run the MPRP-M Option 1 algorithm described in Section 2 on the
transformed instance $I^{\prime\prime}=(S^{\prime\prime},D,d,T,Q,m)$ (note
that $I^{\prime\prime}\in MPRP-M$ since the sites in $S^{\prime\prime}$ now
supply constant quantities).

Denote by $\tau^{\prime\prime}$ the routing obtained by running the MPRP-M
algorithm on $I^{\prime\prime}$. We now analyze the properties of
$\tau^{\prime\prime}$ in order to put a bound on its performance ratio.

We know from [2] that an optimal MPRP algorithm run on $S^{\prime}$ may
collect a quantity at least $\frac{1}{1+\epsilon}$ as much as an optimal MPRP-
VS algorithm run on $S$. Since for $m=1$, an instance of MPRP-M also belongs
to MPRP, and an instance of MPRP-MVS is also an instance of MPRP-VS, we get
the following.

###### Lemma 2

For $m=1$, an optimal MPRP-M algorithm when run on $S^{\prime\prime}$ may
collect a quantity at least $\frac{1}{1+\epsilon}$ as high as an optimal MPRP-
MVS algorithm when run on $S$.

###### Lemma 3

[2] Let $A$ be an algorithm for a MPRP (resp., MPRP-M) and let $P(I)$ be the
profit obtained by $A$ when run on an instance $I$ with one vehicle. Then, on
an instance $I^{\prime}$ with $m$ vehicles, the profit obtained by $A$ is
$P(I^{\prime})\geq\frac{P(I)}{(1+\frac{1}{1+\sqrt{m}})^{2}}$.

By running the $\frac{1}{44\log T}$-optimal MPRP-M algorithm in Section 2 on
$I^{\prime\prime}$, we get the following a profit at least $\frac{1}{44\log
T(1+\frac{1}{1+\sqrt{m}})}$ as high as an optimal MPRP-MVS algorithm when run
on $I$.

Since travel costs are less than the rewards generated by the quantities
collected, a performance ratio of $\frac{1}{1+\epsilon}$ in the quantities
induces a performance ratio of $\frac{1}{1+\epsilon}$ in the profits as well.
Putting this together with the lemma above, we get the following.

###### Lemma 4

When run on $I^{\prime\prime}$, the MPRP-M algorithm in Section 2 may obtain a
profit at least $\frac{1}{44\log T(1+\epsilon)(1+\frac{1}{1+\sqrt{m}})^{2}}$
as high as an optimal MPRP-MVS algorithm when run on $I$.

Note that the reduction described before Lemma 2 takes $O(\frac{n}{\epsilon})$
time. Then, running MPRP-M on $I^{\prime\prime}$ which has
$|S^{\prime\prime}|=O(\frac{n}{\epsilon})$ sites, takes
$O((\frac{n}{\epsilon})^{11})$ time. Thus, we have proved the following
result.

###### Theorem 3.1

MPRP-MVS can be solved in $O((\frac{n}{\epsilon})^{11})$ time within an
approximation ratio of $44\log T(1+\epsilon)(1+\frac{1}{1+\sqrt{m}})^{2}$.

##  4 Conclusions and Future Work

We solve the Multiple Vehicles per Site versions of the Maximum-Profit Routing
Problem, specifically, the Fixed-Supply version and the Time-Variable Supply
version.

We leave for future consideration probablisitc approaches for all versions of
MPRP, e.g. algorithmic solutions whose output is, with high probability,
within a certain bound of the optimum for the given instance. Proving negative
results or lower bounds, e.g. inaproximability within a certain ratio, would
also be of interest.

## References

  * [1] B. Armaselu, O. Daescu,  Approximation Algorithms for the Maximum Profit Pick-up Problem with Time Windows and Capacity Constraint,  arXiv:1612.01038,  December 2016
  * [2] B. Armaselu,  An APX for the Maximum-Profit Routing Problem with Variable Supply,  arXiv:2007.09282,  July 2020
  * [3] B. Armaselu and O. Daescu,  Interactive Assisting Framework for Maximum Profit Routing in Public Transportation in Smart Cities,  PETRA 2017: 13-16
  * [4] S. Arora,  Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems,  Journal of ACM 45 (5),  1998,  pp. 753-782
  * [5] N. Bansal, A. Blum, S. Chawla, and A. Meyerson,  Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time Windows,  STOC 2004: 166-174
  * [6] RR. van Bevern, S. Hartung, A. Nichterlein, and M. Sorge,  Constant-factor approximations for Capacitated Arc Routing without triangle inequality,  Operations Research Letters 42 (4),  June 2014,  pp. 290-292
  * [7] Bredstr¨om D, R¨onnqvist M.  Combined Vehicle Routing and Scheduling with Temporal Precedence and Synchronization Constraints.  European Journal of Operational Research 191: 19–29 (2008)
  * [8] B¨urckert H, Fischer K, Vierke G.  Holonic Transport Scheduling with TELETRUCK.  Applied Artificial Intelligence 14: 697–725 (2000)
  * [9] N. Christofides,  Worst-case analysis of a new heuristic for the traveling salesman problem,  N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem,  Management Sciences Research (388) report, 1976
  * [10] Drexl M.  Synchronization in Vehicle Routing - A Survey of VRPs with Multiple Synchronization Constraints.  Transp. Sci. 46(3): 297-316 (2012)
  * [11] Fisher ML.  Optimal solution of Vehicle Routing Problems using Minimum K-Trees.  Oprations Research 42 (4): 626-642 (1994)
  * [12] Fisher ML, Jornstein KO, Madsen OB.  Vehicle Routing with Time Windows: Two Optimization algorithms.  Operations Research 45 (3), 1997.  DOI: 10.1287/opre.45.3.488
  * [13] B.L. Golden and R.T. Wong,  Capacitated arc routing problems,  Networks 11 (3),  1981,  pp. 305-315
  * [14] Karpinski M, Lampis M, Schmied R.  New Inapproximability bounds for TSP.  Journal of Computer and System Sciences 81 (8): 1665–1677 (2005),  arXiv:1303.6437, doi:10.1016/j.jcss.2015.06.003
  * [15] Papadimitriou CH, Yannakakis M.  The traveling salesman problem with distances one and two,  Math. Oper. Res. 18: 1–12 (1993).  doi: 10.1287/moor.18.1.1
  * [16] S. Sahni and T. Gonzalez,  P-complete approximation problems,  J. ACM, 23 (3),  1976,  pp. 555-565
  * [17] X. Wang, C. Xu, and H. Shang,  Multi-depot Vehicle Routing Problem with Time Windows and Multi-type Vehicle Number Limits and Its Genetic Algorithm,  WiCOM 2008,  DOI: 10.1109/WiCom.2008.1502