Yogesh J Bagul
email: yjbagul@gmail.com

Christophe Chesneau
email: christophe.chesneau@unicaen.fr

Some New Simple Inequalities Involving Exponential, Trigonometric and Hyperbolic Functions

Keywords: Exponential function, trigonometric function, hyperbolic function Mathematics Subject Classification(2010): 26D07, 33B10, 33B20

The prime goal of this paper is to establish sharp lower and upper bounds for useful functions such as the exponential functions, with a focus on exp(-x 2 ), the trigonometric functions (cosine and sine) and the hyperbolic functions (cosine and sine). The bounds obtained for hyperbolic cosine are very sharp. New proofs, refinements as well as new results are offered. Some graphical and numerical results illustrate the findings.

Introduction

Sharp bounds for useful functions play a central role in many areas of mathematics and theoretical physics. They aim to provide some properties of functions of interest, possibly complex, by dealing with more tractable functions (in the context). The literature on the bounds dealing with the special functions such as e -x 2 , cos(x), sin(x), sinc(x), cosh(x), sinh(x) and tanh(x), is very vast. Recent developments can be found in [START_REF] Chesneau | Some tight polynomial-exponential lower bounds for an exponential function[END_REF][START_REF] Chesneau | On two simple and sharp lower bounds for exp(x 2 )[END_REF][START_REF] Bagul | Some sharp circular and hyperbolic bounds of exp(x 2 ) with Applications[END_REF][START_REF] Bagul | Inequalities involving circular, hyperbolic and exponential functions[END_REF][START_REF] Alzer | On Jordan's inequality[END_REF][START_REF] Yang | Jordan type inequalities for hyperbolic functions and their applications[END_REF][START_REF] Qi | Refinements, generalizations and applications of Jordan's inequality and related problems[END_REF][START_REF] Bagul | New inequalities involving circular, inverse circular, hyperbolic, inverse hyperbolic and exponential functions[END_REF][START_REF] Malesevic | One method for proving some classes of exponential analytic inequalities[END_REF][START_REF] Bagul | On Simple Jordan type inequalities[END_REF][START_REF] Zhu | A source of inequalities for circular functions[END_REF][START_REF] Neuman | On some inequalities involving trigonometric and hyperbolic functions with emphasis on the Cusa-Huygens, Wilker and Huygens inequalities[END_REF][START_REF] Bagul | On exponential bounds of hyperbolic cosine[END_REF][START_REF] Bhayo | New trigonometric and hyperbolic inequalities[END_REF] - [START_REF] Lv | A note on Jordan type inequalities for hyperbolic functions[END_REF][START_REF] Huygens | Oeuvres completes[END_REF][START_REF] Sándor | Sharp Cusa-Huygens and related inequalities[END_REF][START_REF] Sándor | On Cusa-Huygens type trigonometric and hyperbolic inequalities[END_REF] and the references therein. In this paper, we offer new simple tight (lower and upper) bounds involving these functions, with a high potential of interest for many researchers in mathematics or theoretical physics. Some proofs of our results are based on the so-called l'Hospital's rule of monotonicity, the others used recent results with a new approach. The sharpness of our bounds are highlighted by some graphics and numerical studies using a global L 2 error as benchmark.

The result below shows bounds for e -x 2 defined with the cosine function and well-chosen constants. Proposition 1. For x ∈ (0, π/2), the best possible constants α and β in the following inequalities cos(x) -1 + α α e -x 2 cos(x) -1 + β β (1.1) are 1/2 and ≈ 1.092663 respectively.

The interest of Proposition 1 is the simplicity of the bounds, with very tractable expressions. It can be useful to evaluate complex functions depending on e -x 2 (Gaussian probability density function, error function etc.). The bounds of Proposition 1 are illustrated in Figure 1. We see that the lower bound is sharp for small values for x. Note: Using exponential and cosine series, Proposition 1 can be expressed in terms of alternating series as follows. For x ∈ (-π/2, π/2), we have

1 α ∞ k=1 (-1) k x 2k (2k)! ∞ k=1 (-1) k x 2k k! 1 β ∞ k=1 (-1) k x 2k (2k)! ,
where α and β are as defined above. Now let us recall that the sinc function is defined by

sinc(x) = sin(x) x x = 0, 1 x = 0. (1.2)
It is of importance due to it's frequent occurrence in Fourier analysis. So the interest of finding the bounds of this type of functions is increasing. In the next proposition, we give new bounds to sinc function using hyperbolic tangent.

Proposition 2. For x ∈ (0, π/2), we have

tanh(x) x δ < sin(x) x < tanh(x) x η (1.3)
with the best possible constants δ = 0.839273 and η = 1/2.

In the following propositions, the inequalities presented are somewhat Cusa-Huygen's type [START_REF] Huygens | Oeuvres completes[END_REF][START_REF] Sándor | Sharp Cusa-Huygens and related inequalities[END_REF]. Proposition 3 below provides bounds for the sinc function using e -x 2 or hyperbolic cosine. In view of Propositions 2 and 3, it is natural to address the following question: Which bounds for sinc are the best ? We provide the answer by doing a numerical study. We investigate the global L 2 error defined by

e(u) = π/2 0 sinx x -u(x) 2 dx,
where u(x) denotes bound (lower or upper) in (1.3), (1.4) and (1.5). The results are summarized in Table 1. The next result provides bounds for x/sinh(x) using cosine function.

Proposition 4. If x ∈ (0, π/2) then we have

2 + cos(x) 3 m < x sinh(x) < 2 + cos(x) 3 n (1.6)
with the constants m ≈ 1.014227 and n ≈ 0.928648.

The obtained bounds are illustrated in Figure 3. x sinh(x) Note: The inequality

( ( 2 + cos(x) ) 3) m ( ( 2 + cos(x) ) 3) n
2 + cos(x) 3 < x sinh(x)
is more sharp version of left inequality of (1.6). It is appeared in [START_REF] Sándor | On Cusa-Huygens type trigonometric and hyperbolic inequalities[END_REF]Theorem 6].

Proposition 5 below presents sharp bounds for sinh(x)/x using hyperbolic cosine.

Proposition 5. For x ∈ (0, π/2) one has

2 + cosh(x) 3 p < sinh(x) x < 2 + cosh(x) 3 q (1.7)
with the constants p ≈ 0.928648 and q ≈ 1.009155.

The bounds are illustrated in Figure 4. Note: The hyperbolic Cusa-Huygen's inequality [START_REF] Neuman | On some inequalities involving trigonometric and hyperbolic functions with emphasis on the Cusa-Huygens, Wilker and Huygens inequalities[END_REF] sinh(x) x < 2 + cosh(x) 3 is however more sharp than right inequality of (1.7).

0.0 0.5 1.0 1.5 1.0 1.1 1.2 1.3 1.4 sinh(x) x ( ( 2 + cosh(x) ) 3) p ( ( 2 + cosh(x) ) 3) q
The rest of the study is devoted to new bounds for cosh(x), with discussion. A well-known upper bound for cosh(x) is given by e x 2 /2 . This result was recently completed by Yogesh Bagul [13, Theorem 2.1] who finds a sharp lower bound, i.e. e ax 2 < cosh(x) < e x 2 /2 , x ∈ (0, 1), (1.8) with the best possible constants a ≈ 0.433781 and 1/2. We now aim to refine the inequalities of (1.8) in Proposition 6 below. Proposition 6. For x ∈ (0, 1), we have

exp 3 2 1 -e -x 2 /3 cosh(x) exp 1 2θ 1 -e -θx 2 (1.9)
with θ ≈ 0.272342.

Note: Using the well-known inequality e y 1 + y for y ∈ R, we obtain exp 1 -e -θx 2 /(2θ) e x 2 /2 . This proves that the upper bound in (1.9) is sharper to the one in (1.8).

Alternative bounds are given in Proposition 7 below, with discussion. Proposition 7. For x ∈ (0, 1), we have

1 + x 2 3 3/2 cosh(x) 1 + x 2 ξ ξ/2
(1.10)

with ξ ≈ 3.194528.

Note: Again, using the well-known inequality e y 1 + y for y ∈ R, we get (1 + x 2 /ξ) ξ/2 e x 2 /2 . This shows that the upper bound in (1.10) is sharper to the one in (1.8).

We now claim that the bounds obtained in (1.10) are better than those in (1.8) and (1.9). Numerical results support this claim. Indeed, by considering the global L 2 error defined by

e * (u) = 1 0 (cosh(x) -u(x)) 2 dx,
where u(x) denotes bound (lower or upper) in (1.8), (1.9) and (1.10), Table 2 indicates that (1.10) are the best.

Table 2: Global L 2 errors e * (u) for cosh(x) and the functions u(x) in the bounds of (1.8), (1.9) and (1.10) for x ∈ (0, 1). The sharpness of the obtained bounds is illustrated in Figures 5 and6 (for a zoom on the interval (0.95, 1) where the hierarchy of the bounds is more clear). Note: To prove the inequalities (1.5), (1.6) and (1.7), we will simply use the results of [START_REF] Bagul | Some sharp circular and hyperbolic bounds of exp(x 2 ) with Applications[END_REF][START_REF] Bagul | Inequalities involving circular, hyperbolic and exponential functions[END_REF]. We stress on the fact that it is not difficult to verify that all the results in [START_REF] Bagul | Inequalities involving circular, hyperbolic and exponential functions[END_REF] are also true in (0, π/2) with the respective best possible constants obtained accordingly (see [START_REF] Chesneau | A note on some new bounds for trigonometric functions using infinite products[END_REF]). Propositions 6 and 7 will be proved by the techniques of integration on some known results [START_REF] Bagul | New inequalities involving circular, inverse circular, hyperbolic, inverse hyperbolic and exponential functions[END_REF][START_REF] Bagul | On Simple Jordan type inequalities[END_REF]. For proving Proposition 1, Proposition 2 and Proposition 3, we need the Lemmas presented in the next section.

(1 + x 2 3) (3 2) (1 + x 2 ξ) (ξ 2)
(1 + x 2 3) (3 2) (1 + x 2 ξ) (ξ 2)

Lemmas

The following Lemma is known as l'Hospital's rule of monotonicity [START_REF] Anderson | Conformal Invarients, Inequalities and Quasiconformal maps[END_REF]. The strictness of the monotonicity of A(x) and B(x) depends on the strictness of monotonicity of f /g . Lemma 2. H(x) = sin(x)-x cos(x)

A(x) = f (x) -f (a) g(x) -g(a) and B(x) = f (x) -f (b) g(x) -g(b) .
x 2 sin(x)
is strictly positive increasing in (0, π/2).

Proof: H(x) is positive as cos(x) < sin(x)

x on (0, π/2). Consider,

H(x) = sin(x) -x cos(x) x 2 sin(x) = H 1 (x) H 2 (x)
where H 1 (x) = sin(x)-x cos(x) and H 2 (x) = x 2 sin(x) are such that H 1 (0) = 0 and H 2 (0) = 0. By differentiating

H 1 (x) H 2 (x) = sin(x) x cos(x) + 2sin(x) = H 3 (x) H 4 (x)
where H 3 (x) = sin(x) and H 4 (x) = x cos(x) + 2 sin(x) with H 3 (0) = 0 and H 4 (0) = 0. Again differentiating we get

H 3 (x) H 4 (x) = cos(x) -x sin(x) + 3cos(x) = 1 -x tan(x) + 3 .
Now it is well known that -x tan(x) is decreasing in (0, π/2) and so is -x tan(x) + 3. By Lemma 1, H(x) is strictly increasing function in (0, π/2).

Proofs of the Main Results

This section is devoted to the proofs of our main results.

Proof of Proposition 1: Clearly equalities hold at x = 0. Consider

f (x) = cos(x) -1 e -x 2 -1 = f 1 (x) f 2 (x) ,
where

f 1 (x) = cos(x) -1 and f 2 (x) = e -x 2 -1 with f 1 (0) = 0 and f 2 (0) = 0.
By differentiation, we obtain

f 1 (x) f 2 (x) = sin(x) e x 2 2 x = f 3 (x) f 4 (x) ,
where f 3 (x) = sin(x) e x 2 and f 4 (x) = 2 x with f 3 (0) = 0 and f 4 (0) = 0. Again differentiating we get

f 3 (x) f 4 (x) = e x 2 2 [cos(x) + 2 x sin(x)] = e x 2 2 F (x),
where F (x) = cos(x) + 2 x sin(x). Differentiation gives F (x) = 2 x cos(x) + sin(x) > 0 in (0, π/2), which implies that F (x) is increasing. Thus

f 3 (x) f 4 (x)
being a product of two positive increasing functions is a positive increasing. By Lemma 1, f (x) is also increasing in (0, π/2).

So α = f (0+) = 1/2 and β = f (π/2-) = -1/[e -(π/2) 2 -1] ≈ 1.092663. Proof of Proposition 2: Let us set h(x) = log(sin(x)/x) log(tanh(x)/x) = h 1 (x) h 2 (x) ,
where h 1 (x) = log(sin(x)/x) and h 2 (x) = log(tanh(x)/x) with h 1 (0+) = 0 and h 2 (0+) = 0. Differentiating we get

h 1 (x) h 2 (x) = sin(x) -x cos(x) x 2 sin(x) x 2 tanh(x) tanh(x) -x sech 2 (x) = H(x) J(x),
where H(x) = sin(x)-x cos(x)

x 2 sin(x)

and J(x) =

x 2 tanh(x) tanh(x)-x sech 2 (x) . Now set

J(x) = J 1 (x) J 2 (x)
where J 1 (x) = x 2 tanh(x) and J 2 (x) = tanh(x) -x sech 2 (x) withJ 1 (0) = 0 and J 2 (0) = 0. Differentiation gives

J 1 (x) J 2 (x) = x sech 2 (x) + 2 tanh(x) 2 sech 2 (x) tanh(x) = 1 2 x tanh(x) + cosh 2 (x),
which is clearly increasing as both x/tanh(x) and cosh 2 (x) are increasing. By Lemma 1, J(x) is also increasing in (0, π/2). Moreover, J(x) is positive as x/sinh(x) < cosh(x). By Lemma 2, H(x) is strictly positive increasing in (0, π/2). h 1 (x)/h 2 (x), being product of two positive increasing functions is positive increasing. Again by Lemma 1, h(x) is strictly increasing in (0, π/2). So δ = log(2/π)/log(2tanh(π/2)/π) ≈ 0.839273 and η = f (0+) = 1/2, by l'Hospital's rule. This completes the assertion.

Proof of Proposition 3:

• Proof of (1.4). Let

f (x) = log (sin(x)/x) log (2 + e -x 2 ) -log3 = f 1 (x) f 2 (x) ,
where f 1 (x) = log (sin(x)/x) and f 2 (x) = log 2 + e -x 2 -log3 such that f 1 (0+) = 0 and f 2 (0) = 0. Differentiation gives

f 1 (x) f 2 (x) = 1 2 (sin(x) -x cos(x)) x 2 sin(x) (2e x 2 + 1) = 1 2 H(x) G(x),
where H(x) = sin(x)-x cos(x)

x 2 sin(x)
is strictly positive increasing in (0, π/2)

by Lemma 2 and G(x) = 2e x 2 + 1 is also clearly positive increasing. Therefore H(x) G(x) is strictly increasing. By making use of Lemma 1, we conclude that f (x) is strictly increasing in (0, π/2). So where k = -log(2/π) (π/2) 2 . After rearrangement, it can be written as

f (0+) < f (x) < f (π/2); x ∈ (0, π/2). Hence, a = f (π/2) = log(2/π)/[log(2 + e -(π/2) 2 ) -log3] ≈ 1.
sin(x) x 6 < e -x 2 < sin(x) x 1/k . ( 3.1)
By virtue of [3, Theorem 2] we write

3 2 + cosh(x) γ < e -x 2 < 3 2 + cosh(x) 6 , (3.2)
where γ = Proof of Proposition 4: According to [4, Theorem 3] and [START_REF] Chesneau | A note on some new bounds for trigonometric functions using infinite products[END_REF] we have e -x 2 /6 < x sinh(x) < e -tx 2 , x ∈ (0, π/2)

where t = -log[π/(2sinh(π/2))] (π/2) 2
. It is equivalent to

x sinh(x) 1/t < e -x 2 < x sinh(x) 6 . (3.3)
Similarly, using [3, Theorem 1] we have Proof of Proposition 6: For x = 0 equalities hold obviously. Rearranging [8, Theorem 5], for any t ∈ (0, 1), we have t e -t 2 /3 < tanh(t) < t e -θt 2 with θ ≈ 0.272342. Therefore by integration, for x ∈ (0, 1), we get 1 -e -x 2 /3 < log(cosh(x)) < 1 2θ

2 + cos(x) 3 λ < e -x 2 < 2 + cos(x) 3 6 , (3.4
1 -e -θx 2 .

By composing with the exponential function, we get the required result.

Proof of Proposition 7: Clearly, equalities hold at x = 0. Rearranging [10, Theorem 4], for any t ∈ (0, 1), we have 3t 3 + t 2 < tanh(t) < ξt ξ + t 2 with ξ ≈ 3.194528. On integration, for x ∈ (0, 1), we have The desired result follows by composing with the exponential function.

Figure 1 :

 1 Figure 1: Graphs of the functions of the bounds (1.1) for x ∈ (0, π/2).

Proposition 3 .

 3 For x ∈ (0, π/2), the inequalities 2 + e -x 2 3 are true with the best possible constants a ≈ 1.240827, b = 1/2, c ≈ 1.108171 and d = 1.

( 3 ( 2 +

 32 cosh(x) ) ) c (3 (2 + cosh(x) ) ) d

Figure 2 :

 2 Figure 2: Graphs of the functions of the bounds (1.5) for x ∈ (0, π/2).

Figure 3 :

 3 Figure 3: Graphs of the functions of the bounds (1.6) for x ∈ (0, π/2).

Figure 4 :

 4 Figure 4: Graphs of the functions of the bounds (1.7) for x ∈ (0, π/2).

Figure 5 :

 5 Figure 5: Graphs of the functions of the bounds (1.10) for x ∈ (0, 1).

Figure 6 :

 6 Figure 6: Graphs of the functions of the bounds (1.10) for x ∈ (0.95, 1).

Lemma 1 .

 1 ( [15]) Let f, g be two real valued functions which are continuous on [a, b] and differentiable on (a, b), where -∞ < a < b < ∞ and g (x) = 0, for ∀x ∈ (a, b). Let,

  Then I) A(x) and B(x) are increasing on (a, b) if f /g is increasing on (a, b) and II) A(x) and B(x) are decreasing on (a, b) if f /g is decreasing on (a, b).

•

  240827 and b = f (0+) = 1/2 by l'Hospital's rule. Proof of (1.5). Utilizing [4, Theorem 2], [20, Proposition 3] we have e -kx 2 < sin(x) x < e -x 2 /6 ,

(π/2) 2

 2 log[(2+cosh(π/2))/3] . Combining (3.1) and (3.2)2+cosh(π/2))/3] ≈ 1.108171.

= λ 6 = 5 :

 65 -(π/2) 2 6log(2/3) ≈ 1.014227 and n = 6t = -6log[π/(2sinh(π/2))] The proof follows easily by combining inequalities (3.2) and (3.3) to getp = -6log[π/2sinh(π/2)] (π/2) 2 ≈ 0.928648 and q = (π/2) 26log[(2+cosh(π/2))/3] ≈ 1.009155.

Table 1 :

 1 Global L 2 errors e(u) for sinc(x) and the functions u(x)

	in the

e(u) ≈ 6.53313 × 10 -5 ≈ 0.0001542441

It follows from Table

1

that the bounds (1.5) are more sharp. This sharpness is illustrated in Figure

2

.


Christophe Chesneau
email: christophe.chesneau@unicaen.fr

Yogesh J Bagul
email: yjbagul@gmail.com

New refinements of two well-known inequalities

Keywords: Trigonometric function, infinite product, exponential bounds Mathematics Subject Classification(2010): 26D07, 33B10, 33B20

In this note, we improve the useful inequalities sin(x)sinh(x) x 2 and cos(x)cosh(x) 1 by the use of infinite products.

Introduction

During the past several years, sharp inequalities involving trigonometric and hyperbolic functions have received a lot of attention. Thanks to their usefulness in all areas of mathematics. Old and new such inequalities, as well as refinements of the so-called Jordan's, Cusa-Huygens and Wilker inequalities, can be found in [START_REF] Guo | Sharpening and generalizations of Carlson's inequality for the arc cosine function[END_REF][START_REF] Neuman | On some inequalities involving trigonometric and hyperbolic functions with emphasis on the Cusa-Huygens, Wilker, and Huygens inequalities[END_REF][START_REF] Neuman | Optimal inequalities for hyperbolic and trigonometirc functions[END_REF][START_REF] Qi | Some inequalities constructed by Tchebysheff's integral inequality[END_REF][START_REF] Qi | Sharpening and generalizations of Shafer's inequality for the arc sine function[END_REF][START_REF] Qi | Refinements, generalizations, and applications of Jordan's inequality and related problems[END_REF][START_REF] Sándor | Two sharp inequalities for trigonometric and hyperbolic functions[END_REF][START_REF] Sándor | Trigonometric and hyperbolic inequalities[END_REF][START_REF] Zhu | On Wilker-type inequalities[END_REF][START_REF] Sándor | On Cusa-Huygens type trigonometric and hyperbolic inequalities[END_REF], and the references therein.

In this note, we focus our attention on the following famous results proved by [9, Lemma 1 page 67] and [11,

Lemma 1 page 148]. Lemma 1. [9, Lemma 1], [11, Lemma 1] For x ∈ (0, π/2), we have sin(x)sinh(x) x 2 , cos(x)cosh(x) 1.
The proof of Lemma 1 is based on the studies of appropriate functions. The first inequality is also known in the form sin(x)/x x/sinh(x) or sin(x)

x 2 /sinh(x). In this note, we develop refinements of the two inequalities in Lemma 1 by using infinite products and applying the methodology developed in [START_REF] Chesneau | A note on some new bounds for trigonometric functions using infinite products[END_REF]. Sharp lower bounds of various nature are also established, with graphical supports.

2 Main results

In the following result, we propose a double inequality for sin(x)sinh(x), implying sin(x)sinh(x) x 2 for the upper bound. Proposition 1. For x ∈ (0, α) and α ∈ (0, π), we have

x 2 exp(-βx 4 ) sin(x)sinh(x) x 2 exp - x 4 90 , with β = -ln(sin(α)sinh(α)/α 2 )/α 4 .
Proof of Proposition 1. We have the following infinite products:

sin(x) x = +∞ k=1 1 - x 2 π 2 k 2 , sinh(x) x = +∞ k=1 1 + x 2 π 2 k 2 .
Therefore, using the inequality 1 + y e y for y ∈ R and ζ(4)

= +∞ k=1 (1/k 4 ) = π 4 /90, we have sin(x)sinh(x) = x 2 +∞ k=1 1 - x 2 π 2 k 2 +∞ k=1 1 + x 2 π 2 k 2 = x 2 +∞ k=1 1 - x 4 π 4 k 4 x 2 +∞ k=1 exp - x 4 π 4 k 4 = x 2 exp - x 4 π 4 ζ(4) = x 2 exp - x 4 90 .
For the lower bound, using the Bernoulli inequality, i.e. for u, v ∈ (0, 1), we have 1 -uv (1 -v) u , we obtain, for x ∈ (0, α),

sin(x)sinh(x) = x 2 +∞ k=1 1 - x 4 α 4 α 4 π 4 k 4 x 2 +∞ k=1 1 - α 4 π 4 k 4 x 4 /α 4 = x 2 +∞ k=1 1 - α 4 π 4 k 4 x 4 /α 4 = x 2 sin(α)sinh(α) α 2 x 4 /α 4 = x 2 exp(-βx 4 ).
This ends the proof of Proposition 1.

The proposition below proposes a tight polynomial lower bound for sin(x)sinh(x). Proposition 2. For x ∈ (0, π), we have

x 2 1 - x 4 π 4 π 4 /90 sin(x)sinh(x).
Proof of Proposition 2. Using the Bernoulli inequality, i.e. for u, v ∈ (0, 1), we have 1 -uv (1 -v) u , and ζ(4) = π 4 /90, we have

sin(x)sinh(x) = x 2 +∞ k=1 1 - x 4 π 4 k 4 x 2 +∞ k=1 1 - x 4 π 4 1/k 4 = x 2 1 - x 4 π 4 ζ(4) = x 2 1 - x 4 π 4 π 4 /90
.

This ends the proof of Proposition 2.

Figure 1 illustrates the sharpness of the bounds in Propositions 1 and 2 for x ∈ (0, 3). We see that these inequalities are sharp, particularly for x ∈ (0, 1.5). At least for x ∈ (1.5, 1), the lower bound in Proposition 2 is clearly more sharp to the one in Proposition 1. x 2 exp(-x 4 90)

x 2 exp(-βx 4 )

x 2 (1x 4 π 4 ) (π 4 90)

Figure 1: Graphs of the functions in Propositions 1 and 2 for x ∈ (0, 3).

Similarly, the following result determines a double inequality for cos(x)cosh(x), implying cos(x)cosh(x) 1 for the upper bound. Proposition 3. For x ∈ (0, α) and α ∈ (0, π/2), we have exp(-γx 4 ) cos(x)cosh(x) exp -

x 4 6 , with γ = -ln(cos(α)cosh(α))/α 4 .

Proof of Proposition 3. We have the following infinite products:

cos(x) = +∞ k=1 1 - 4x 2 π 2 (2k -1) 2 , cosh(x) = +∞ k=1 1 + 4x 2 π 2 (2k -1) 2 .
Therefore, using the inequality 1 + y e y for y ∈ R and

+∞ k=1 (1/(2k -1) 4 ) = (15/16)ζ(4) = (15/16)(π 4 /90) = (1/16)(π 4 /6), we have cos(x)cosh(x) = +∞ k=1 1 - 4x 2 π 2 (2k -1) 2 +∞ k=1 1 + 4x 2 π 2 (2k -1) 2 = +∞ k=1 1 - 16x 4 π 4 (2k -1) 4 +∞ k=1 exp - 16x 4 π 4 (2k -1) 4 = exp -x 4 16 π 4 +∞ k=1 1 (2k -1) 4 = exp - x 4 6
.

Using the Bernoulli inequality, i.e. for u, v ∈ (0, 1), we have 1-uv (1-v) u , we obtain, for x ∈ (0, α),

cos(x)cosh(x) = +∞ k=1 1 - x 4 α 4 16α 4 π 4 (2k -1) 4 +∞ k=1 1 - 16α 4 π 4 (2k -1) 4 x 4 /α 4 = +∞ k=1 1 - 16α 4 π 4 (2k -1) 4 x 4 /α 4 = [cos(α)cosh(α)] x 4 /α 4 = exp(-γx 4 ).
The proof of Proposition 3 is completed.

The proposition below presents a sharp polynomial lower bound for cos(x)cosh(x). (1/(2k -1) 4 ) = π 4 /96, we have

cos(x)cosh(x) = +∞ k=1 1 - 16x 4 π 4 (2k -1) 4 +∞ k=1 1 - 16x 4 π 4 1/(2k-1) 4 = 1 - 16x 4 π 4 +∞ k=1 (1/(2k-1) 4 ) = 1 - 16x 4 π 4 π 4 /96
.

This ends the proof of Proposition 4.

Figure 2 illustrates the sharpness of the bounds in Propositions 3 and 4 for x ∈ (0, 1.5). At least for x ∈ (0.5, 1.5), we see that the lower bound in Proposition 4 is clearly more sharp to the one in Proposition 3.

Proposition 4 .- 16x 4 π 4 π 4

 444 For x ∈ (0, π/2), we have1 /96 cos(x)cosh(x).Proof of Proposition 4. Using the Bernoulli inequality, i.e. for u, v ∈ (0, 1), we have 1 -uv (1 -v) u , and +∞ k=1

γx 4 ) ( 1 -

 41 16x 4 π 4 ) (π 4 96)

Figure 2 :

 2 Figure 2: Graphs of the functions in Propositions 3 and 4 for x ∈ (0, 1.5).


Thomas Bosman
email: thomas.bosman@vu.nl

Martijn Van Ee
email: m.van.ee@vu.nl

Yang Jiao
email: yangjiao@andrew.cmu.edu

Alberto Marchetti-Spaccamela
email: alberto@dis.uniroma1.it

R Ravi
email: ravi@andrew.cmu.edu

Leen Stougie
email: l.stougie@vu.nl

Approximation Algorithms for Replenishment Problems with Fixed Turnover Times

We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places; at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

Introduction

Imagine the following particular inventory-routing problem. A set of automatic vendor machines are spread over a country or a city. They have a certain turnover time: the number of days in which a full machine will be sold out. Replenishment is done by vehicles. Let us assume that turnover times are machine dependent but not time dependent, and that it is highly undesirable to have an empty machine. However, the holding costs of the machine are negligible, so that we will always fill the machine to capacity. There is nothing against replenishing a machine before it has become empty, but then the next replenishment will due earlier as well. That is, the deadline of the next replenishment is always within the turnover time after the last replenishment. Equivalently, in any consecutive number of days equal to the turnover time, at least one replenishment has to take place. Replenishing a machine earlier to combine it with the replenishment of another machine that is due earlier may lead to cost savings. The feature that makes this problem so special w.r.t. existing literature, is that it can be compactly modeled by only specifying for every machine its location and the turnover time. The feature is very natural but has hardly been studied in the existing literature. There are intriguing basic open complexity questions, and some highly non-trivial results.

The motivation for studying this problem comes linea recta from a business project for the replenishment of ATMs in the Netherlands, in which some of the co-authors are involved. The replenishment of the ATMs of all the large banks in the Netherlands has been outsourced to a single company: Geld Service Nederland. Of course the real-life ATM replenishment problem is not as stylized as described above; the turnover time is not strictly the same over time but subject to variability, there are restrictions on the routes for the vehicles, etc. But the feature that is least understood in the ATM-problem is exactly the problem of how to deal with the trade-off between replenishing an ATM earlier than its due date leading to a higher frequency of replenishments and the savings on vehicle routing costs.

Formally, an instance of the problem that we study in this paper, which we baptize the replenishment problem with fixed turnover times (rftt), consists of a pair (G, τ ), where G = (V ∪ {s}, E, c) is a weighted graph with a designated depot vertex s and weights on the edges c : E → R + , and turnover times τ ∈ N |V | , indicating that v j ∈ V should be visited at least once in every interval of τ j days.

A solution consists, for each day k, of a tour T k in G starting in and returning to the depot s and visiting a subset of the vertices J k ⊆ V . It is feasible if v j ∈ t+τj k=t+1 J k , ∀t and ∀v j ∈ V . We will focus on solutions that repeat themselves after a finite amount of time, that is, in which (T k , ..., T k+ ) = (T k+ +1 , ..., T k+2 ) for some , and all k. Since all turnover times are finite, this is no real restriction.

We consider two versions of rftt. In the first version, called min-avg, the goal is to find a feasible solution that minimizes the average tour length. In the min-max problem, we want to find a feasible solution that minimizes the maximum tour length over all days.

We emphasize that the particular feature of this model, that jobs or visits to clients recur and need to be done within each job-specific consecutive time interval occurs naturally in many problem settings. It allows any job of a recurring task to be done before its deadline, but then the next job of the task comes earlier and hence its deadline. This is a feature that, despite its natural applicability, has hardly been studied in the literature from a theoretical point of view.

Related work. As mentioned before, our problem can be seen as a special case of the Inventory Routing Problem (IRP) [START_REF] Coelho | Thirty years of inventory routing[END_REF]. Here, clients (vertices) have their own storage with a certain capacity and for each day a demand is specified. The clients pay holding cost over their inventory. However, omitting inventory cost, we can interpret our problem as such an inventory routing problem in which the demand at any given location is the same every day, leading to a very small input description of our problem consisting only of a location and a turnover time (storage capacity divided by daily demand), which makes it incomparable to the inventory routing problem from a complexity point of view. Indeed it is unclear if the decision version of our problem is in NP or in co-NP.

Another closely related problem is the Periodic Latency Problem [START_REF] Coene | Charlemagne's challenge: The periodic latency problem[END_REF], which features the recurring visits requirement of rftt. We are given recurrence length q i for each client i and travel distances between clients. Client i is considered served if it is visited every q i time units. The server does not return to the depot at the end of each time unit (e.g. day), but keeps moving continuously between clients at uniform speed. Another difference between Periodic Latency Problem and rftt is the objective function. Coene et. al. [START_REF] Coene | Charlemagne's challenge: The periodic latency problem[END_REF] study two versions of the problem: one that maximizes the number of served clients by one server, and one that minimizes the number of servers needed to serve all clients. They resolve the complexity of these problems on lines, circles, stars, trees, and general metrics.

A problem that does share the compact input size and is in fact a very special case of our problem is known under the guise of Pinwheel Scheduling. It has been introduced to model the scheduling of a ground station to receive information from a set of satellites without data loss. In terms of our problem no more than one vertex can be replenished per day and all distances to the depot are the same; the interesting question here is if there exists a feasible schedule for replenishing the vertices. Formally, a set of jobs {1, ..., n} with periods p 1 , ..., p n is given, and the question is whether there exists a schedule σ : N → {1, .., n} such that j ∈ t+pj k=t+1 σ k , ∀t ≥ 0 and ∀j. Pinwheel Scheduling was introduced by Holte et al. [START_REF] Holte | The pinwheel: A real-time scheduling problem[END_REF], who showed that it is contained in PSPACE. The problem is in NP if the schedule σ is restricted to one in which for each job the time between two consecutive executions remains constant throughout the schedule. In particular this holds for instances with density ρ = j 1/p j = 1 [START_REF] Holte | The pinwheel: A real-time scheduling problem[END_REF]. They also observed that the problem is easily solvable when ρ ≤ 1 and the periods are harmonic, i.e. p i is a divisor of p j or vice versa for all i and j. As a corollary, every instance with ρ ≤ 1 2 is feasible. Chan and Chin [START_REF] Chan | Schedulers for larger classes of pinwheel instances[END_REF] improved the latter result by giving an algorithm that produces a feasible schedule for Pinwheel Scheduling whenever ρ ≤ 2 3 . In [START_REF] Chan | General schedulers for the pinwheel problem based on double-integer reduction[END_REF], they improved this factor to 7 10 . Later, Fishburn and Lagarias [START_REF] Peter | Pinwheel scheduling: Achievable densities[END_REF] showed that every instance with ρ ≤ 3 4 has a feasible schedule. All these papers work towards the conjecture that there is a feasible schedule if ρ ≤ 5 6 . That this bound is tight can be seen by the instance with p 1 = 2, p 2 = 3 and p 3 = M , with M large. This instance cannot be scheduled, but has a density of 5 6 + 1 M . The complexity of Pinwheel Scheduling has been open since it was introduced. It was only recently shown by Jacobs and Longo [START_REF] Jacobs | A new perspective on the windows scheduling problem[END_REF] that there is no pseudopolynomial time algorithm solving the problem unless SAT has an exact algorithm running in expected time n O(log n log log n) , implying for example that the randomized exponential time hypothesis fails to hold [START_REF] Calabro | The complexity of unique k-sat: An isolation lemma for k-cnfs[END_REF][START_REF] Dell | Exponential time complexity of the permanent and the tutte polynomial[END_REF]. Since the latter is unlikely, one could conclude that Pinwheel Scheduling is not solvable in pseudopolynomial time. It remains open whether the problem is PSPACEcomplete.

Similar to Pinwheel Scheduling, the k-server Periodic Maintenance Problem [START_REF] Mok | Algorithms and complexity of the periodic maintenance problem[END_REF][START_REF] Baruah | The complexity of periodic maintenance[END_REF][START_REF] Eisenbrand | Scheduling periodic tasks in a hard real-time environment[END_REF] has n jobs, each with a specified periodicity and a processing time. Each server may serve at most one job per time unit. However, job i is required to be served exactly every m i days apart rather than within every m i days. The case k = 1, c j = 1 for all j is analogous to Pinwheel Scheduling, except for the exact periodicity constraint. For any k ≥ 1, Mok et. al. [START_REF] Mok | Algorithms and complexity of the periodic maintenance problem[END_REF] have shown it is NP-complete in the strong sense. For the special case when m i are multiples of each other or when there are at most 2 different periodicities, they have shown it is in P. It was shown that even in the case of a single server and c j = 1 for all j the problem remains coNP-hard [START_REF] Sanjoy | Feasibility problems for recurring tasks on one processor[END_REF].

d Other related problems with a compact input representation include realtime scheduling of sporadic tasks [START_REF] Baruah | Scheduling real-time tasks: Algorithms and complexity[END_REF][START_REF] Bonifaci | Feasibility analysis of sporadic real-time multiprocessor task systems[END_REF], where we are given a set of recurrent tasks. On a single machine, EDF (Earliest Deadline First) is optimal. However, we remark that the complexity of deciding whether a given set of tasks is feasible has been open for a long time and only recently proved showing that it is coNP-hard to decide whether a task system is feasible on a single processor even if the utilization is bounded [START_REF] Ekberg | Schedulability analysis of a graph-based task model for mixed-criticality systems[END_REF].

Another related problem is the Bamboo Garden Trimming Problem introduced by Gasieniec et. al. [START_REF] Gasieniec | Bamboo garden trimming problem[END_REF]. There are n bamboos, each having a given growth rate, which may be viewed as inducing a periodicity. On each day, a robot may trim at most one bamboo back to height 0. The goal is to minimize the maximum height of the bamboos. Gasieniec et. al. provide a 4-approximation for the general case and a 2-approximation for balanced growth rates. This paper. We investigate the computational complexity of both the min-max and the min-avg version of rftt. Mostly we will relate their complexity to the complexity of Pinwheel Scheduling. Some interesting inapproximability results follow from this relation. After that, we will start with some special cases. In Section 3, we give our most remarkable result, a constant factor approximation for min-max on a tree, next to a less remarkable constant approximation for the min-avg version on the tree. In the same section, we show for min-avg that the problem can be solved to optimality in pseudopolynomial time on line metrics. Finally, in Section 4, we present logarithmic factor approximations for both problem versions on general metrics.

In this section, we investigate the computational complexity for both objectives. Since our problem requires finding a shortest tour visiting some subset of vertices for every day, it is at least as hard as the Traveling Salesman Problem (tsp). However it is also interesting to note that the problems are at least as hard as Pinwheel Scheduling as well. For the min-max objective there is a direct reduction showing that a factor 2 approximation is at least as hard as Pinwheel Scheduling: construct an unweighted star with the depot at the center and each leaf corresponding to a job in the pinwheel instance. This instance has value 2 only if there exists a pinwheel schedule and at least 4 otherwise.

For the min-avg rftt the reduction is a bit more involved, and given in the appendix.

Theorem 1. On series-parallel graphs, min-avg rftt is at least as hard as Pinwheel scheduling.

We note that this hardness result is incomparable to the tsp reduction. Pinwheel is neither known to be NP-hard nor in NP, although it is conjectured to be PSPACE-complete.

Lastly, as Theorem 2 shows, the min-max rftt remains hard even on star graphs (where TSP is trivial). A reduction can be found in the appendix.

Theorem 2. min-max rftt is NP-hard on star graphs.

Approximation on trees

In this section we give a 2-approximation for min-avg and a 6-approximation for min-max on trees.

We start out with a simplifying result, which will also be of use in the next sections. The proof of Lemma 1, which is not hard to derive, can be found in the appendix.

Lemma 1. Given an instance (G, τ ) of rftt, let τ be found by rounding every turnover time in τ down to a power of 2. Then OP T (G, τ ) ≤ 2OP T (G, τ ) for both min-avg and min-max objectives.

In the remainder we assume w.l.o.g. that G is rooted at s and that turnover times are increasing on any path from the depot to a leaf node in G. Furthermore, for an edge e in E we define D(e) to be the set of vertices that are a descendant of e. We also need the following definition.

Definition 1 (tt-weight of an edge). For any edge in G we define:

q(e) = min j∈D(e) τ j .
We call this quantity the tt-weight (turnover time-weight) of e.

This definition allows us to express the lowerbound in Lemma 2.

Lemma 2 (tt-weighted tree). For an instance (G, τ ) of the rftt on trees it holds that the average tour length is at least:

L(G, τ ) := 2 e∈E c(e) q(e)
.

Proof. This follows immediately from the fact that 2 q(e) lower bounds the number of times edge e must be traversed on average in any feasible solution.

Since the maximum tour length is at least the average tour length, Lemma 2 also provides a lower bound for the min-max objective.

An approximation for min-avg rftt is thus found by rounding all turnover times to powers of 2 and then visit each client j on every day that is a multiple of τ j . Since in that case the lower bound of Lemma 2 is exactly attained on the rounded instance, Lemma 1 implies the following theorem.

Theorem 3. There is a 2-approximation for min-avg rftt on trees.

MIN-MAX

We will now show that we can achieve a 6-approximation for min-max rftt on trees by providing a 3-approximation algorithm if all turnover times are powers of 2 and then applying Lemma 1.

The main idea is to take a TSP-tour and recursively split it to obtain a schedule for the clients with increasing turnover times. During the splitting process, we assign each client j on that tour to a congruence classes āτj = {k ∈ N|k ≡ a (mod τ j )} for some a ≤ τ j , to indicate we want to visit j on each day in āτj . Similarly, we distribute all edges e to a congruence class āq(e) . We do this ensuring that on any given day, we can create a tour through all clients associated with that day, using the edges associated with that day plus a small set of extra edges.

Let us define some further notation. For a given congruence class ām ⊆ N, we denote g(ā m ) ⊆ V the set of vertices and f (ā m ) ⊆ E the set of edges assigned to that class. Note that ām and (a + m) m define the same congruence class, so f (ā m ) = f ((a + m) m ). Then, for any k ∈ N we have that J k , the set of clients we need to visit on day k, is

J k = m∈N,a≤m|k∈ām g(ā m ).
The assignment of vertices and edges to classes is guided by the recursive splitting of a TSP-tour in G. The full procedure for constructing f (•) and g(•) is shown in Algorithm 1. The algorithm is initially called with d, a TSP-tour visiting all vertices in G, and a = m = 1 and will determine the set of vertices to be visited on every day (i.e., those congruent to ā1 ). Then the first (second) recursive call determines the sets of vertices with turnover time 2 that will be visited on odd Algorithm 1 Algorithm for recursively constructing f (•) and g(•)

function RecurseTreeSchedule(d, a, m) Require: d, a connected sequence of edges in G, powers of 2 turnover times τ ; a, m,

integers if d = ∅ then f (ām) = {e ∈ d | q(e) = m} g(ām) = {j ∈ V (d) | τj = m} k = max k s.t. i∈[k -1]|q(d i )>m c(d i ) q(d i ) ≤ 1 2 i∈[n]|q(d i )>m c(d i ) q(d i ) d 1 = (d1, . . . , d k-1 ) d 2 = (d k+1 , . . . , dn) RecurseTreeSchedule(d 1 , a, 2m), RecurseTreeSchedule(d 2 , a + m, 2m) end if end function
(even) days. Analougously, RecurseTreeSchedule(d 1 , a, m) will return the set of vertices with turnover time m to be visited on days in the congruence class ām and the two recursive calls will return the set of vertices with turnover time 2m that are visited on days a, a + 2m, a + 4m, . . . and a + m, a + 3m, a + 5m, . . ., respectively.

In the remainder we assume that any call to f (•) and g(•) returns the empty set for any argument that is not explicitly handled in Algorithm 1. Note that we use the notation V (A) to denote the vertices incident to edges in A ⊆ E. Lemma 3. After Algorithm 1 terminates, each vertex j appears in some set g(ā τj ) for some a.

Proof. Note that d 1 ∩ d 2 = ∅ and that |d 1 ∪ d 2 | = |d| -1; since d is a connected set of edges then in each call to RecurseTreeSchedule, V (d 1 )∪V (d 2 ) = V (d).
Therefore no vertex is skipped in the construction of g(•).

In order to find a tour on day k through the vertices in J k we use edges in h=1,2,...,m f (ā h ); as we already observed this set of edges does not necessarily connect vertices in g(ā m ) to the depot. The next lemma shows that a tree that connects all vertices in g(ā m ) to the root can be found by considering ∪ h=1,2,...,m f (ā h ) and adding a shortest path from some vertex in g(ā m ) to the depot.

Lemma 4. Let a, m be such that f (ā m ) is nonempty. Let P be the set of edges on the shortest path connecting some arbitrary edge in f (ā m ) to the root of G. Then the following edge set forms a connected component:

T (ā m ) := P ∪ ( h=1,2,...,m f (ā h )). Moreover, T (ā m ) spans h=1,2,...,m/2,m g(ā h ).
Proof. To prove our first claim, we first show that for k ≤ m, f (ā k ) either induces at most one connected component, or each component it induces is incident to a component induced by h=1,2,..,k/2 f (ā h ). Then, we will show that if f (ā k ) induces at most one connected component, it is incident to P ∪ ( h=1,2,..,k/2 f (ā h )).

Suppose f (ā k ) does not induce at most one component. Note that f (ā k ) is the subset of edges in some connected edge sequence d through G that have tt-weight k. But by the way tt-weight is defined and the fact that G is a tree, a simple path connecting disjoint edges with tt-weight k, can only consist of edges with tt-weight at most k. So every two components in f (ā k ) are connected through a path of edges with tt-weight of at most k. Moreover since the sequence d used to construct f (ā k ) is a subset of the sequence used to construct f (ā k/2 ), by induction these connecting paths must be contained in h=1,2,...,k/2 f (ā h ), as required.

Next we show that for any k ≤ m such that f

(ā k ) = ∅, if f (ā k ) is not incident to P then it is incident to h=1,...,k/2 f (ā h ).
Let d be the sequence that was used to construct f (ā k ). Since d contains all edges in f (ā m ) and P contains at least one such edge, there exists a minimal path Q that contains some edge e in f (ā k ) such that Q is connected to P . Moreover since Q is minimal and P contains the root, e must be the edge furthest away from the root on Q. This implies that all edges on Q have tt-weight k or less. Now suppose that Q contains edges with tt-weight strictly less than k. Then those edges are necessarily in h=1,...,k/2 f (ā h ) and therefore

f (ā k ) is incident to that set. If not then Q is strictly contained in f (ā k ) and therefore f (ā k ) is connected to P .
The first claim of our lemma now follows by induction.

P ∪ f (ā 1 ) is clearly connected. If P ∪ h=1,2,...,k/2 f (ā h ) is connected, we get that f (ā k )
is either empty or is connected to P or to h=1,2,...,k/2 f (ā h ), and the result follows.

To prove our second claim, suppose that for some k and j ∈ g(ā k ) it holds that no edge incident to j, is in h=1,2,...,k f (ā h ). We will show that that j appears on P , from which our claim immediately follows.

Let d be the sequence used to construct g(ā k ). The edge e incident to j that is closest to the root, satisfies q(e) ≤ k. So, it cannot be in d otherwise it would be contained in h=1,2,...,k f (ā h ). But this implies that e cuts off every edge in d from the root, and therefore e appears on P , as claimed, concluding the proof.

The next lemma allows us to bound the cost of edges included in f (ā h ). Proof. The proof is by induction on m. Since we initially call the algorithm with d a TSP-tour in G, which visits each edge twice, it clearly holds for m = 1. Now for m > 1, suppose it holds for all smaller m. Without loss of generality, suppose we have a call to the function with input d 1 , a, m, such that d, a, m/2 are the input parameters for its parent in the call stack. For the first equality, we split the second sum into an h = m/2 part and an h = 1, . . . , m/4 part. In the first inequality we used the way d 1 and d 2 are determined in Algorithm 1, in the second inequality we used that f (ā m ) ⊆ d and in the last inequality we used the inductive hypothesis, concluding the proof.

We are now ready for the main theorem.

Theorem 4. There is a 6-approximation for min-max rftt on trees.

Proof. We first round all turnover times down to powers of 2, which loses a factor of 2 in the optimal solution. We then use Algorithm 1 to construct f (•) and g(•) thus determining the set of vertices J k to be visited on day k. By Lemma 3 this defines a feasible schedule.

If we then take T ( kτmax ) as in Lemma 4, we get a tree that spans J k . Moreover the weight of T ( kτmax ) is at most 3 2 OP T : the contribution of P is at most 1 2 OP T , since we need to reach any client at least on some day (and drive back), while the contribution of h=1,..τmax f ( kh ) is at most L(G, τ ) ≤ OP T , which can be seen by applying Lemma 5 for m = 2τ max . Lastly, since we need a tour around T ( kτmax ), we lose another factor 2. This gives the approximation factor of 6.

It remains to show that Algorithm 1 runs in polynomial time, and that we can find a polynomial representation for the schedule. For the first claim, note that in each recursive call to the algorithm, the following equality holds |d 1 ∪ d 2 | = |d| -1; hence the algorithm terminates after at most 2|E(G)| calls.

For the second claim, the crucial observation is that we only need to store the entries of g for a and m such that g(ā m ) is nonempty. Since at most one entry is defined in every call to the algorithm, and we can simply check if k ≡ a (mod m) for all stored entries, the claim, and the theorem, follow.

MIN-AVG on the line

As an even more special underlying metric, we might consider the min-avg problem on the line (on a path). For the min-max version this case is trivial, but for the min-avg version its complexity is unclear: we do not know whether it is in NP, although we expect it to be NP-hard.

On the positive side we can show that the problem is not strongly NP-hard.

Theorem 5. min-avg on the line can be solved in pseudopolynomial time.

The proof of Theorem 5 is deferred to the appendix, where we give a DP that finds an optimal schedule in polynomial time for any instance with polynomially bounded turnover times.

Approximation on general graphs

We will now present logarithmic approximations for both objectives. Note that an O(log τ max )-approximation is readily achieved; simply treat the sets of clients with equal turnover time as independent instances. For min-avg, the problem with equal turnover times is simply tsp, for the min-max we get a problem sometimes called the k-tsp, for which a 5 2 approximation is known [START_REF] Frederickson | Approximation algorithms for some routing problems[END_REF]. Since by rounding to powers of 2, we ensure there are O(log(τ max ) different turnover times, we get Theorem 6 (a formal proof can be found in the appendix). Theorem 6. min-max and min-avg rftt have an O(log τ max )-approximation.

In the case of min-max it is relatively simple to adapt this idea for an O(log n)-approximation by appropriately reassigning clients to lower turnover times, as per Theorem 7.

Theorem 7. min-max rftt has an O(log n)-approximation.

Proof. We start by assuming that every turnover time is a power of 2. Next, we split up the instance into two new instances. To this end we first define a turnover time k to be saturated if |{j ∈ V |τ j = k}| ≥ k. In the first instance we retain the set of vertices V 1 with saturated turnover times, and in the second all vertices V 2 with unsaturated turnover times. Now if all turnover times are saturated, then τ max = O(n) and we can find a O(log n)-approximation using Theorem 6. So what remains is to find a O(log n)-approximation for the second instance.

Since no turnover time is saturated, it is easy to see that we can partition the vertices in V 2 into log n sets W 1 , W 2 , W 4 , . . . , W 2 log n , such that |W i | ≤ i, and such that τ j ≥ i for all j ∈ W i . For example we could first add all vertices j with τ j = i to W i for i ≤ log n , and then arbitrarily distribute vertices j with τ j > log n among the sets that have space. We now produce a schedule by visiting all clients in any set W k on different days. This is feasible and implies that at most log n clients are visited on a given day, which leads to O(log n)-approximation factor, as required.

The approach of Theorem 6 does not trivially extend to the min-avg case. However, we may combine our result on trees with the FRT tree embeddings [START_REF] Fakcharoenphol | A tight bound on approximating arbitrary metrics by tree metrics[END_REF], to get a randomized O(log n)-approximation.

A more direct, and deterministic O(log n)-approximation is possible as well.

In particular, we use the simple heuristic of visiting each client on every day that is a multiple of its turnover time, when turnover times are powers of 2. We call such a schedule a synchronized solution, and show that gives a logarithmic approximation.

The proof of this approximation factor, which is not trivial, works by show that a synchronized schedule is no more costly than a non-decreasing schedule, in which all tours are routed along a tree with turnover times non-decreasing from the root. We then show how to transform any schedule to a non-decreasing one, losing a logarithmic factor in the process. As a byproduct we show that the analysis is tight, an that a non-decreasing schedule must be Ω(log n) times more costly than OPT in the worst case. The proof of Theorem 8 can be found in the appendix.

Theorem 8. min-avg rftt has an O(log n)-approximation.

It is an open question whether there exists a constant factor approximation algorithm for the general case. We observe that the approach of first finding a tree spanning all vertices and then using the algorithm of Section 3 is unsuccessful. In fact there exist instances of the problem on a graph G with n vertices, such that if we limit our attention to tours that for each day use only edges of a spanning tree of G then the obtained solution is Ω(log n) approximated. This implies that we need some new ideas, in order to improve the O(log n) approximation of the previous theorem.

Conclusion

In this paper, we considered replenishment problems with fixed turnover times, a natural inventory-routing problem that has not been studied before. We formally defined the rftt problem and considered the objectives min-avg and min-max. For the min-avg rftt, we showed that it is at least as hard as the intractable Pinwheel Scheduling Problem on series-parallel graphs and we gave a 2approximation for trees. For the min-max objective we showed NP-hardness on stars and gave a 6-approximation for tree metrics. We also presented a DP that solved the min-avg rftt in pseudopolynomial time on line graphs. Finally, we gave a O(log n)-approximation for the min-max objective on general metrics.

The results that we present should be considered as a first step in this area and many problems remain open. An intriguing open problem is the complexity of the of rftt on a tree. Namely, for min-avg variant we conjecture that the problem is hard, and we ask whether the simple 2-approximation we provide can be improved. For the min-max variant it is open whether the problem is APX-hard and whether we can improve the 6-approximation, Next to replenishing locations with routing aspects as we studied in this paper, scheduling problems modeling maintenance or security control of systems, form a class of problems to which this model naturally applies. It would be interesting to study such fixed turnover time problems in combination with scheduling. Would this combination allow for more definitive results?

A Proof of Theorem 1

Proof. Given an instance p 1 , ..., p n of Pinwheel Scheduling, create an instance (G, τ ) of min-avg rftt. We define

V = {s, w 1 , w, w 2 } ∪ V 1 ∪ V 2 , where V i = {v i 1 , ..., v i n } for i = 1, 2, E = {(s, v)|v ∈ V 1 ∪ V 2 } ∪ {(w i , v i j )|∀j; i = 1, 2} ∪ {(w 1 , w), (w 2 , w)},
and

τ w 1 = τ w 2 = τ w = 1, τ v 1 j = τ v 2 j = p j .
All edge weights are 1. See Figure 1 for an illustration.

We claim that the instance (G, τ ) has a solution of cost 6 if and only if p 1 , ..., p n is a feasible Pinwheel Scheduling instance.

For the 'if'-direction, suppose we have a feasible pinwheel schedule. Then we create a replenishment schedule as follows: we take the set of jobs visited on day k, J k = {v 1 j , w 1 , w, w 2 , v 2 j }, where job j is the job scheduled on day k in the pinwheel solution (when no job is visited, pick one arbitrarily). The pinwheel schedule then guarantees that the periods of jobs in V 1 ∪ V 2 are satisfied, while jobs w 1 , w, w 2 are visited every day, as required. Now since any tour (s, v 1 j , w 1 , w, w 2 , v 2 j , s) has length 6, we can do this within the claimed cost.

For the 'only if'-direction, note that any replenishment schedule must have cost 6 at least, since no tour that visits w 1 , w, w 2 costs less than that. Moreover, any tour visiting those three vertices that is not of the form (s, v 1 j , w 1 , w, w 2 , v 2 j , s), will cost strictly more than 6. It follows that if the cost of the replenishment schedule is 6, every tour visits at most one job from V 1 (and the same for V 2 ). Since τ v 1 j = p j for all j, this directly implies that the Pinwheel Scheduling instance is feasible.

w w 1 w 2 v 1 1 v 1 2 v 1 3 v 2 1 v 2 2 v 2 3

B Proof of 2

In 3-Partition, we are given 3m integers a 1 , . . . , a 3m and an integer B = 1

m i a i such that B 4 < a i < B 2 for all i.
The question is whether we can partition the integers into m sets of three integers that add up to B [START_REF] Garey | Computers and intractability: A guide to the theory of NP-completeness[END_REF].

Proof. Given an instance of 3-Partition, create a weighted star graph G with the depot at the center and for every integer a i a leaf vertex attached with an edge of weight a i /2. Finally set the turnover time to m for every leaf. We will show that the rftt instance has value B if and only if we have a YES-instance for 3-Partition.

Given a valid partition of the integers, clearly one can assign every set of 3 integers a unique day in 1, . . . , m and visit the associated leaf on every multiple of that day for a valid rftt solution. That the opposite direction works as well hinges on the fact that B 4 < a i for all i, so we cannot visit more than 3 clients on one day. Since after m days all clients must have been visited due to the turnover times, it follows that the first m days of the schedule corresponds to a valid partition.

C Proof of Lemma 1

Proof. Let (G, τ ) denote the instance found from (G, τ ) by rounding every turnover time up to a power of 2. Since any schedule remains feasible if we round up the turnover times, we have that OP T (G, τ ) ≤ OP T (G, τ ) ≤ OP T (G, τ ).

Suppose we have an optimal solution for (G, τ ) in which Tk is scheduled on day k. We can construct a feasible schedule for (G, τ ) by scheduling the concatenation of T2k-1 and T2k on day k. The maximum tour length in this schedule is at most twice that of the optimal solution for (G, τ ) and every tour from the original schedule is visited exactly twice in the new schedule, so this yields a factor 2 increase in both the min-max and the min-avg objective.

D A dynamic program that proves Theorem 5

In this section we will show how to solve the min-avg problem on the line in pseudopolynomial time. Since we are minimizing the average, it is easy to see that we can reduce this problem to two times the min-avg problem on the half-line (a path with the depot in one of the leaves). On the half-line each vertex i has a distance d i ∈ N from the origin. Suppose vertices are numbered such that d 1 ≤ . . . ≤ d n . We present a pseudopolynomial time dynamic programming agorithm for this problem, based on the following observations. First of all, we note that on any tour visiting vertex j automatically visits every vertex i < j. As in the tree case, we therefore assume that τ i ≤ τ j for i < j. Thus, after visiting j, all i ≤ j have a remaining turnover time of τ i . For the dynamic program to work, we guess L, the day on which vertex n is visited for the first time and try all guesses between 1 and τ n .

The dynamic program now works as follows. Suppose we are given the optimal solution for vertices 1, . . . , i -1 when only considering the days 1, . . . , k. Now we want to include i in the optimal solution for the first k days. If k < min{τ i , L}, it is not necessary to visit i during the first k days, and hence it is optimal to take the optimal solution for the first i -1 vertices and k days. Otherwise, we need to visit i on some day in {1, . . . , min{τ i , L}}. Before day , we only need to visit the vertices 1, . . . , i -1. Thus, we take the optimal -1 tours for visiting the first i -1 vertices in the first -1 days. After day , all vertices have the same remaining turnover time as they had at time zero. Hence, we can take the optimal tours for the first i vertices and k -days.

Let φ L (i, k) := the minimum cost of the first k tours visiting vertices 1, ..., i. We initialize φ L (0, k) = φ L (i, 0) = 0 and we use the recursion:

φ L (i, k) = φ L (i -1, k) , if k < min{τ i , L} min =1,...,min{τi,L} φ L (i -1, -1) + d i + φ L (i, k -) , else
The optimal solution is the schedule that corresponds to the value L ∈ {1, . . . , τ n } minimizing φ L (n, L)/L. Note that the algorithm runs in time O(nτ 3 n ), implying the following. Theorem 9. min-avg on the line can be solved in pseudopolynomial time.

E Proof of Theorem 6

Proof. By Lemma 1 we may assume every τ i is a power of 2 so that there are at most log τ max different turnover times. We simply treat the sets of vertices with the same turnover time as separate instances and concatenate the solutions. Our result then follows from the fact that for all these instances a constant factor approximation is available. In the case of the min-max objective we get the k-tsp problem, where k is equal to the turnover time of the vertices in the instance. In the case of min-avg, we need to minimize the sum over all k tours. But since all turnover times are equal there is no advantage to visiting vertices on different days, hence we recover a simple tsp problem.

F Proof of Theorem 8 and tightness of analysis

This section provides two proofs of Theorem 8, which shows that we can get a O(log n)-approximation for the min-avg objective as well. The first proof is a direct application of metric tree embeddings.

Proof (Proof of Theorem 8). We will apply the FRT tree embedding [START_REF] Fakcharoenphol | A tight bound on approximating arbitrary metrics by tree metrics[END_REF] of the initial instance and then use the 2-approximation for tree metrics to obtain the final solution. Given the instance (G, τ ), let T be a random tree produced by the tree metric approximation with O(log n) distortion. Then

d G (u, v) ≤ d T (u, v) and E[d T (u, v)] ≤ O(log n)d G (u, v).
Let S be the solution produced by the 2-approximation for min-avg rftt on the tree metric T . Then

E[S] ≤ 2E[OP T (T, τ )] ≤ O(log n)E[OP T (G, τ )
] by linearity of expectation on the sum over the edges.

The second proof arises from a more natural algorithm given by a simple greedy strategy. We round all periods to powers of 2 and delay visiting any client for as long as possible. Next, for every day we use any constant factor approximation for TSP to calculate a tour on the clients whose visit can no longer be delayed. We call this a synchronized solution. It takes some work to show this does indeed provide a logarithmic approximation though. We do this by showing that any synchronized solution is no more costly than a non-decreasing solution, in which every tour is based on a tree that has the clients ordered by ascending turnover times from root to leaves. We then show that such a non-decreasing solution costs at most O(log n) times the optimal solution , and provide an example showing this analysis is tight. Moreover, we show that the optimal non-decreasing solution is at most twice as costly as the optimal synchronized solution. This implies that that any sub-logarithmic approximation algorithm must avoid finding such solutions.

As always we will assume that turnover times are rounded to powers of 2. Let us define a synchronized solution, as one where a client with turnover time 2 i is visited on each day that is a multiple of 2 i , for all i. We define a non-decreasing tree as a tree on the depot and subset of clients, such that the turnover times on every path from the depot to the leafs are non-decreasing. A non-decreasing solution is a solution in which for each day the tour is given by visiting the clients of a non-decreasing tree in depth first order.

The following two lemmas show that optimal synchronized and non-decreasing solutions differ in cost by at most a constant factor. Lemma 6. The optimal synchronized solution costs at most two times the optimal non-decreasing solution.

Proof. Suppose we have a non-decreasing solution. Let T i be the non-decreasing tree associated with day i, for i ∈ N. We will show that we can find a set of trees T i for i ∈ N that cost at most as much as T i on average, and such that any client v appears in tree T i if i is a multiple of τ v . A synchronized solution can then be found by taking the tour on day i to be a tour depth first search in T i , losing a factor 2.

Iteratively, from j = 0, . . . , log τ max , we build the new trees. In iteration j and for all i, select all unmarked edges in T i that are used on a path from the depot to a client v with τ v = 2 j , and mark them. Then insert these edges in the tree T k for the earliest following day k that is a multiple of 2 j , so k = i 2 j 2 j . We now show by induction that after iteration j, for each day k that is a multiple of 2 j , T k is a tree connecting the depot to all clients v with turnover time 2 j . The base case j = 0 follows from the fact that the trees T i are non-decreasing and must contain every client with turnover time 1. For higher j, it is easy to see that T k must contain a path from v to w for all clients v with τ v = 2 j and some w with τ w < 2 j . But T k already contains w by our inductive hypothesis and the result follows.

We remark that we have corresponding converse result, as per Lemma 7.

Lemma 7. The optimal non-decreasing solutions costs at most two times the optimal synchronized solution.

Proof. We may assume that any synchronized solution uses at most log(τ max ) + 1 distinct tours, lets label them T 0 , . . . , T log(τmax) , where T j visits all clients with turnover time at most 2 j . Furthermore define ∆ 0 = c(T 0 ) and ∆ j = c(T j )c(T j-1 ), for j = 1, . . . , log(τ max ). Then it holds that the cost of the synchronized solution is

c sync = log(τmax) j=0 1 2 j ∆ j .
Now note that we can create a non-decreasing tree for any day with 2 j as its largest power of 2 factor from the synchronized solution, by taking the union of T 0 , . . . , T j where we shortcut every client v with τ v < 2 j in tour T j . But the cost of such a solution is

c ndecr = log(τmax) j=0 1 2 j c(T j ) = log τmax j=0 1 2 j j i=0 ∆ i = log τmax i=0 log τmax j=i 1 2 j ∆ i ≤ 2 log τmax i=0 1 2 i ∆ i = 2c sync
Our main result follows from showing that we can always find a non-decreasing solution of cost O(log n) times OP T . We use the following tree pairing Lemma by Klein and Ravi [START_REF] Klein | A nearly best-possible approximation algorithm for node-weighted steiner trees[END_REF]. Lemma 8. Given any tree T and an even subset S of its vertices, there is a pairing of vertices covering S such that the tree-path induced by the pairs are edge-disjoint.

Using the tree pairing Lemma 8, we will construct non-decreasing trees to approximate arbitrary trees. First we define the notations needed for the algorithm.

A non-decreasing arc a({u, v}) of {u, v} is the arc between u and v that points from the client with lower turnover time to the one with higher turnover time (ties are broken arbitrarily). The client with the lower (higher) turnover time is denoted by L({u, v}) (H({u, v})). We denote by U the unpaired clients and A the arcs of the non-decreasing tree being constructed, and require that all arcs must eventually point away from the depot. Lemma 9. Given an arbitrary tree T of cost c(T ), there is a non-decreasing tree of cost at most log n c(T ).

Algorithm 2 Algorithm to create non-decreasing tree from arbitrary tree 1: Initialize U ← V and A ← ∅. 2: while |U | > 0 do: 3:

Find an edge-disjoint pairing P of a largest even subset of U . 4:

for {u, v} ∈ P do: 5:

A ← A ∪ a({u, v}).

6:

U ← U \ H({u, v}).

7:

end for 8: end while Proof. Let T be a tree. We will construct a non-decreasing tree T by iteratively pairing off the vertices and directing each pair in a non-decreasing manner.

In the algorithm, we apply the pairing procedure log n times to get a nondecreasing tree of the desired cost. In each round, we pair a largest subset of V such that the pairs induce edge disjoint paths in T . Then we direct each pair {u, v} in ascending order of turnover times and delete the client with higher turnover time from consideration. These arcs are added to the arc set of T . We can think of each pair as a connected component represented by the client with the smallest turnover time. In the end, T is finalized when no unpaired vertices remain. Note that picking the vertex of minimum turnover time as the representative per connected component ensures that the final tree is indeed directed away from the depot.

In each round, we used each edge of T at most once since all pair-induced paths were edge-disjoint. Let κ(t) be the number of vertices at the beginning of round t. Since each round paired off either all vertices or all but one vertex, we have κ(t) = κ(t -1)/2 . So the total number of rounds is log n . Hence c(T ) ≤ log n c(T ).

Proof (Proof of Theorem 8). Given an optimal solution, let T i be the minimum Steiner tree on the set of clients visited on day i, which costs no more than the tour of that day. Using Lemma 9 we can find non-decreasing trees T i of cost at most O(log n)c(T i ). Turning the trees into tours loses only a constant factor, which gives us a non-decreasing solution of cost O(log n) times OP T . By Lemma 6 we may then turn this solution into a synchronized one as required, concluding the proof.

The bound in the proof of Theorem 8 is tight; as there exists a class of instances where requiring a solution to be non-decreasing introduces a logarithmic optimality gap. Together with Lemma 7, this implies that our algorithm does no better than O(log n) as well.

Proposition 1. There exists a class of instances in which there is a logarithmic optimality gap between the optimal and the optimal non-decreasing solution.

To show that the bound in the proof of Theorem 8 is tight, we first show that Lemma 9 is tight. Consider the following sequence of sequences (a 0 , a 1 , . . .) where a 0 = (1) and a i+1 is generated by alternatingly taking an element from a i and then from the sequence b i = (2 i + 1, 2 i + 2, . . . , 2 i+1 ). For example:

a 0 = 1 a 1 = 1, 2 a 2 = 1, 3, 2, 4 a 3 = 1, 5, 3, 6, 2, 7, 4, 8 -• • • Then define the (unweighted) graph G i as the path graph with 2 i vertices, where the jth vertex has turnover time 2 a i j -1 . See Figure 2 for an example. The minimum spanning tree in G i costs 2 i -1. It is easy to check that the decreasing spanning tree produced by Algorithm 2 costs i2 i-1 . Moreover, since the solution produced attaches every vertex to a nearest vertex with lower turnover time, it must be optimal.

To show tightness of our main theorem, we will define another class of graphs H i for i ≥ 1 that are constructed from {G i }. The idea is to make τ j copies of each terminal j, and then connect them in a regular way, for example like in Figure 3. Formally H i is constructed as follows. For simplicity of description, we assume that G i is planarly embedded from left to right, and we assume that we keep a planar embedding of H i during construction.

We first copy node 1 to H i . Now we work from left to right, starting from the second node. When we are at node j, we put τ j copies of j vertically above each other and to the right of the copies of j -1 in H i . Then we connect them to the copies of j -1 in H i such that the graph remains planar and all copies of j -1 have the same degree, and all copies of j have the same degree. This can be done in only one way. Furthermore we identify vertex 1 with the depot. Proposition 2. The instance induced by H i has a logarithmic optimality gap between the optimal and the optimal non-decreasing solution.

Proof. There exists an obvious solution that visits exactly one client of each turnover time per day, that costs 2(2 i -1). Now suppose we impose non-decreasing constraints. In this case we need to use (on average) at least one edge pointing from a client with a lower turnover time to one with a higher turnover time per day. But from our reasoning on the decreasing minimum spanning tree in G i , we find that the cheapest set of edges that contains at least one edge pointing from a client with turnover time 2 i to one with lower turnover time for all i, costs at least i2 i-1 . Therefore the optimal solution under non-decreasing constraints is at least a logarithmic factor more expensive than the optimal solution.

Lemma 5 .

 5 During each (recursive) call to RecurseTreeSchedule, it holds that (ā h )|q(e)=h c(e) ≤ L(G, τ ).

  ..., m 4 e∈f (ā h )|q(e)=h c(e) ≤ L(G, τ )

Fig. 1 .

 1 Fig. 1. Instance created in the proof of Theorem 1.

  s

Fig. 2 .

 2 Fig. 2. Illustration of G2, (turnover times in circles) 1 4 2 8

Fig. 3 .

 3 Fig. 3. Illustration of H2 τi = 1 τi = 4 τi = 2 τi = 8


Jomar Da Silva
email: jomar.silva@uniriotec.br

Kate Revoredo
email: katerevoredo@uniriotec.br

Fernanda Araujo Baião
email: fernanda.baiao@uniriotec.br

Jérôme Euzenat
email: jerome.euzenat@inria.fr

Interactive Ontology Matching: Using Expert Feedback to Select Attribute Mappings

Keywords: ontology matching, Wordnet, interactive ontology matching, ontology alignment, interactive ontology alignment

Interactive Ontology Matching considers the participation of domain experts during the matching process of two ontologies. An important step of this process is the selection of mappings to submit to the expert. These mappings can be between concepts, attributes or relationships of the ontologies. Existing approaches define the set of mapping suggestions only in the beginning of the process before expert involvement. In previous work, we proposed an approach to refine the set of mapping suggestions after each expert feedback, benefiting from the expert feedback to form a set of mapping suggestions of better quality. In this approach, only concept mappings were considered during the refinement. In this paper, we show a new approach to evaluate the benefit of also considering attribute mappings during the interactive phase of the process. The approach was evaluated using the OAEI conference data set, which showed an increase in recall without sacrificing precision. The approach was compared with the state-of-the-art, showing that the approach has generated alignment with state-of-the-art quality.

Introduction

Ontology matching aims to discover correspondences (mappings) between entities of different ontologies [START_REF] Euzenat | Ontology Matching -Second Edition[END_REF]. One of its strategies is the interactive one. Interactive ontology matching approaches consider the knowledge of domain experts during the matching process. The interaction with the user can be used to improve the results over fully automatic approaches [START_REF] Paulheim | Towards Evaluating Interactive Ontology Matching Tools[END_REF]. An important step of this strategy is the definition of the set of mappings to be submitted to the expert for feedback. This set to be submitted to the expert was called, in this paper, set of mapping suggestions. Existing approaches [START_REF] Paulheim | Wesee-match results for oaei[END_REF][4] [START_REF] Duan | One size does not fit all: Customizing ontology alignment using user feedback[END_REF][6] [START_REF] Li | Improving ontology matching with propagation strategy and user feedback[END_REF][8] [START_REF] To | An Adaptive Machine Learning Framework with User Interaction for Ontology Matching[END_REF][10] [START_REF] Cruz | Interactive user feedback in ontology matching using signature vectors[END_REF][12] [START_REF] Lambrix | A Session-based Ontology Alignment Approach enabling User Involvement[END_REF][14] [START_REF] Jiménez-Ruiz | Large-scale interactive ontology matching: Algorithms and implementation[END_REF] define this set before the interaction with the expert begins; thus, the approaches do not use expert feedback to select mappings to the set of mapping suggestions.

In previous work [START_REF] Da Silva | Semantic interactive ontology matching: Synergistic combination of techniques to improve the set of candidate correspondences[END_REF], we combined a structural and a semantic technique for interactively considering the expert feedback in the revision of the set of mapping suggestions, but taking into account only concept mappings. However, considering also the properties of these concepts may bring a better integration of the ontologies.

In this work, we propose ALIN Attr to evaluate the benefit of also considering attribute mappings during the interactive strategy. The attribute mappings suggested are associated with the concept mappings evaluated by the expert; therefore, they are more prone to be correct and potentially increase the recall compared with existing strategies that automatically include attribute mappings [START_REF] Faria | The agreementmakerlight ontology matching system[END_REF] [START_REF] Jiménez-Ruiz | Large-scale interactive ontology matching: Algorithms and implementation[END_REF].

The evaluation results evidenced the benefit of considering attributes during the interactive phase, using a heuristic for choosing the attribute mappings inspired on the Stable Marriage Problem [START_REF] Gale | College admissions and the stability of marriage[END_REF] [START_REF] Irving | Stable marriage with ties and bounded length preference lists[END_REF]. In addition, the current approach was compared to the state-of-the-art.

The rest of this paper is organized as follows. Section 2 reviews interactive ontology matching. Section 3 presents the approach, which is called ALIN Attr , and its implementation. Section 4 describes our evaluation methodology and discusses experimental results. Finally, section 5 concludes the paper.

Interactive Ontology Matching

An interactive ontology matching process is an ontology matching process considering the involvement of domain experts. In this paper, we consider this involvement as the domain experts providing feedback about mappings of ontologies entities, that is, mapping are presented to the expert who replies which of them should be accepted or rejected. Therefore, the approach takes advantage of the knowledge of domain experts towards finding an alignment.

The most relevant steps in this process are the selection of the mappings to receive expert feedback and the propagation of this feedback. Furthermore, the propagation may also impact the mappings selected for future expert feedback. The different existing approaches for interactive ontology matching vary in techniques for these two steps.

In the selection step, the existing approaches of interactive ontology matching use similarity metrics to select the set of mapping suggestions. The similarity metric is a function that returns a numeric value, indicating the similarity between the two entities of a mapping, according to some criterion. An approach can associate one or several similarity values, each of a different similarity metric, to a mapping.

In the selection step, the approaches can use multiple matchers, algorithms that receive, as input, entities and generate, as output, mappings. Each matcher can use different similarity metrics, among other features. At the end of the selection step, the results of these matchers can be combined and filtered generating the set of mapping suggestions [START_REF] Lambrix | A Session-based Ontology Alignment Approach enabling User Involvement[END_REF].

In the propagation step, user feedback can be used in different ways. Some approaches automatically classify some mapping suggestions using a threshold, a value that indicates whether a mapping should be automatically accepted (in some cases rejected) if its similarity values are greater (or smaller) than it. Expert feedbacks are used to calculate this threshold [START_REF] Paulheim | Wesee-match results for oaei[END_REF][4] [START_REF] Duan | One size does not fit all: Customizing ontology alignment using user feedback[END_REF][6] [START_REF] Li | Improving ontology matching with propagation strategy and user feedback[END_REF]. Some approaches automatically classify some mappings of the set of mapping suggestions using a classifier. These approaches use expert feedbacks to create the training dataset for learning the classifiers [8] [START_REF] To | An Adaptive Machine Learning Framework with User Interaction for Ontology Matching[END_REF]. Some approaches use expert feedbacks to modify the weight of similarity metrics [START_REF] Duan | One size does not fit all: Customizing ontology alignment using user feedback[END_REF][6] [START_REF] Balasubramani | User involvement in ontology matching using an online active learning approach[END_REF] or to directly change the value of similarity metrics [START_REF] Cruz | Interactive user feedback in ontology matching using signature vectors[END_REF] [START_REF] Cruz | Pay-as-you-go multiuser feedback model for ontology matching[END_REF]. Expert feedbacks are also used to remove mapping suggestions from the set of mapping suggestions [START_REF] Lambrix | A Session-based Ontology Alignment Approach enabling User Involvement[END_REF][14] [START_REF] Jiménez-Ruiz | Large-scale interactive ontology matching: Algorithms and implementation[END_REF].

The ALIN Attr Approach

In this section, we describe our approach, ALIN Attr , for interactively matching two ontologies. ALIN Attr , at each interaction, uses expert feedback to remove mapping suggestions and include new attribute mapping suggestions into the set of mapping suggestions.

The ALIN Attr top-level algorithm (Algorithm 1) starts with a pair of ontologies (O and O ) and a set of similarity metrics (SoM). Then, it splits in two main steps. The first one defines the initial mapping suggestions (SMS) and the initial alignment (A) (line 1 to line 17 of Algorithm 1) and the second one interactively receives expert feedback to a mapping suggestion and propagate it (lines 18 to 29 of Algorithm 1).

The initialization step starts collecting all concepts of ontology O (SCO) and O (SCO ) and then for each similarity metric (SimM) a set of mapping suggestions is found using the simple matching algorithm (line 5 of Algorithm 1). This algorithm treats the matching problem as a stable marriage problem with size list limited to 1 [START_REF] Gale | College admissions and the stability of marriage[END_REF][18], i.e., the algorithm only selects one mapping if similarity value between the two entities of the mapping is the highest considering all the mappings with at least one of these entities (Algorithm 2). At this moment only concept mappings, not property mappings, are chosen. The initial set of mapping suggestions is defined as the union of the mapping suggestions found for each similarity metric (lines 6 to 10 of Algorithm 1). The mappings in which their entity names are the same are placed in the alignment and removed from the set of mapping suggestions (lines 12 to 17 of Algorithm 1). Moreover, ALIN Attr inserts into the set of mapping suggestions attribute mappings associated with these concept mappings placed in the alignment (line 15 of Algorithm 1). The approach uses the structural attribute selection technique, which will be explained later, to choose the attribute mappings.

After defining the initial set of mapping suggestions and the initial alignment, ALIN Attr moves to the interactive step, in which the mapping suggestions receive the feedback of the expert (line 20 of Algorithm 1). If the expert accepts a mapping suggestion, then it is included in the alignment (line [START_REF] David | The alignment api 4.0. Semant[END_REF] end if 29: end while 30: return A 1). ALIN Attr simulates the expert feedback by accessing a reference alignment. Session 4 further explains the reference alignment.

Up to this point, as we use several similarity metrics and the set of mapping suggestions is the union of the formed sets made for each metric there may be mappings with one of the entities equal. Since we want to generate a one-to-one alignment, once one of these mappings is accepted, the others will be rejected and removed from the set of mapping suggestions (line [START_REF] Petrakis | Design and Evaluation of Semantic Similarity Measures for Concepts Stemming from the Same or Different Ontologies object instrumentality[END_REF] ALIN Attr would automatically reject these mappings, it would probably make mistakes.

At this point, the ALIN Attr approach uses the structural attribute selection technique which will try to select, based on expert feedback, the best attribute mappings to be included into the set of mapping suggestions. The assumption behind the structural attribute selection technique is that if the attributes in an attribute mapping are attributes of concepts of a concept mapping, then this attribute mapping is more likely to be correct. Algorithm 3 describes the structural attribute selection technique. It considers all attributes of the concepts of the input accepted mapping (lines 1 and 2 of Algorithm 3) and for each similarity metric it uses the simple matching algorithm to define attribute mapping suggestions. The output of the algorithm is the union of the set of attribute mappings found for each similarity metric. M ← Simple Matching Algorithm(SA,SA ,SimM);

5:
for each m(a, a ) ∈ M do

6:
if m(a, a ) ∈ SMS then end for 10: end for 11: return SMS Instead of selecting mappings between concepts of the two ontologies, like in the ALIN Attr top-level algorithm, the structural attribute selection technique (Algorithm 3) uses the simple matching algorithm (Algorithm 2) to select mappings between attributes of the concepts in an accepted mapping. The use of the simple matching algorithm proved to be efficient in choosing the attribute mappings to be inserted in the set of mapping suggestions, as will be shown later in this paper.

ALIN Attr was implemented in Java using the following Java APIs: Stanford coreNLP API [START_REF] Manning | The Stanford CoreNLP natural language processing toolkit[END_REF] with a routine to put a word in canonical form; Simmetrics API [START_REF] Surhone | SimMetrics[END_REF], with string-based similarity metrics; HESML API [START_REF] Lastra-Daz | [END_REF], with Wordnet [START_REF] Fellbaum | WordNet: An electronic lexical database[END_REF] based linguistic metrics; And the Alignment API [START_REF] David | The alignment api 4.0. Semant[END_REF], which contains routines for handling ontologies written in OWL. The most frequent synsets of words are used to calculate semantic similarities. To find this synset is used the WS4J API 3 .

Experimental Evaluation

In this section, we evaluate our approach for interactive ontology matching considering attribute mappings.

Configuration of the experiment

The evaluation is designed towards answering three research questions: RQ1: Does the consideration of attribute mappings improve the quality of the final alignment? RQ2: Does the use of expert feedback for the inclusion of attribute mappings in the set of mapping suggestions improve the quality of the final alignment? RQ3: Does the simple matching algorithm between the attributes of the concepts improve the quality of the final alignment?

The quality of an alignment is generally measured by F-measure, which is the harmonic mean between recall and precision. In an interactive approach another quality metric should be taken into account, the number of interactions with the expert that was necessary to achieve the alignment. The lower the number of interactions, the better. Thus, the two quality metrics were used to answer the research questions in this work. for each a in ∈ SA do add m(a, a ) to SMS;

Algorithm 4 Attribute Inclusion

6:
end for 7: end for 8: return SMS Towards answering these questions, some variations of ALIN Attr were considered:

• ALIN W Attr : This variation didn't take into account attribute mappings, i.e., only concept mappings compose the set of mapping suggestions. For that, the ALIN W Attr variation removes the calls for the structural attribute selection technique (Algorithm 3) in line 15 and from line 25 to line 27 of the ALIN Attr top-level algorithm (Algorithm 1). OAEI provides several data sets, which are sets of ontologies, to be used in the evaluation of ontology matching tools. From the data sets provided by OAEI, the only one that contained documentation of attributes and that had size that allowed the execution of ALIN Attr is the conference data set. Therefore, the conference data set was used to evaluate the approach. OAEI provides reference alignments, which are alignments that contains the mappings that are believed to be correct, between the pairs of the ontologies of the conference data set. In the ALIN Attr approach, a reference alignment query simulates the consult to the expert. The selection of the similarity metrics was based on two criteria: available implementations and the result of these metrics in assessments, such as those carried out in [START_REF] Petrakis | Design and Evaluation of Semantic Similarity Measures for Concepts Stemming from the Same or Different Ontologies object instrumentality[END_REF] and [START_REF] Cheatham | String similarity metrics for ontology alignment[END_REF]. Based on [START_REF] Petrakis | Design and Evaluation of Semantic Similarity Measures for Concepts Stemming from the Same or Different Ontologies object instrumentality[END_REF] and [START_REF] Cheatham | String similarity metrics for ontology alignment[END_REF], ALIN Attr uses Jaccard, Jaro-Wrinkler and n-gram string-based metrics and the Resnick, Jiang-Conrath and Lin linguistic metrics. Resnick, Jiang-Conrath and Lin are metrics that require a taxonomy to be computed [START_REF] Petrakis | Design and Evaluation of Semantic Similarity Measures for Concepts Stemming from the Same or Different Ontologies object instrumentality[END_REF], this taxonomy being provided, in this algorithm, by Wordnet [START_REF] Fellbaum | WordNet: An electronic lexical database[END_REF].

Results

The results in terms of number of interactions (NI), precision, recall and F-measure can be seen in Table 1. In each interaction with the expert, up to three mapping suggestions can be presented, since each mapping suggestion has one entity in common with another mapping suggestion of the interaction [START_REF] Faria | Using the SEALS Client's Oracle in Interactive Matching[END_REF].

Comparing ALIN W Attr with the other three approaches, that considered attributes mappings, we can see the improvement in the recall, which was expected since other mappings were evaluated. It is also possible to notice an increase in the number of interactions with the expert. Therefore, the inclusion of attribute mappings without taking into account the expert feedback generates an increase in the F-measure, but also an increase in the number of interactions with the expert leading to an inconclusive answer to the RQ1 question.

Comparing ALIN AttrAuto , which did not take into account the feedback of the expert, with ALIN AttrF Back and ALIN Attr , which considered it, we can observe an improvement in the F-measure and a decrease in the number of interactions with the expert. This demonstrates that using expert feedback is a good practice, answering positively RQ2. It is important to note that it was assumed that the expert did not make mistakes. Therefore, these results are valid when the expert makes no mistakes.

Addressing RQ3, i.e., comparing ALIN Attr with ALIN AttrF Back towards evaluating the benefit of reducing the number attribute mappings by using the simple matching algorithm, we observed a decrease in the number of interactions with almost no loss of quality of the alignment, what answer positively to the RQ3 question. OAEI annually provides a comparison between ontology matching tool performances, and one ontology group used is the conference dataset, used in this paper [START_REF] Achichi | Results of the Ontology Alignment Evaluation Initiative[END_REF]. Table 2 depicts a comparison between some the tools that participated in the OAEI 2017 interactive conference track and ALIN Attr and ALIN Attr+Syn .

Comparison between tools that participated in the OAEI interactive conference track

The tools AML, LogMap, and XMAP (Table 2) are interactive ontology matching tools. This tools, like ALIN Attr , include attribute mappings in the generated alignment but this inclusion is done in a non-interactive way, not taking into account the expert feedback.

The Table 2 depicts results with the expert hitting 100% of the answers. The results showed that ALIN Attr generated a high level result when running the conference data set when the expert hit 100% of the answers, but with a very large number of interactions when compared to the other tools.

To verify the quality of ALIN Attr if it uses a number of interactions more compatible with the other tools, two techniques, described in [START_REF] Da Silva | Semantic interactive ontology matching: Synergistic combination of techniques to improve the set of candidate correspondences[END_REF], were added to ALIN Attr . In [START_REF] Da Silva | Semantic interactive ontology matching: Synergistic combination of techniques to improve the set of candidate correspondences[END_REF], these techniques proved to be very efficient in reducing the number of interactions without significantly reducing quality. The inclusion of the two techniques generates the results shown on line 'ALIN Attr+Syn ' of Table 2 and shows that, as the quality as the number of interactions, ALIN Attr+Syn is good when compared to other tools.

Conclusion

Ontology matching is a necessary step for establishing interoperation among semantic web applications. Its purpose is to discover mappings between the entities of at least two ontologies. The quality of an alignment generated by a matching approach is generally measured by F-measure, which is the harmonic means between recall and precision. Another quality metric, when the ontology matching process is interactive, is the number of interactions with the expert.

An important step in the process of interactive ontology matching is the definition of the set of mapping suggestions, that is, the set of mappings that will be shown to the expert. The problem seen in this paper is how to efficiently include attribute mappings into the set of mapping suggestions. The ALIN Attr approach includes attribute mappings taking advantage of the expert feedback, of the structures of the involved ontologies, as well as the use of the simple matching algorithm. Experimental results showed the benefit of the approach when assuming that the expert does not make mistakes.

In addition, the quality of the alignment provided by ALIN Attr was compared to state of the art tools that have participated in the track of interactive ontology matching in OAEI 2017. The results obtained show that ALIN Attr generates an alignment with a good quality in comparison to other tools, with regard to precision, recall and F-measure, when the expert never makes mistakes, but with a number of interactions far superior to other tools. When performed with techniques to decrease the number of interactions, the number of interactions was compatible with that of the other tools, preserving a good quality.

As future work, one interesting direction is to explore how to reduce the negative effects of expert mistakes. The ALIN Attr generates good results when the expert does not make mistakes, but because the approach uses the expert feedback as the input of the structural attribute selection technique, probably incorrect attribute mappings will be generated when the expert makes a mistake.

20 :

 20 receive expert feedback on m(e, e );21:remove m(e, e ) from SMS; 22: if m(e, e ) is accepted then 23: add m(e, e ) to A; 24: SMS ← Remove Mappings with Equal Entities(SMS,m(e, e )); 25: if m(e, e ) is a concept mapping then 26: SMS ← Structural Attribute Selection Technique(m(e, e ),SoM);

Algorithm 3

 3 Structural Attribute Selection Technique Input: m(c, c ),SoM Output: SMS 1: SA ← all attributes of c; 2: SA ← all attributes of c ; 3: for each SimM ∈ SoM do 4:

  of Algorithm Algorithm 1 ALIN Attr Top-level Algorithm Input: O, O , SoM Output: A /*Initialization step*/ 1: A = ∅; SMS = ∅; 2: SCO ← all concepts of O; 3: SCO ← all concepts of O ; 4: for each SimM ∈ SoM do

	5:	M ← Simple Matching Algorithm(SCO,SCO ,SimM);
	6:	for each m(e, e ) ∈ M do
	7:	if m(e, e ) ∈ SMS then
	8:	add m(e, e ) to SMS;
	9:	end if
	10:	end for
	11: end for
	12: for each m(e, e ) ∈ SMS do
	13:	if name of e = name of e then
	14:	move m(e, e ) from SMS to A;
	16:	end if
	17: end for
		/*Interactive step*/

15: SMS ← Structural Attribute Selection Technique(m(e, e ),SoM); 18: while SMS = ∅ do 19:

select m(e, e ) ∈ SMS with the biggest sum of similarity metrics;

  of Algorithm 1) It is worth noting that ALIN Attr uses expert feedback to reject these mappings. If

	Algorithm 2 Simple Matching Algorithm
	Input: SE, SE , SimM
	Output: M
	1: for each e ∈ SE do
	2:	max e ← max e ∈SE	SimM (e, e );
	3:	max e ← max e ∈SE	SimM (e , max e );
	4:	if e = max e then
	5:	add m(e, max e ) to M;
	6:	end if
	7: end for
	8: return M;

  Technique for ALIN AttrAuto

	Input: O, O , SoM
	Output: SMS
	1: SA ← all attributes of O;
	2: SA ← all attributes of O ;
	3: for SimM ∈ SoM do
	4:	M ← Simple Matching Algorithm(SA,SA ,SimM);
	5:	for each m(e, e ) ∈ M do
	6:	if m(e, e ) ∈ SMS then
	7:	add m(e, e ) to SMS;
	8:	end if
	9:	end for
	10: end for
	11: return SMS
	Algorithm 5 Structural Attribute Selection Technique for ALIN AttrF Back
	Input: m(c, c ),SoM
	Output: SMS

1: SA ← all attributes of c; 2: SA ← all attributes of c'; 3: for each a ∈ SA do 4:

  • ALIN AttrAuto : This variation includes the attribute mappings only in the initialization step, i.e., not considering expert feedback. For that, the ALIN AttrAuto variation removes the calls for the structural attribute selection technique (Algorithm 3) in line 15 and from line 25 to line 27 in the ALIN Attr top-level algorithm (Algorithm 1) and includes a call for attribute inclusion technique for ALIN AttrAuto (Algorithm 4) in the ALIN Attr top-level algorithm (Algorithm 1) after line 17.• ALIN AttrF Back : This variation includes all attribute mappings related to the accepted concept mapping into the set of mapping suggestions, i.e., this variation doesn't use the simple matching algorithm (Algorithm 2) to reduce the number of included attribute mappings. For that, the ALIN AttrAuto variation makes a call to the structural attribute selection technique for ALIN AttrF Back (Algorithm 5) instead of a call to the structural attribute selection technique (Algorithm 3) in lines 15 and 26 of the ALIN Attr top-level algorithm (Algorithm 1).

Table 1 .

 1 Comparison between different ALINAttr variations executions with Conference Data Set

		Total of questions NI Precision F-measure Recall
	ALIN W Attr	1183	582 0.921	0.783	0.692
	ALIN AttrAuto	1574	739 0.905	0.809	0.741
	ALIN AttrF Back	1321	631 0.924	0.817	0.741
	ALIN Attr	1242	614 0.924	0.815	0.738

Table 2 .

 2 Comparison between some the tools of OAEI 2017 Conference Data Set Interactive Tracking and ALINAttr and ALINAttr+Syn with 100% hit rate

		Number of questions NI Precision F-measure Recall
	ALIN Attr	1242	614 0.924	0.815	0.738
	AML [14][27]	270	271 0.912	0.799	0.711
	LogMap [15][28]	142	82 0.886	0.723	0.610
	XMap [29][30]	4	4	0.837	0.678	0.57
	ALIN Attr+Syn	443	205 0.918	0.782	0.692

Acknowledgement

The second author was partially funding by project PQ-UNIRIO N o 01/2017 ("Aprendendo, adaptando e alinhando ontologias:metodologias e algoritmos.") and CAPES/PROAP. The fourth author was partially funding by 'CNPq Special visiting researcher grant (314782/2014-1)'.