# Improved Algorithms for Online Rent Minimization Problem Under Unit-Size
Jobs

Enze Sun The University of Hong Kong. Email<EMAIL_ADDRESS>Zonghan
Yang Shanghai Jiao Tong University. Email<EMAIL_ADDRESS>Yuhao Zhang
Shanghai Jiao Tong University. Email<EMAIL_ADDRESS>
###### Abstract

We consider the Online Rent Minimization problem, where online jobs with
release times, deadlines, and processing times must be scheduled on machines
that can be rented for a fixed length period of $T$. The objective is to
minimize the number of machine rents. This problem generalizes the Online
Machine Minimization problem where machines can be rented for an infinite
period, and both problems have an asymptotically optimal competitive ratio of
$O(\log(p_{\max}/p_{\min}))$ for general processing times, where $p_{\max}$
and $p_{\min}$ are the maximum and minimum processing times respectively.
However, for small values of $p_{\max}/p_{\min}$, a better competitive ratio
can be achieved by assuming unit-size jobs. Under this assumption, Devanur et
al. (2014) gave an optimal $e$-competitive algorithm for Online Machine
Minimization, and Chen and Zhang (2022) gave a $(3e+7)\approx
15.16$-competitive algorithm for Online Rent Minimization. In this paper, we
significantly improve the competitive ratio of the Online Rent Minimization
problem under unit size to $6$, by using a clean oracle-based online algorithm
framework.

##  1 Introduction

_Machine Minimization_ is a classical scheduling problem in combinatorial
optimization. We are given $n$ jobs with release time and deadline to
schedule. Each job $j$ has a length $p_{j}$ and must be assigned to a machine
for $p_{j}$ units of time between its release time $r_{j}$ and its deadline
$d_{j}$. However, in many practical scenarios, such as cloud computing, we may
not need to buy the machines but only rent them for a fixed period of time.
This motivates the _Rent Minimization_ problem, introduced by Saha [12]. In
this problem, we are given a constant $T$, which represents the duration of a
machine rent. The goal is to minimize the number of rents we make to process
all jobs within their deadlines.

Another related formulation, inspired by nuclear weapon testing, is the
_Calibration_ problem, proposed by Bender et al. [3]. In this problem, we are
given $m$ machines and a set of jobs that must be completed feasibly. However,
before using a machine, we need to _calibrate_ it. Each calibration, similar
to a rent, activates the machine for a time period of $T$. The goal is to
minimize the number of calibrations to process all jobs on time. The main
difference between the Calibration and the Rent Minimization problems is that
the former restricts us to have at most $m$ machines working in parallel at
any given time, while the latter does not have such a constraint. Therefore,
the Rent Minimization problem can be regarded as a special case of the
Calibration problem when $m=\infty$.

On the other hand, in the cloud rental scenario and many other practical
applications, the computing requests usually increase over time and can be
modeled as online released jobs. Therefore, we investigate the problem in an
online setting. We do not have any prior knowledge about the jobs before their
release time, and need to schedule jobs and rent machines online and
irrevocably over time. The goal is to minimize the total number of _rents_ for
scheduling all jobs. Note that the online generalization is also studied in
the Calibration problem by Chen and Zhang [5]. To ensure that online
algorithms can schedule all jobs, they also assume $m=\infty$ in their model,
which coincides with the Online Rent Minimization model.

#### Why consider unit-size jobs?

Saha [12] proposes an $O(\log{(p_{\max}/p_{\min})})$-competitive algorithm for
the Online Machine Minimization problem. By paying a constant factor, it can
be extended to an $O(\log{(p_{\max}/p_{\min}))}$-competitive algorithm for the
Online Rent Minimization problem. ($p_{\max}$ and $p_{\min}$ are the longest
and shortest processing time among all jobs.), which was proved to be the best
competitive ratio asymptotically. However, in many real-world applications,
one company usually receives similar length requests, so the ratio between
$p_{\max}$ and $p_{\min}$ may not be too large; and it is worthwhile to reduce
the constant factor of the ratio when $p_{\max}/p_{\min}$ is small. To this
end, we focus on the special case of unit-size jobs (i.e., all $p_{j}=1$).
Note that by partitioning jobs by their length into $\log(p_{\max}/p_{\min})$
groups, the $\alpha$-competitive unit-size algorithm can be extended to a
roughly $(3\alpha\log{(p_{\max}/p_{\min})})$-competitive algorithm in the
general case.

The unit-size special case has also been considered in the Online Machine
Minimization problem [5, 8, 10]. Devanur et al. [8] present an $e$-competitive
algorithm for the Online Machine Minimization problem under unit-size jobs
(though earlier work by Bansal et al. [2] implies the same result), and it is
the optimal ratio among all deterministic algorithms. Current best lower bound
of the online renting problem under unit-size jobs is also $e$ since it is a
generalized model. On the positive side, Chen and Zhang [5] study the online
renting problem under unit-size jobs. They improve the implicit constant ratio
by Saha [12] to $3e+7\approx 15.16$. In their algorithm, jobs are
distinguished by whether they are long or short based on the length of their
time window (i.e., $d_{j}-r_{j}$) and are handled separately. Our paper
significantly improves the competitive ratio to $6$ with a cleaner oracle-
based algorithm without identifying whether jobs are short or long.

######  Theorem 1.

There exists an efficient $6$-competitive algorithm for the online renting
problems under unit-size jobs.

#### Our techniques.

In the work of Chen and Zhang [5], they rent machines for long and short jobs
separately; as a result, their final competitive ratio is the sum of two
cases, which makes the ratio large. The technical reason behind this result is
that they use the $e$-competitive Online Machine Minimization algorithm by
Devanur et al. [8] as a black box, which is only suitable for _short_ jobs.
(Roughly speaking, it is because we can view $T=\infty$ when jobs are short.)
Therefore, they must use another approach to handle long jobs.

In our paper, we formalize and extend the Online Machine Minimization
algorithm to an oracle-based framework, instead of using the algorithm as a
black box. The oracle-based framework uses an offline algorithm to guide our
online decision. Note that the Online Machine Minimization algorithm also uses
an efficient offline optimal algorithm as an oracle. However, we do not know a
polynomial offline Rent Minimization algorithm for unit-size jobs. The main
algorithmic novelty is that we find an efficient substitute for the optimal
algorithm to act as a bridge between online decisions and the optimal offline
solution. The oracle is a kind of optimal augmentation algorithm. It is
allowed to use a rent length of $3T$, and the rent number is at most OPT with
rent length $T$. It also satisfies some online monotone properties so that we
can control the cost of the online algorithm. Finally, we prove that by
following the offline oracle and paying a factor of $6$ online, we can recover
the same ability for scheduling jobs as the offline oracle. This concludes the
competitive ratio of $6$.

#### Extension to the model with delay.

Chen and Zhang [5] also raise a perspective that the operation _rent_ (a.k.a.
_calibration_ in their paper) needs a non-negative time $\lambda$ to finish.
We call it _Online Rent Minimization with Delay_. They propose an
$\left(3(e+1)\lambda+3e+7\right)\approx(11.15\lambda+15.16)$-competitive
algorithm. We use a black box reduction to extend the algorithm in Theorem 1
and improve the ratio to $6(\lambda+1)$.

######  Theorem 2.

As a corollary of Theorem 1, there exists an efficient
$6(\lambda+1)$-competitive algorithm when we need $\lambda$ time to finish
each rent.

#### Other related works.

Offline Machine Minimization is a well-studied and classic model. Garey and
Johnson [9] shows that it is NP-hard. On the algorithm side, Raghavan and
Thompson [11] propose an $O(\frac{\log n}{\log\log n})$-approximation
algorithm. Later, the ratio has been improved to $O(\sqrt{\frac{\log
n}{\log\log n})}$ by Chuzhoy et al. [6]. Whether there exists a constant
approximation ratio is still open. Moreover, several special cases are also
discussed. Cieliebak et al. [7] focus on the case that each job’s active time
$(d_{j}-r_{j})$ is small. Yu and Zhang [13] achieve a ratio of 2 in the equal
release time case and a ratio of 6 in the equal processing time case.

Scheduling to minimize the number of calibrations is proposed by Bender et al.
[3]. The general case is NP-hard even for checking feasibility. Under unit-
size jobs, Bender et al. give a $2$-approximation algorithm; later, Chen et
al. [4] give the first PTAS algorithm. However, it is worth noting that
whether the unit-size special case is polynomially solvable is still open.
Moreover, Angel et al. [1] introduce the concept of delay, which means that
each calibration requires $\lambda$ time to finish. They study the delay
setting on the one-machine special case of the offline calibration problem and
show that it is polynomially solvable.

##  2 Preliminaries

We first define the models and introduce the basic notations.

#### Rent Minimization.

We have a set of jobs $\mathcal{J}=\\{1,\cdots,n\\}$ and a fixed rent length
$T$. For job $j\in\mathcal{J}$, it has a release time $r_{j}$, a deadline
$d_{j}$, and a unit processing time $p_{j}=1$. Each job should be assigned to
one active machine at an integer time unit $[t,t+1)$, where $t$ is an integer
such that $r_{j}\leq t\leq d_{j}-1$. We can rent a machine at any integer time
point $t$. Then we will have an active machine during $[t,t+T)$. The objective
is to minimize the number of machine rents to process all jobs in
$\mathcal{J}$.

#### Online Rent Minimization.

In the online version, all jobs are released online, and they become _visible_
at their release time. On the other hand, we need to make rent decisions and
assign jobs online irrevocably. In particular, at an integer time point $t$,
we have:

  * •

Jobs with release time equal to $t$ become visible.

  * •

We can decide to rent a machine at $t$ or any time after that.

  * •

We can schedule jobs on active machines during the time unit $[t,t+1)$
irrevocably.

#### Notations on Rent Set.

We use a multiset
$I=\\{[s_{1},c_{1}),[s_{2},c_{2}),\cdots[s_{i},c_{i}),\cdots\\}$ to denote a
set of rents, where the $i$-th rent interval starts at $s_{i}$ and is active
in $[s_{i},c_{i})$. Note that $c_{i}$ always equals $s_{i}+T$ when the rent
length is $T$; however, we use the general notation for future reference.

Focusing on the time unit $[t,t+1)$, the number of _active units_ $A_{I}(t)$
is defined as the number of active machines at time $t$, which means that we
can schedule at most $A_{I}(t)$ jobs at time $t$. For a given rent set $I$, we
have $A_{I}(t)=\left|\left\\{[s_{i},c_{i})\in
I\;\middle|\;t\in[s_{i},c_{i})\right\\}\right|.$ We also extend the notation
for intervals, such that $A_{I}(r^{*},d^{*})=\sum_{t=r^{*}}^{d^{*}-1}A_{I}(t)$
is the number of active units during the time interval $[r^{*},d^{*})$.

#### Feasibility of Rent Set.

We call a rent set $I$ _feasible_ for $J$, if we can schedule all jobs in $J$
on $I$. We introduce a lemma based on Hall’s Theorem to check whether $I$ is
feasible.

For a given jobs set $J$, we define $J(r^{*},d^{*})=\left\\{j\in J|r^{*}\leq
r_{j}<d_{j}\leq d^{*}\right\\}$ to represent the jobs that must be assigned
inside the interval $[r^{*},d^{*})$.

######  Lemma 3 (Feasibility).

$I$ is feasible for $J$ iff. $\forall r^{*}\leq
d^{*}\in\mathbb{N},~{}A_{I}(r^{*},d^{*})\geq|J(r^{*},d^{*})|~{}.$

###### Proof.

For any fixed $r^{*}$ and $d^{*}$, the sum of active units provided by $I$ is
$A_{I}(r^{*},d^{*})$. Each job released and due between this period must be
scheduled on these time slots. If there exists a pair of $r^{*}$ and $d^{*}$
such that $A_{I}(r^{*},d^{*})<|J(r^{*},d^{*})|$, there is no feasible
assignment because of the pigeonhole principle. On the other hand, if the
inequality holds for all $r^{*}$ and $d^{*}$, we can view it as a bipartite
matching between jobs and active units. There is a feasible assignment by
Hall’s Theorem. ∎

#### An Efficient Checker and Scheduler: Earliest Deadline First (EDF).

Earliest Deadline First is a greedy algorithm that can find a feasible
assignment for $J$ on $I$ if and only if $I$ is feasible for $J$. When we call
$\textup{\sf EDF}(J,I)$, we scan time units from early to late, and assign the
released job with the earliest deadline to a free active machine at the
current time unit. If a job with deadline $d$ cannot find a free active
machine at the time unit $[d-1,d)$, $\textup{\sf EDF}(J,I)$ fails, and we call
$d$ the _fail time_ of $\textup{\sf EDF}(J,I)$. Otherwise, $\textup{\sf
EDF}(J,I)$ succeeds. Bender et al. [3] has already proved that EDF can check
the feasibility. It is also worth noting that EDF can be efficiently
implemented in $O(n\log n)$ by using a heap, instead of going through all
integer time points directly.

######  Lemma 4 ([3]).

$\textup{\sf EDF}(J,I)$ succeeds, i.e., it can find a feasible schedule for
$J$ on $I$, if and only if $I$ is feasible for $J$.

#### Using EDF online.

Note that we only make comparisons between released jobs. Therefore, the EDF
algorithm can be simulated online : we only need to find a feasible rent set
$I$, and then EDF can automatically find a feasible assignment online.

##  3 Oracle-based Online Algorithm Framework

Moving towards online algorithms, one natural way is to use an offline
algorithm as an _oracle_ to suggest the actions of online algorithms. We keep
track of this offline algorithm and make corresponding online decisions when
the offline algorithm changes along with the online jobs release. Whenever the
offline algorithm increases by one at the moment $t$ because of the change of
the job set, the online algorithm performs one Batch-Rent at this time $t$,
which is a fixed rent scheme that contains $\Gamma$ machines. Intuitively, we
use these $\Gamma$ machines to catch up with the one increment of the offline
oracle. It is worth noting that the $e$-competitive algorithm for Online
Machine Minimization follows this approach [8].

In our case, compared to Machine Minimization, we have two main differences in
our oracle-based framework. The first difference is the job set we input to
the oracle. Because of the online fashion, the most natural way is to input
the set of all released jobs to the oracle. In Machine Minimization, it works
because $T=\infty$ and earlier rents are always more powerful; however, this
is not true in Rent Minimization. Indeed, too early rents may cause trouble in
Rent Minimization. Intuitively, we are only allowed to make online rent when
the offline oracle reports an increment if we want to bound the competitive
ratio in the framework. Consider the case where $T=10$ and two jobs will be
due at $100$ with release time $0$ and $90$. If we report the first job to the
offline oracle at $0$, the offline oracle will return one new rent interval.
Following the oracle-based framework, we will make $\Gamma$ online rent
intervals at $0$. However, we still need to make more rent intervals at $90$,
while the offline oracle may not increase. To this end, we use the job set
$J_{t}$ as the job set we input to the oracle at time $t$. A job $j$ is in
$J_{t}$ if it satisfies the following two properties:

  1. 1)

It is _visible_ at $t$, i.e., $r_{j}\leq t$.

  2. 2)

It is _emergent_ at (or before) $t$, i.e., $d_{j}\leq t+T$.

Another difference is an augmentation factor $\alpha$. The oracle is allowed
to have $\alpha T$ active time for each rent. Since the existence of a
polynomial time optimal offline algorithm for Rent Minimization is still
unknown, this factor allows us to find an efficient substitute. We use
$\textup{\sf Oracle}_{\alpha}(J,T)$ (instead of $\textup{\sf Oracle}(J,\alpha
T)$, since the target rent length is still $T$) to denote an oracle with
augmentation factor $\alpha$. The framework is formalized in Algorithm 1.

Algorithm 1 Oracle-based Online Algorithm Framework

procedure OracleBasedOnline($t$: time, $J$: known jobs, $T$: length of rent)

$\Delta_{t}=|\textup{\sf Oracle}_{\alpha}(J_{t},T)|-|\textup{\sf
Oracle}_{\alpha}(J_{t-1},T)|$ $\triangleright$ $\alpha$ is a positive integer

Perform $\Delta_{t}$(if $\Delta_{t}>0$) Batch-Rent operations at $t$,
consisting of $\Gamma$ machines that start at or after $t$.

schedule jobs at $t$ following $\textup{\sf EDF}(J,I)$, where $I$ is the
current online rent set.

end procedure

Then, we discuss how this framework helps us control the number of rents made
by the online algorithm. First, as a substitute for the optimal offline
algorithm, $\textup{\sf Oracle}_{\alpha}$ needs to maintain some properties
similar to those of the optimal offline algorithm. Second, Batch-Rent should
support the online algorithm to be as powerful as the offline oracle in
scheduling all released jobs. We integrate and formalize these messages in the
following lemma.

######  Lemma 5.

Let $\textup{\sf OPT}(J,T)$ be the number of rents used by the optimal offline
algorithm to schedule the job set $J$, Algorithm 1 is $\Gamma$-competitive if
these three properties are guaranteed:

  1. 1)

For any job set $J$, $|\textup{\sf Oracle}_{\alpha}(J,T)|\leq\textup{\sf
OPT}(J,T)$;

  2. 2)

The offline oracle is online monotone: $|\textup{\sf
Oracle}_{\alpha}(J_{t_{1}},T)|\leq|\textup{\sf Oracle}_{\alpha}(J_{t_{2}},T)|$
if $t_{1}\leq t_{2}$;

  3. 3)

Algorithm 1 is feasible for scheduling all online released jobs.

###### Proof.

The online algorithm makes $\sum_{\Delta_{t}>0}\Delta_{t}$ rent batches, which
is exactly $|\textup{\sf Oracle}_{\alpha}(\mathcal{J},T)|$ by property 2) and
is not greater than $|\textup{\sf OPT}(\mathcal{J},T)|$ by property 1). Also,
the output satisfies the feasibility requirement by property 3). Therefore,
Algorithm 1 is $\Gamma$-competitive. ∎

#### The $e$-competitive algorithm for Online Machine Minimization.

We can use the framework to understand the $e$-competitive Online Machine
Minimization algorithm.

  * •

Oracle is the optimal offline algorithm, and we set $\alpha=1$. The
monotonicity directly comes from optimality.

  * •

$J_{t}$ is the set of visible jobs at $t$ because all jobs are emergent.

  * •

Each Batch-Rent contains $e$ new machines in average; for simplicity, we omit
any rounding issues related to $e$.

#### Choice of the oracle.

Recall that we do not have an efficient optimal algorithm for Rent
Minimization currently. It remains to find a suitable substitute that also
uses a small number of rents (property 1). One candidate algorithm may be the
Lazy-Binning algorithm by Bender et al. [3], which requires an augmentation
factor of $2$ to satisfy property 1). However, Lazy-Binning algorithm, as well
as other relatively simple 2 approximation algorithms we come up with, cannot
guarantee monotonicity. This will make us fail to bound the competitive ratio
of the online algorithm. In the next section, we introduce our oracle with an
augmentation factor of $3$, called the semi-online algorithm, which provides
all the properties we need in Lemma 5.

##  4 The Semi-Online Algorithm

In this section, we introduce the semi-online algorithm shown as Algorithm 2,
which uses an augmentation factor of $3$ and acts as the $\textup{\sf
Oracle}_{3}$ in our framework.

Algorithm 2 The Semi-Online Algorithm

procedure SemiOnline($J$: input job set, $T$: length of rent)

$J^{\prime},I\leftarrow\varnothing$ $\triangleright$ $I$ is a multiset for
rents.

$\tau_{j}=\max\\{r_{j},d_{j}-T\\}$ for all $j$.

for $j\in J$ in non-decreasing order of $\tau_{j}$ do

$J^{\prime}\leftarrow J^{\prime}\cup\\{j\\}$

if $\textsf{EDF}(J^{\prime},I)$ fails then

$I\leftarrow I\cup\left\\{\left[\tau_{j}-T,\tau_{j}+2T\right)\right\\}$
$\triangleright$ A rent that starts at $\tau_{j}-T$ with length $3T$.

end if

end for

return $I$

end procedure

We call Algorithm 2 semi-online, because the enumerating order is exactly the
same as how $J_{t}$ increases in the oracle-based framework. Thus, if we have
some new jobs with $r_{j}=t$ or $d_{j}-T=t$ when the online time moves from
$t-1$ to $t$, the only possible difference between $\textup{\sf
SemiOnline}(J_{t-1},T)$ and $\textup{\sf SemiOnline}(J_{t},T)$ is some rent
intervals of $[t-T,t+2T)$. This observation could be formalized into the
following properties of the semi-online algorithm.

######  Lemma 6 (Strong Monotonicity).

We have the following two properties for Algorithm 2.

  1. 1.

For any $J_{t_{1}}$ and $J_{t_{2}}$ where $t_{1}\leq t_{2}$, we have
$\textup{\sf SemiOnline}(J_{t_{1}},T)\subseteq\textup{\sf
SemiOnline}(J_{t_{2}},T).$

  2. 2.

$\textup{\sf SemiOnline}(J_{t},T)\setminus\textup{\sf SemiOnline}(J_{t-1},T)$
is a multiset of a fixed rent interval $[t-T,t+2T)$.

###### Proof.

Intuitively, the reason behind the lemma is that the order of $\tau_{j}$ is
the same as the order in which we insert jobs into $J_{t}$ as $t$ increases.
Formally speaking, compare $J_{t_{1}}$ and $J_{t_{2}}$ and consider a job
$j\in J_{t_{2}}\setminus J_{t_{1}}$. By definition, we have that
$\tau_{j}\geq\displaystyle\max_{j^{\prime}\in J_{t_{1}}}\tau_{j^{\prime}}$.
Therefore, Algorithm 2 first enumerates the jobs in $J_{t_{1}}$ and then the
jobs in $J_{t_{2}}\setminus J_{t_{1}}$, which concludes the first property
immediately. For the second property, the reason is that $J_{t}\setminus
J_{t-1}$ is a set of jobs with $r_{j}=t$ or $d_{j}-T=t$. In other words, we
enumerate them after jobs in $J_{t-1}$. Thus, if $I$ continues to grow when we
enumerate them, the new interval must be $[t-T,t+2T)$. ∎

The strong monotonicity in Lemma 6 suffices to show the weak monotonicity in
property 2) of Lemma 5. On the other hand, these two properties are also used
in the proof of property 3) later. It remains to prove property 1) by bounding
the cardinality of the semi-online algorithm’s solution.

######  Lemma 7.

$|\textup{\sf SemiOnline}(J,T)|\leq\textup{\sf OPT}(J,T)$, and $\textup{\sf
SemiOnline}(J,T)$ is feasible for $J$.

Before proving Lemma 7, we introduce coOPT so that we can better understand
the solution structure.

######  Definition 8 (Optimal complement solution).

For a job set $J$, rent length $T$, and a given rent set $I$ (which may not be
length $T$), the optimal complement solution of $I$, denoted as $\textup{\sf
coOPT}(I)$, is defined as a rent set of length $T$ with minimum cardinality
such that $I\cup\textup{\sf coOPT}(I)$ is feasible for $J$.

######  Fact 9.

$\textup{\sf coOPT}(\varnothing)=\textup{\sf OPT},\textup{\sf
coOPT}(\textup{\sf OPT})=\varnothing.$

Consider a rent set $I$ that is infeasible for $J$. Below, we state the main
property of coOPT.

######  Lemma 10.

Let $d$ be the fail time of $\textup{\sf EDF}(J,I)$. There exists a
$\textup{\sf coOPT}(I)$ such that there is a rent interval
$[s,s+T)\in\textup{\sf coOPT}(I)$ that satisfies: $d-T\leq s<d.$

###### Proof.

We use coOPT as a shorthand for $\textup{\sf coOPT}(I)$ in this proof. Let
$[s,s+T)$ be the earliest interval in coOPT.

First, we show that $s<d$. Suppose, for a contradiction, that $s\geq d$. Let
$j$ be the job that fails in $\textup{\sf EDF}(J,I)$, where $J$ is a fixed
given job set. Then, $j$ has no more active units in coOPT, since all rent
intervals start at or after $d$. But this contradicts the definition of coOPT,
which is a feasible rent set for $J$.

Second, we show that $s\geq d-T$ can be true. If this is not true, we
construct a new rent set ${\textup{\sf coOPT}^{\prime}}=\textup{\sf
coOPT}\setminus\left\\{[s,s+T)\right\\}\cup\left\\{[d-T,d)\right\\}.$ That is,
we replace the rent interval at $s$ with another one at $d-T$. We claim that
$\textup{\sf coOPT}^{\prime}\cup I$ is also feasible for $J$. This means that
$\textup{\sf coOPT}^{\prime}$ is also a feasible coOPT, and
$[s^{\prime}=d-T,T)$ is a feasible rent interval that satisfies our desired
condition.

To prove our claim, we fix an arbitrary choice of $r^{*}\leq
d^{*}\in\mathbb{N}$, and we verify the condition in Lemma 3, i.e.,
$A_{I\cup\textup{\sf coOPT}^{\prime}}(r^{*},d^{*})\geq|J(r^{*},d^{*})|.$

We consider two cases:

  * •

Case 1: $d^{*}<d$. If the condition does not hold, we have
$A_{I}(r^{*},d^{*})\leq A_{I\cup\textup{\sf
coOPT}^{\prime}}(r^{*},d^{*})<J^{\prime}(r^{*},d^{*})$, which means that
$\textup{\sf EDF}(I,J^{\prime})$ must fail no later than $d^{*}$ since the
active units are not enough beforehand. This contradicts the definition of
$d$.

  * •

Case 2: $d^{*}\geq d$. The only difference between coOPT and $\textup{\sf
coOPT}^{\prime}$ is the contribution of active units by $[s,s+T)$ and
$[d-T,d)$. We prove that $[d-T,d)$ must provide at least as many active units
as $[s,s+T)$ does.

Figure 1: coOPT’ contributes at least as many active units as coOPT on
$[r^{*},d^{*})$ when $d^{*}\geq d$.

Referring to Figure 1, we see that $[d-T,d)$ has more active units than
$[s,s+T)$ in $[s+T,d)$, and vice versa in $[s,d-T)$. Since $d^{*}\geq d$, we
need $r^{*}\leq d-T$ to reach the advantage area of coOPT; however,
$[r^{*},d^{*})$ then covers the whole part of $[d-T,d)$. This implies that the
total contribution of coOPT never exceeds that of $\textup{\sf
coOPT}^{\prime}$.

The discussion concludes the claim.

∎

######  Lemma 11.

At the end of each iteration of $j$, $I$ is feasible for $J^{\prime}$.

###### Proof.

We prove it by induction. In the base case, $I$ is feasible for $J^{\prime}$
when they are $\varnothing$. Then, assume the lemma is true after the
$(j-1)$-th iteration. At the $j$-th iteration, we add a job $j$ to
$J^{\prime}$. This means that $\forall r^{*}\leq r_{j},~{}d^{*}\geq d_{j}$,
$|J^{\prime}(r^{*},d^{*})|$ will increase by one. If $\textup{\sf
EDF}(J^{\prime},I)$ is already feasible, we are done. Otherwise, the algorithm
will employ a new $3T$ length rent interval $[\tau_{j}-T,\tau_{j}+2T)$. Notice
that $d^{*}\geq d_{j}\geq\tau_{j}$. Every $A_{I}(r^{*},d^{*})$ also increases
by at least one. Thus, we still have
$A_{I}(r^{*},d^{*})\geq|J^{\prime}(r^{*},d^{*})|$ after we employ
$[\tau_{j}-T,\tau_{j}+2T)$ (at the end of the $j$-th iteration). ∎

######  Corollary 12.

$\textup{\sf SemiOnline}(J,T)$ is feasible for $J$.

######  Lemma 13.

In the $j$-th iteration, if $\textup{\sf EDF}(J^{\prime},I)$ is infeasible in
Algorithm 2, before we rent $[t-T,t+2T)$, we have

$|\textup{\sf coOPT}(I\cup\left\\{[t-T,t+2T)\right\\})|\leq|\textup{\sf
coOPT}(I)|-1.$

###### Proof.

By the condition of the lemma and Lemma 11, we have $\textup{\sf
EDF}(J^{\prime},I)$ is infeasible while $\textup{\sf
EDF}(J^{\prime}\setminus\\{j\\},I)$ is feasible. By the enumerating order, all
the jobs $j^{\prime}$ in $J^{\prime}$ must satisfy
$\max\\{r_{j},d_{j^{\prime}}-T\\}\leq\tau_{j}$. Therefore, $\textup{\sf
EDF}(J^{\prime},I)$ must fail at a deadline $d\leq\tau_{j}+T$. On the other
hand, for all $j^{\prime}\in J$ such that $d_{j^{\prime}}<\tau_{j}$, we must
have $j^{\prime}\in J^{\prime}\setminus\\{j\\}$, also because of the
enumerating order. Thus, we can show that $d\geq\tau_{j}$. Otherwise,
$J^{\prime}\setminus\\{j\\}$ would be infeasible for $I$, which is a
contradiction. In conclusion, we show that the failure time $d$ of
$\textup{\sf EDF}(J^{\prime},I)$ satisfies $\tau_{j}\leq d<\tau_{j}+T.$

Finally, by Lemma 10, there exists a coOPT with rent interval $[s,s+T]$ such
that $d-T\leq s<d$. It implies that $\tau_{j}-T<s<\tau_{j}+T$. Therefore
$[s,s+T)$ is always a subset of $[\tau_{j}-T,\tau_{j}+2T)$. We have

$|\textup{\sf coOPT}(I\cup\left\\{[t-T,t+2T)\right\\})|\leq|\textup{\sf
coOPT}(I\cup\\{s\\})|=|\textup{\sf coOPT}(I)|-1.$

∎

###### Proof of Lemma 7.

Recall 9 that $\textup{\sf coOPT}(\varnothing)=\textup{\sf OPT}$. It follows
that $\sf{SemiOnline}$ rents at most OPT times as a corollary of Lemma 13. ∎

##  5 The 6-competitive Online Algorithm

It remains to define the rent scheme for each Batch-Rent in the framework. For
completeness, we formally describe the algorithm in Algorithm 3.

Algorithm 3 The Online algorithm

procedure OnlineRent($t$: time, $J$: known jobs, $T$: length of rent)

$\Delta=|{\sf SemiOnline}(J_{t},T)|-|{\sf SemiOnline}(J_{t-1},T)|$

Perform $\Delta$ Batch-Rent at time $t$, each consists of $6$ machines: $4$ at
$t$ and $2$ at $t+T$.

schedule jobs at $t$ following $\textup{\sf EDF}(J,I)$, where $I$ is the
current online rent set.

end procedure

Next, we prove the property 3) of Lemma 5 by our design of Batch-Rent, i.e.,
to show Algorithm 3 is feasible for the total job set $\mathcal{J}$. Combining
with the property 1) and 2) by the semi-online algorithm, we can conclude our
online algorithm is $6$-compeititve as claimed in Theorem 1.

First, we introduce an obvious relationship between online and semi-online
algorithms.

######  Fact 14.

At every moment $t$, there always exists a bijection from one semi-online rent
batch to one online rent batch, such that both batches are at the same time:
$4\times[t,t+T)+2\times[t+T,t+2T)\text{ in {\sf
Online}}\mapsto[t-T,t+2T)\text{ in {\sf SemiOnline}}$.

###### Proof.

This fact is directly implied by the second property of Lemma 6. Whenever
$\textup{\sf SemiOnline}(J_{t},T)$ increases from $\textup{\sf
SemiOnline}(J_{t-1},T)$ by some rent intervals of $[t-T,t+2T)$, the new
batches must be $4\times[t,t+T)+2\times[t+T,t+2T)$. Each of them can
correspond to one $[t-T,t+2T)$. ∎

We prove the feasibility by showing that the active units provided by the
online algorithm are always enough for the possible jobs inside any possible
interval $[r^{*},d^{*})$.

######  Lemma 15.

Let $I$ be the rent sets made by our algorithm. We have $\forall r^{*}\leq
d^{*}\in\mathbb{N},~{}A(r^{*},d^{*})\geq|\mathcal{J}(r^{*},d^{*})|$, where we
use $A$ to denote $A_{I}$ for simplicity.

We remark that Lemma 15 provides the necessary information to prove the
correctness via the feasibility lemma (Lemma 3). It only remains to complete
the proof of Lemma 15.

###  5.1 Proof of Lemma 15

Let us fix an arbitrary range $r^{*}\leq d^{*}$, and discuss $A(r^{*},d^{*})$
and $\mathcal{J}(r^{*},d^{*})$ separately. First, we discuss $A(r^{*},d^{*})$.
The behavior of the online algorithm can be represented by a set of online
rent batches. Note that only those rent batches that start in
$\left(r^{*}-2T,d^{*}\right)$ can provide active units inside
$\left[r^{*},d^{*}\right)$. Therefore, we only discuss a subset $B$ of all
rent batches with a start time in $\left(r^{*}-2T,d^{*}\right)$. Each $b$
means a Batch-Rent made by Algorithm 3. We use $t(b)$ to mean its decision
time. That is, a batch $b$ contains 4 rent intervals of $[t(b),t(b)+T)$, and 2
of $[t(b)+T,t(b)+2T)$.

We partition the time interval $[r^{*},d^{*})$ by several critical time
points. The first time point is
$\theta_{1}=\max\left\\{\left(\frac{r^{*}+d^{*}}{2}\right),d^{*}-T\right\\}.$
It means that $\theta_{1}=d^{*}-T$ when $d^{*}-r^{*}\geq 2T$ and
$\theta_{1}=\left(\frac{r^{*}+d^{*}}{2}\right)$ when $d^{*}-r^{*}<2T$. Remark
that in both cases, $\theta_{1}\geq d^{*}-T$. Then we recursively define
$\theta_{i+1}=\left(\frac{\theta_{i}+d^{*}}{2}\right)$ for every $i\geq 1$
until $\lfloor\theta_{i}\rfloor=d^{*}-1$. Besides, we let
$\theta_{0}=r^{*}-1$. For $i\geq 1$, we call
$\left[\left\lfloor\theta_{i-1}\right\rfloor+1,\left\lfloor\theta_{i}\right\rfloor\right]$
the $i$-th sub-interval, which is the minimal sub-interval of
$(\theta_{i-1},\theta_{i}]$ that contains all integers in it. We define
$B_{i}\subseteq B$ as the set of rent batches starting in the $i$-th sub-
interval. Moreover, we let $B_{0}$ be the set of rent batches starting in
$(r^{*}-2T,r^{*}]$.

For each $b\in B$, recall that $t(b)$ is the time it was allocated, and we let
$\lambda_{i}(b)$ be the length of the intersecting interval of
$[t(b),t(b)+2T)$ and
$\left[\left\lfloor\theta_{i-1}\right\rfloor+1,d^{*}\right)$. Note that
$\lambda_{1}(b)$ represents the intersecting interval with the whole
$\left[r^{*},d^{*}\right)$. Let
$L=\min\\{2T,d^{*}-r^{*}\\}=2(d^{*}-\theta_{1})$ denote the maximum possible
length in $\lambda_{1}$, and by our partition method. It follows the property
of the length of sub-intervals by our partition.

######  Lemma 16 (Partition length property).

For any batch $b\in B_{i}$ where $i\geq 1$, the intersection of
$\left[t(b),t(b)+2T\right)$ and
$[\left\lfloor\theta_{i-1}\right\rfloor+1,d^{*})$ satisfies: $2^{-i}\cdot
L\leq\lambda_{i}(b)\leq 2^{1-i}\cdot L.$

###### Proof.

For $i=1$, $\lambda_{1}(b)=\min\\{2T,d^{*}-t(b)\\}$. By definition, $r^{*}\leq
t(b)\leq\lfloor\theta_{1}\rfloor$, hence

$L/2=\min\\{T,d^{*}-\theta_{1}\\}\leq\min\\{2T,d^{*}-t(b)\\}\leq\min\\{2T,d^{*}-r^{*}\\}=L.$

For $i\geq 2$, by definition $d^{*}-\theta_{i}=2^{-i}\cdot L$. Because
$t(b)\in\left[\left\lfloor\theta_{i-1}\right\rfloor+1,\left\lfloor\theta_{i}\right\rfloor\right]\subseteq(\theta_{i-1},\theta_{i}]$,
we have $2^{-i}\cdot L\leq\lambda_{i}(b)\leq\min\\{2T,~{}2^{1-i}\cdot L\\}$.
Since $2\cdot L\leq 2T$, we conclude the lemma. ∎

Then, we present the lemmas for a lower bound of active units and an upper
bound of job numbers.

######  Lemma 17 (Lower bound of active units).

$\displaystyle A(r^{*},d^{*})\geq$ $\displaystyle\sum_{b\in
B_{0}}\left(2\lambda_{1}(b)+2\max\\{\lambda_{1}(b)-T,0\\}\right)$
$\displaystyle+\sum_{b\in
B_{1}}\left(2\lambda_{1}(b)+2\min\\{\lambda_{1}(b),T\\}\right)$
$\displaystyle+\sum_{i\geq 2}4\cdot(2^{-i}\cdot L)\cdot|B_{i}|.$

###### Proof.

Figure 2: An example for $b\in B_{1}$ when $d^{*}-r^{*}>2T$. The shaded area
is the considered $[r^{*},d^{*})$, and the online rent batch provides
$2\lambda_{1}(b)+2\min\\{\lambda_{1}(b),T\\}$ active units to it.

Three terms on the RHS of the inequality are counting of $B_{0},B_{1}$ and
$B_{\geq 2}$, where the first two are straightforward counting as shown in
Figure 2, and the last term was scaled down a bit by Lemma 16:

$4\sum_{i\geq 2}\sum_{b\in B_{i}}\lambda_{1}(b)=4\sum_{i\geq 2}\sum_{b\in
B_{i}}\lambda_{i}(b)\geq\sum_{i\geq 2}4\cdot(2^{-i}\cdot L)\cdot|B_{i}|.$

∎

Let $\mathcal{J}_{i}$ be the job set with deadline at most $d^{*}$ and
released in the $i$-th subinterval:

$\mathcal{J}_{i}=\left\\{j\in\mathcal{J}\;\middle|\;\lfloor\theta_{i-1}\rfloor+1\leq
r_{j}\leq\lfloor\theta_{i}\rfloor,\ d_{j}\leq d^{*}\right\\}.$

We provide an upper bound of $\mathcal{J}_{i}$ by the performance of our
algorithm.

######  Lemma 18.

Let $I_{t}$ be the semi-online batches allocated at or before time $t$. We
have that $\mathcal{J}_{i}$ is no more than the active units after
$\lfloor\theta_{i-1}\rfloor+1$ provided by SemiOnline at
$\lfloor\theta_{i}\rfloor$. i.e.,

$\mathcal{J}_{i}\leq
A_{I_{\lfloor\theta_{i}\rfloor}}(\lfloor\theta_{i-1}\rfloor+1,d^{*}).$

###### Proof.

Let us observe the time point $t=\lfloor\theta_{i}\rfloor$. $\textup{\sf
SemiOnline}(J_{t},T)$ reports $I_{t}$ at this time. By Lemma 11, $I_{t}$ is
feasible for $J_{t}$. By the definition of $\theta_{i}$, we prove $t\geq
d^{*}-T$ because $\theta_{1}\geq d^{*}-T$. Thus, all jobs with deadlines at
most $d^{*}$ are already in $J_{t}$, and combining with the feasibility of
$I_{t}$, we have:

$\mathcal{J}_{i}=J_{t}(\lfloor\theta_{i-1}\rfloor+1,d^{*})\leq
A_{t}(\lfloor\theta_{i-1}\rfloor+1,d^{*}).$

The lemma then concludes because we define $t=\lfloor\theta_{i}\rfloor$. ∎

######  Lemma 19 (Upper bound of job numbers).

We have two different upper bounds for $\mathcal{J}_{i}$:

  * •

$i=1$: $\quad\displaystyle|\mathcal{J}_{1}|\leq\sum_{b\in
B_{0}}\lambda_{1}(b)+\sum_{b\in B_{1}}\left(\lambda_{1}(b)+L/2\right).$

  * •

$i\geq 2$: $\quad\displaystyle|\mathcal{J}_{i}|\leq\sum_{b\in
B_{0}}\lambda_{i}(b)+2\cdot(2^{-i}\cdot L)\cdot\sum_{j=1}^{i}|B_{j}|.$

###### Proof.

In this proof, we apply Lemma 18 and count the number of active units after
$\theta_{i-1}$ by $I_{\lfloor\theta_{i}\rfloor}$. Note that by 14, each $3T$
length rent interval in $I_{\lfloor\theta_{i}\rfloor}$ corresponds to an
online Batch-Rent.

First, let us consider the case $i=1$. $I_{\lfloor\theta_{i}\rfloor}$
corresponds to the online batches with $t(b)\leq
I_{\lfloor\theta_{i}\rfloor}$. Note that the ending time of $b$ and its
corresponding semi-online rent interval are both $t(b)+2T$. Thus,
$A_{I_{\lfloor\theta_{i}\rfloor}}(\lfloor\theta_{i-1}\rfloor+1,d^{*})$
corresponds to $B_{0}$ and $B_{1}$.

For $i=1$, we keep the $B_{0}$ straightforward and calculate the upper bound
of active units provided by the corresponding semi-online batch for each batch
$b$ in $B_{1}$. Note that the semi-online rent set spans $[t(b)-T,t(b)+2T)$.
We split the $3T$ interval into first $T$ and last $2T$: the latter could be
upper bounded by $\lambda_{1}(b)$ using Lemma 16, and we could find that the
former is at most $L/2$:

  * •

When $d^{*}-r^{*}<2T$, $t(b)-r^{*}<(d^{*}-r^{*})/2$, then
$\min\left\\{T,t(b)-r^{*}\right\\}<L/2$.

  * •

When $d^{*}-r^{*}\geq 2T$, $L=2T$, and then
$\min\left\\{T,t(b)-r^{*}\right\\}\leq T=L/2$.

So we can conclude that

$|\mathcal{J}_{1}|\leq\sum_{b\in B_{0}}\lambda_{1}(b)+\sum_{b\in
B_{1}}\left(\lambda_{1}(b)+L/2\right).$

For the case $i\geq 2$, all jobs released in sub-interval $i$ can be allocated
at most $[\theta_{i-1}+1,d^{*})$, and by Lemma 16 each semi-online batch
covers at most $2\cdot(2^{-i}\cdot L)$. Like $i=1$, the inequality follows
direct counting on $\cup_{j=0}^{i}B_{j}$. ∎

Thus far, we are ready to prove Lemma 15 by a charging argument.

###### Proof of Lemma 15.

Recall that in Lemma 17 we have

$\displaystyle A(r^{*},d^{*})\geq$ $\displaystyle\sum_{b\in
B_{0}}\left(2\max\\{\lambda_{1}(b)-T,0\\}+2\lambda_{1}(b)\right)+\sum_{b\in
B_{1}}\left(2\lambda_{1}(b)+2\min\\{T,\lambda_{1}(b)\\}\right)$ (1)
$\displaystyle+\sum_{i\geq 2}4\cdot(2^{-i}\cdot L)\cdot|B_{i}|.$

Also, by Lemma 19,

$\mathcal{J}(r^{*},d^{*})\leq\sum_{b\in B_{0}}\lambda_{1}(b)+\sum_{b\in
B_{1}}\left(\lambda_{1}(b)+L/2\right)+\sum_{i\geq 2}\left(\sum_{b\in
B_{0}}\lambda_{i}(b)+2\cdot(2^{-i}\cdot L)\cdot\sum_{j=1}^{i}|B_{j}|\right).$
(2)

Using these two inequalities, we charge the upper bound of
$\mathcal{J}(r^{*},d^{*})$ and the lower bound of $A(r^{*},d^{*})$ to each
$b\in B$. We prove that for each $b$, the charged amount of
$\mathcal{J}(r^{*},d^{*})$’s upper bound is at most $A(r^{*},d^{*})$’s lower
bound.

First, for $b\in B_{0}$, the contribution of $b$ to the lower bound of
$A(r^{*},d^{*})$ (i.e., RHS of Equation 1) is:
$2\max\\{\lambda_{1}(b)-T,0\\}+2\lambda_{1}(b).$ The contribution to the upper
bound of $\mathcal{J}(r^{*},d^{*})$ (i.e., RHS of Equation 2) is:
$\lambda_{1}(b)+\sum_{i\geq 2}\lambda_{i}(b).$ Note that $b\in B_{0}$ only
contributes to a prefix of $[r,d)$, it is easy to see that $\lambda_{i}(b)\leq
2^{1-i}\lambda_{1}(b)$, and thus

$\lambda_{1}(b)+\sum_{i\geq 2}\lambda_{i}(b)\leq\lambda_{1}(b)+\sum_{i\geq
2}2^{1-i}\lambda_{1}(b)<2\lambda_{1}(b).$

We are done for $b\in B_{0}$.

Second, for $b\in B_{1}$, the contribution of $b$ to the lower bound of
$A(r^{*},d^{*})$ (i.e., RHS of Equation 1) is:
$2\lambda_{1}(b)+2\min\\{T,\lambda_{1}(b)\\}.$ The contribution to the upper
bound of $\mathcal{J}(r^{*},d^{*})$ (i.e., RHS of Equation 2) is:
$\lambda_{1}(b)+L/2+\sum_{i\geq 2}2\cdot(2^{-i}\cdot L).$ Then, we have

$\displaystyle\lambda_{1}(b)+L/2+\sum_{i\geq 2}2\cdot(2^{-i}\cdot L)$
$\displaystyle<\lambda_{1}(b)+L/2+2\cdot\left(2^{-1}\cdot L\right)$
$\displaystyle\leq\lambda_{1}(b)+L/2+2\cdot\min\left\\{T,\lambda_{1}(b)\right\\}$
$\displaystyle\leq 2\lambda_{1}(b)+2\min\\{T,\lambda_{1}(b)\\}.$

The last inequality holds by Lemma 16. Therefore, we are done for $b\in
B_{1}$.

Finally, for $b\in B_{i\geq 2}$, the contribution of $b$ to the lower bound of
$A(r^{*},d^{*})$ (i.e., RHS of Equation 1) is: $4\cdot(2^{-i}\cdot L).$ The
contribution to the upper bound of $\mathcal{J}(r^{*},d^{*})$ (i.e., RHS of
Equation 2) is: $\sum_{i^{\prime}\geq i}2\cdot(2^{-i^{\prime}}\cdot L).$ We
are done because $\sum_{i^{\prime}\geq i}2^{-i^{\prime}}<2^{1-i}.$ Summing up
three parts, we have proved that $A(r^{*},d^{*})\geq\mathcal{J}(r^{*},d^{*})$.

∎

###  5.2 A Remark on Running Time.

We only need to recalculate ${\sf SemiOnline}$ if the job set gets updated,
and the procedure of reconstructing the rent set in ${\sf SemiOnline}$ can be
maintained incrementally. Thus, it is possible to implement the algorithm
calling EDF at most $n+\textup{\sf OPT}\leq 2n$ times, and hence achieve a
worst case guarantee of $O(n^{2}\log n)$. Also, note that a job can influence
the calculation of ${\sf SemiOnline}$ for at most $O(T)$ time units, so the
${\sf SemiOnline}$ can also update in $O(nw\log w)$ if there are at most
$O(w)$ jobs within any interval of length $O(T)$. Therefore, the online
algorithm is efficient in terms of worst case guarantee and also average
online updating.

##  6 Online Rent Minimization with Delay

In the version with delay, we are also given an online released job set
$\mathcal{J}$ and a rent length $T$. We aim to minimize the number of rents
needed to process all jobs. The notations are the same as in the Online Rent
Minimization problem. Moreover, we are given a nonnegative integer $\lambda$
as the delay parameter. It means that if we rent a machine at time $t$, we
will have an active machine at $[t+\lambda,t+\lambda+T)$. Note that it is
impossible to serve an unknown emergency job with $d_{j}-r_{j}\leq\lambda$
online; following Chen and Zhang [5], we require that the active time
$d_{j}-r_{j}$ is at least $\lambda+1$.

We use the following reduction lemma and our $6$-competitive no-delay
algorithm as a black box to prove Theorem 2. Chen and Zhang [5] also mention
this approach.

######  Lemma 20 (Reduction).

If $\textup{\sf ALG}(\mathcal{J})\leq\Gamma\cdot\textup{\sf OPT}(\mathcal{J})$
for every job set $\mathcal{J}$, we have an algorithm $\textup{\sf
ALG}_{\lambda}$ that guarantees

$\textup{\sf
ALG}_{\lambda}(\mathcal{J},\lambda)\leq\Gamma\cdot(\lambda+1)\cdot\textup{\sf
OPT}(\mathcal{J}),$

if $\forall j\in\mathcal{J}$, $d_{j}-r_{j}\geq\lambda+1$.

#### Construction of $\mathcal{J}_{\lambda=0}$ and $\textup{\sf
ALG}_{\lambda}$.

$\mathcal{J}_{\lambda=0}$ is a modified job set by $\mathcal{J}$. For any job
$j$ in $\mathcal{J}$, we construct a corresponding $j^{\prime}$ in
$\mathcal{J}_{\lambda=0}$ such that $r_{j^{\prime}}=r_{j}$ and
$d_{j^{\prime}}=d_{j}-\lambda$. Then, we construct $\textup{\sf
ALG}_{\lambda}$. At any time $t$, $\textup{\sf ALG}_{\lambda}(\mathcal{J})$
will make the rent decision as the decisions of $\textup{\sf
ALG}(\mathcal{J}_{\lambda=0})$ made at $t$. That is, if there is a rent
interval $[t,t+T)$ in $\textup{\sf ALG}(\mathcal{J}_{\lambda=0})$, we will
have a rent interval $[t+\lambda,t+T+\lambda)$ in $\textup{\sf
ALG}_{\lambda}(\mathcal{J})$. Because we do not change the releasing time,
$\textup{\sf ALG}_{\lambda}$ is also an online algorithm. Clearly, the cost of
$\textup{\sf ALG}_{\lambda}(\mathcal{J})$ is the same as that of $\textup{\sf
ALG}(\mathcal{J}_{\lambda=0})$.

######  Lemma 21.

$\textup{\sf
ALG}_{\lambda}(\mathcal{J},\lambda)\leq\Gamma(\lambda+1)\cdot\textup{\sf
OPT}(\mathcal{J})$.

###### Proof.

We have $\textup{\sf ALG}_{\lambda}(\mathcal{J},\lambda)=\textup{\sf
ALG}(\mathcal{J}_{\lambda=0})$ by the construction. Then, let us refer to the
lemma for OPT in Chen and Zhang [5]:

######  Lemma 22 ([5]).

$\textup{\sf OPT}(\mathcal{J}_{\lambda=0})\leq(\lambda+1)\cdot\textup{\sf
OPT}(\mathcal{J}).$

By Lemma 22,

$\textup{\sf ALG}_{\lambda}(\mathcal{J},\lambda)=\textup{\sf
ALG}(\mathcal{J}_{\lambda=0})\leq\Gamma\cdot\textup{\sf
OPT}(\mathcal{J}_{\lambda=0})\leq\Gamma(\lambda+1)\cdot\textup{\sf
OPT}(\mathcal{J}).$

∎

######  Lemma 23.

$\textup{\sf ALG}_{\lambda}(\mathcal{J})$ is feasible to process all jobs in
$\mathcal{J}$.

###### Proof.

We apply Lemma 3 to prove the feasibility. Let $I$ be the rent set of
$\textup{\sf ALG}(\mathcal{J}_{\lambda=0})$. Given that $\textup{\sf
ALG}(\mathcal{J}_{\lambda=0})$ is feasible, we know that $\forall
r^{*}<d^{*}$, $\mathcal{J}_{\lambda=0}(r^{*},d^{*})\leq A_{I}(r^{*},d^{*})$.
Next, we consider $\textup{\sf ALG}_{\lambda}(\mathcal{J})$ and let its rent
set be $I^{\prime}$. $\forall r^{*}<d^{*}$ such that $d^{*}-r^{*}\leq\lambda$,
$\mathcal{J}(r^{*},d^{*})=0$ by definition. For those
$d^{*}-r^{*}\geq\lambda+1$,

$\mathcal{J}(r^{*},d^{*})=\mathcal{J}_{\lambda=0}(r^{*},d^{*}-\lambda)\leq
A_{I}(r^{*},d^{*}-\lambda).$

By definition, the active unit in $A_{I}(r^{*},d^{*}-\lambda)$ will be
postponed to $A_{I^{\prime}}(r^{*}+\lambda,d^{*})$. Thus, we have

$\mathcal{J}(r^{*},d^{*})\leq
A_{I}(r^{*},d^{*}-\lambda)=A_{I^{\prime}}(r^{*}+\lambda,d^{*})\leq
A_{I^{\prime}}(r^{*},d^{*}).$

Therefore, we can use Lemma 3 to show the feasibility of $I^{\prime}$ in both
cases. ∎

We now can conclude the correctness of Lemma 20 from Lemma 21 and Lemma 23,
Theorem 2 also follows directly.

See 2

##  7 Conclusion and Future Work

In conclusion, our main contribution is a $6$-competitive algorithm for the
Online Rent Minimization problem under unit-size jobs, which follows the
oracle-based framework.

Since the Online Rent Minimization problem is a generalization of the Online
Machine Minimization problem, where we have an optimal $e$-competitive
algorithm, one major question is: Is the Rent Minimization problem strictly
harder than the Machine Minimization problem?

On the other hand, we are also interested in the power of oracle-based
algorithms. Note that the optimal $e$-competitive algorithm for Machine
Minimization follows the oracle-based framework. It is interesting to ask:
What is the best competitive ratio we can achieve for the Online Rent
Minimization problem by using the oracle-based framework? The Semi-Online
captures our current understanding of the possible range of optimal solutions,
so replacing it with an optimal oracle cannot improve ratio directly by the
same argument in the paper. Is it possible to obtain a better ratio with
access to an optimal oracle?

## Acknowledgement

The authors would like to thank Minming Li, Pinyan Lu, and Biaoshuai Tao for
many insightful discussions on the research topic of this paper. Yuhao Zhang
is supported by National Natural Science Foundation of China, Grant No.
62102251.

## References

  * Angel et al. [2017] Eric Angel, Evripidis Bampis, Vincent Chau, and Vassilis Zissimopoulos.  On the Complexity of Minimizing the Total Calibration Cost.  In Mingyu Xiao and Frances Rosamond, editors, _Frontiers in Algorithmics_ , Lecture Notes in Computer Science, pages 1–12, Cham, 2017\. Springer International Publishing.  ISBN 978-3-319-59605-1.  doi: 10.1007/978-3-319-59605-1_1.
  * Bansal et al. [2007] Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs.  Speed scaling to manage energy and temperature.  _J. ACM_ , 54(1), mar 2007.  ISSN 0004-5411.  doi: 10.1145/1206035.1206038.  URL https://doi.org/10.1145/1206035.1206038.
  * Bender et al. [2013] Michael A. Bender, David P. Bunde, Vitus J. Leung, Samuel McCauley, and Cynthia A. Phillips.  Efficient scheduling to minimize calibrations.  In _Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures_ , pages 280–287, Montréal Québec Canada, July 2013. ACM.  ISBN 978-1-4503-1572-2.  doi: 10.1145/2486159.2486193.  URL https://dl.acm.org/doi/10.1145/2486159.2486193.
  * Chen et al. [2019] Lin Chen, Minming Li, Guohui Lin, and Kai Wang.  Approximation of Scheduling with Calibrations on Multiple Machines (Brief Announcement).  In _The 31st ACM Symposium on Parallelism in Algorithms and Architectures_ , pages 237–239, Phoenix AZ USA, June 2019. ACM.  ISBN 978-1-4503-6184-2.  doi: 10.1145/3323165.3323173.  URL https://dl.acm.org/doi/10.1145/3323165.3323173.
  * Chen and Zhang [2022] Zuzhi Chen and Jialin Zhang.  Online scheduling of time-critical tasks to minimize the number of calibrations.  _Theoretical Computer Science_ , page S0304397522000548, January 2022\.  ISSN 03043975.  doi: 10.1016/j.tcs.2022.01.040.  URL https://linkinghub.elsevier.com/retrieve/pii/S0304397522000548.
  * Chuzhoy et al. [2004] J. Chuzhoy, S. Guha, S. Khanna, and J. Naor.  Machine Minimization for Scheduling Jobs with Interval Constraints.  In _45th Annual IEEE Symposium on Foundations of Computer Science_ , pages 81–90, Rome, Italy, 2004. IEEE.  ISBN 978-0-7695-2228-9.  doi: 10.1109/FOCS.2004.38.  URL http://ieeexplore.ieee.org/document/1366227/.
  * Cieliebak et al. [2004] Mark Cieliebak, Thomas Erlebach, Fabian Hennecke, Birgitta Weber, and Peter Widmayer.  Scheduling with release times and deadlines on a minimum number of machines.  In Jean-Jacques Lévy, Ernst W. Mayr, and John C. Mitchell, editors, _Exploring New Frontiers of Theoretical Informatics, IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004), 22-27 August 2004, Toulouse, France_ , volume 155 of _IFIP_ , pages 209–222. Kluwer/Springer, 2004.  doi: 10.1007/1-4020-8141-3\\_18.  URL https://doi.org/10.1007/1-4020-8141-3_18.
  * Devanur et al. [2014] Nikhil Devanur, Konstantin Makarychev, Debmalya Panigrahi, and Grigory Yaroslavtsev.  Online Algorithms for Machine Minimization.  _arXiv:1403.0486 [cs]_ , March 2014.  URL http://arxiv.org/abs/1403.0486.  arXiv: 1403.0486.
  * Garey and Johnson [1979] M. R. Garey and David S. Johnson.  _Computers and Intractability: A Guide to the Theory of NP-Completeness_.  W. H. Freeman, 1979.  ISBN 0-7167-1044-7.
  * Kao et al. [2012] Mong-Jen Kao, Jian-Jia Chen, Ignaz Rutter, and Dorothea Wagner.  Competitive design and analysis for machine-minimizing job scheduling problem.  In Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee, editors, _Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings_ , volume 7676 of _Lecture Notes in Computer Science_ , pages 75–84. Springer, 2012.  doi: 10.1007/978-3-642-35261-4\\_11.  URL https://doi.org/10.1007/978-3-642-35261-4_11.
  * Raghavan and Thompson [1987] Prabhakar Raghavan and Clark D. Thompson.  Randomized rounding: a technique for provably good algorithms and algorithmic proofs.  _Comb._ , 7(4):365–374, 1987.  doi: 10.1007/BF02579324.  URL https://doi.org/10.1007/BF02579324.
  * Saha [2013] Barna Saha.  Renting a Cloud.  In Anil Seth and Nisheeth K. Vishnoi, editors, _IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)_ , volume 24 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 437–448, Dagstuhl, Germany, 2013. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  ISBN 978-3-939897-64-4.  doi: 10.4230/LIPIcs.FSTTCS.2013.437.  URL http://drops.dagstuhl.de/opus/volltexte/2013/4391.  ISSN: 1868-8969.
  * Yu and Zhang [2009] Guosong Yu and Guochuan Zhang.  Scheduling with a minimum number of machines.  _Oper. Res. Lett._ , 37(2):97–101, 2009.  doi: 10.1016/j.orl.2009.01.008.  URL https://doi.org/10.1016/j.orl.2009.01.008.


# Weighted composition operators preserving various Lipschitz constants

Ching-Jou Liao, Chih-Neng Liu, Jung-Hui Liu and Ngai-Ching Wong  Department of
Mathematics, Hong Kong Baptist University, Hong Kong<EMAIL_ADDRESS>School of Information Engineering, Sanming University, No. 25, Jing Dong Road
San Yuan District, Sanming City, Fujian 365004, China<EMAIL_ADDRESS>Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung,
80424, Taiwan<EMAIL_ADDRESS><EMAIL_ADDRESS>Dedicated to
Professor Anthony To-Ming Lau on the occasion of his 80th birthday

(Date: June 8, 2023)

###### Abstract.

Let $\mathrm{Lip}(X)$, $\mathrm{Lip}^{b}(X)$, $\mathrm{Lip}^{\mathrm{loc}}(X)$
and $\mathrm{Lip}^{\mathrm{pt}}(X)$ be the vector spaces of Lipschitz, bounded
Lipschitz, locally Lipschitz and pointwise Lipschitz (real-valued) functions
defined on a metric space $(X,d_{X})$, respectively. We show that if a
weighted composition operator $Tf=h\cdot f\circ\varphi$ defines a bijection
between such vector spaces preserving Lipschitz constants, local Lipschitz
constants or pointwise Lipschitz constants, then $h=\pm 1/\alpha$ is a
constant function for some scalar $\alpha>0$ and $\varphi$ is an
$\alpha$-dilation.

Let $U$ be open connected and $V$ be open, or both $U,V$ are convex bodies, in
normed linear spaces $E,F$, respectively. Let $Tf=h\cdot f\circ\varphi$ be a
bijective weighed composition operator between the vector spaces
$\mathrm{Lip}(U)$ and $\mathrm{Lip}(V)$, $\mathrm{Lip}^{b}(U)$ and
$\mathrm{Lip}^{b}(V)$, $\mathrm{Lip}^{\mathrm{loc}}(U)$ and
$\mathrm{Lip}^{\mathrm{loc}}(V)$, or $\mathrm{Lip}^{\mathrm{pt}}(U)$ and
$\mathrm{Lip}^{\mathrm{pt}}(V)$, preserving the Lipschitz, locally Lipschitz,
or pointwise Lipschitz constants, respectively. We show that there is a linear
isometry $A:F\to E$, an $\alpha>0$ and a vector $b\in E$ such that
$\varphi(x)=\alpha Ax+b$, and $h$ is a constant function assuming value $\pm
1/\alpha$. More concrete results are obtained for the special cases when
$E=F=\mathbb{R}^{n}$, or when $U,V$ are $n$-dimensional flat manifolds.

###### Key words and phrases:

(Local/pointwise) Lipschitz functions, (Local/pointwise) Lipschitz constants,
weighted composition operators, flat manifolds

###### 2000 Mathematics Subject Classification:

46B04, 51F30, 26A16

##  1\. Introduction

Let $f:(X,d_{X})\to(Y,d_{Y})$ be a map between metric spaces. Let
$B(p,\epsilon)$ be the open ball in the metric space $X$ centered at $p$ of
radius $\epsilon>0$. We say that $f$ is _Lipschitz_ if the _Lipschitz
constant_

$L(f)=\sup_{x\neq y\in X}\frac{d_{Y}(f(x),f(y))}{d_{X}(x,y)}<+\infty;$

we say that $f$ is _locally Lipschtiz_ if the _local Lipschtiz constants_

$L^{\mathrm{loc}}_{p}(f)=\lim_{\epsilon\to 0^{+}}\sup_{x\neq y\in
B(p,\epsilon)}\frac{d_{Y}(f(x),f(y))}{d_{X}(x,y)}<+\infty,\quad\forall p\in
X;$

and we say that $f$ is _pointwise Lipschitz_ if the _pointwise Lipschitz
constants_

$L^{\mathrm{pt}}_{p}(f)=\limsup_{x\to
p}\frac{d_{Y}(f(x),f(p))}{d_{X}(x,p)}<+\infty,\quad\forall p\in X.$

Let $\mathrm{Lip}(X)$, $\mathrm{Lip}^{b}(X)$, $\mathrm{Lip}^{\mathrm{loc}}(X)$
and $\mathrm{Lip}^{\mathrm{pt}}(X)$ denote the (real) vector spaces of
Lipschitz, bounded Lipschitz, locally Lipschtiz, and pointwise Lipschitz
__(real-valued) functions on $X$ into $Y=\mathbb{R}$, respectively. Clearly,
$\mathrm{Lip}^{b}(X)\subseteq\mathrm{Lip}(X)\subseteq\mathrm{Lip}^{\mathrm{loc}}(X)\subseteq\mathrm{Lip}^{\mathrm{pt}}(X)$
and $0\leq L^{\mathrm{pt}}(f)\leq L^{\mathrm{loc}}\leq L(f)$, in general, but
all the inclusions and inequalities can be strict. However, for a bounded
metric space $X$ we have $\mathrm{Lip}(X)=\mathrm{Lip}^{b}(X)$. On the other
hand, $\mathrm{Lip}(X)=\mathrm{Lip}(\overline{X})$ where $\overline{X}$ is the
metric completion of $X$. See, e.g., [2, Examples 2.6 and 2.7], for more
details.

We are interested in the question how the (resp. local, pointwise) Lipschitz
constants determine the (resp. local, pointwise) Lipschitz function spaces.
For example, if $T:\mathrm{Lip}(X)\to\mathrm{Lip}(Y)$ is a bijective linear
map preserving Lipschitz constants, namely,

$L(Tf)=L(f),\quad\text{for every $f\in\mathrm{Lip}(X)$,}$

we ask if the underlying metric spaces $X,Y$ are equivalent, and if $T$
carries some good structure. The following results give us motivations.

######  Proposition 1.1.

  1. (a)

(Weaver [11, Theorem D]; see also [12, Sections 2.6 and 2.7]) Let $X,Y$ be
complete metric spaces of diameter at most $2$, which cannot be written as a
disjoint union of two nonempty subsets with distance $\geq 1$. If
$T:\mathrm{Lip}(X)\rightarrow\mathrm{Lip}(Y)$ is a surjective linear isometry
with respect to the norm $\|f\|=\max\\{\|f\|_{\infty},L(f)\\}$, then

$Tf=\alpha\cdot f\circ\varphi,\quad\forall f\in\mathrm{Lip}(X),$

where $\varphi:Y\rightarrow X$ is a surjective isometry and $\alpha$ is a
unimodular constant.

  2. (b)

(Wu [13], Araujo and Dubarbie [1, Corollary 6.1]) Let $X$ be a bounded
complete metric space and $Y$ be a compact metric space. If
$T:\mathrm{Lip}(X)\rightarrow\mathrm{Lip}(Y)$ is a linear bijection preserving
zero products, that is,

$fg=0\quad\implies\quad TfTg=0,$

then

$Tf=h\cdot f\circ\varphi,\quad\forall f\in\mathrm{Lip}(X),$

where $\varphi$ is a bijective Lipschitz map from $Y$ onto $X$ with Lipschitz
inverse $\varphi^{-1}$, and $h\in\mathrm{Lip}(Y)$ is nonvanishing.

See also, e.g., [2, 6, 10]. However, if the map $T$ preserves only the
Lipschitz constants without other assumption, $T$ needs not carry a weighted
composition operator form. For example, let $\Psi$ be an arbitrary linear
functional of the vector space $\mathrm{Lip}(X)$. Then the assignment
$Tf(x)=f(x)+\Psi(f)$ defines a linear bijective map from $\mathrm{Lip}(X)$
onto $\mathrm{Lip}(X)$ preserving Lipschitz constants. But $T$ does not assume
a weighted composition form.

In this paper, based on [7], we study the structure of a weighted composition
operator $Tf=h\cdot f\circ\varphi$ between Lipschitz function spaces defined
on metric spaces $X$ and $Y$, which preserves Lipschitz constants. We will see
that $\varphi$ is an _$\alpha$ -dilation_ for a positive constant $\alpha$,
i.e., $d_{X}(\varphi(u),\varphi(v))=\alpha d_{Y}(u,v)$, $\forall u,v\in Y$,
and $h$ is a constant function assuming the value $\pm 1/\alpha$. In
particular, if $U$ is open connected and $V$ is open, or both $U,V$ are convex
bodies, in normed linear spaces $E,F$, respectively, then $\varphi(x)=\alpha
Ax+b$ for a linear isometry $A:F\to E$ and a vector $b\in E$. In other words,

$Tf(x)=\pm\alpha^{-1}f(Ax+b).$

When $E=F=\mathbb{R}^{n}$, we obtain similar results for those bijective
weighted composition operators preserving local or pointwise Lipschitz
constants. We also extend these results to the case when $U,V$ are flat
manifolds.

##  2\. Weighted composition operators preserving Lipschitz constants

All vector spaces discussed in this paper are over the real number field
$\mathbb{R}$.

In this section, we study Lipschitz constant preserving weighted composition
operators between Lipschtiz function spaces. We begin with some well known
results. Here, by an _$\alpha$ -dilation_ (resp.  _isometry_) between metric
spaces $X,Y$ for $\alpha>0$, we mean a map $\varphi:X\to Y$ such that
$d_{Y}(\varphi(x),\varphi(y))=\alpha d_{X}(x,y)$ (resp. when $\alpha=1$) for
all $x,y\in X$. Moreover, a _convex body_ in a normed linear space is a (not
necessarily closed or bounded) convex set with nonempty interior.

######  Proposition 2.1.

  1. (a)

(Mazur-Ulam theorem; see, e.g., [4]) Every surjective isometry $T:M\to N$
between normed linear spaces is affine; namely,

$T(\lambda x+(1-\lambda)y)=\lambda Tx+(1-\lambda)Ty,\quad\text{for all $x,y\in
M$ and $0\leq\lambda\leq 1$.}$

  2. (b)

(Mankiewicz [9]) Every isometry $\varphi:U\to V$ from an open connected set
(resp. convex body) $U$ in a normed linear space $M$ onto an open set (resp.
convex body) $V$ in a normed linear space $N$ has a unique isometric extension
from $M$ onto $N$.

Recall that a metric space $(X,d_{X})$ is _quasi-convex_ if there is a
constant $C>0$ such that for any $x,y\in X$ there is a continuous path in $X$
joining $x$ to $y$ with length at most $Cd_{X}(x,y)$.

######  Proposition 2.2 ([5, Theorems 3.9 and 3.12]).

Let $\varphi:Y\to X$ be a map between metric spaces. Then $\varphi$ is
Lipschitz if and only if

  1. (a)

$f\circ\varphi\in\mathrm{Lip}(Y)$ for each $f\in\mathrm{Lip}(X)$; or

  2. (b)

$f\circ\varphi\in\mathrm{Lip}^{b}(Y)$ for each $f\in\mathrm{Lip}^{b}(X)$,
provided that both $X,Y$ are quasi-convex.

######  Theorem 2.3.

Let $(X,d_{X})$ and $(Y,d_{Y})$ be (resp. quasi-convex) metric spaces. Let
$T:\mathrm{Lip}(X)\to\mathrm{Lip}(Y)$ (resp.
$T:\mathrm{Lip}^{b}(X)\to\mathrm{Lip}^{b}(Y)$) be a bijective weighted
composition operator $Tf=h\cdot f\circ\varphi$ preserving Lipschitz constants.
Then $\varphi$ is an $\alpha$-dilation from $Y$ onto a dense subset
$X_{0}=\varphi(Y)$ of $X$ for $\alpha>0$, and $h$ is a constant function
assuming either $1/\alpha$ or $-1/\alpha$. If $Y$ is complete, then
$\varphi(Y)=X$.

###### Proof.

We verify the case when $T$ sends $\mathrm{Lip}(X)$ onto $\mathrm{Lip}(Y)$.
The other case follows similarly.

Since $T$ preserves Lipschitz constants, so does its inverse; indeed,

$L(g)=L(TT^{-1}g)=L(T^{-1}g),\quad\text{for all $g$ in $\mathrm{Lip}(Y)$.}$

Observe that

$0=L(1)=L(T1)=L(h)=\sup_{u\neq v}\frac{|h(u)-h(v)|}{d_{Y}(u,v)}.$

Hence $h=\pm 1/\alpha$ is a nonzero constant function for a scalar $\alpha>0$.

For any $f$ in $\mathrm{Lip}(X)$, we have $f\circ\varphi=\pm\alpha
Tf\in\mathrm{Lip}(Y)$. It follows from Proposition 2.2 that $\varphi$ is
Lipschitz. Since $T$ is bijective, $\varphi$ is one-to-one with dense range.
Let $X_{0}=\varphi(Y)$, which is a dense subset of the metric space $X$.
Define a bijective linear map $S:\mathrm{Lip}(Y)\to\mathrm{Lip}(X_{0})$ such
that $Sg=T^{-1}g\mid_{X_{0}}$; in other words, $Sg=\pm\alpha g\circ\psi$,
where $\psi$ is the bijection from $X_{0}$ onto $Y$ defined by the condition
$\psi(x)=y$ whenever $x=\varphi(y)$. Then a similar argument shows that $\psi$
is Lipschitz from $X_{0}$ onto $Y$. Let
$\overline{\varphi}:\overline{Y}\to\overline{X}$ and
$\overline{\psi}:\overline{X}\to\overline{Y}$ be the unique Lipschitz
extensions of $\varphi$ and $\psi$ between the metric completions
$\overline{X},\overline{Y}$ of $X,Y$, respectively. For any
$x\in\overline{X}$, let $x_{n}\in X_{0}$ such that $x_{n}\to x$, we have
$\overline{\varphi}(\overline{\psi}(x))=\lim_{n}\overline{\varphi}(\overline{\psi}(x_{n}))=\lim_{n}\varphi(\psi(x_{n}))=\lim_{n}x_{n}=x$.
It amounts to saying that
$\overline{\varphi}\circ\overline{\psi}=I_{\overline{X}}$. In a similar
manner, we see that $\overline{\psi}\circ\overline{\varphi}=I_{\overline{Y}}$,
and thus $\overline{\varphi}^{-1}=\overline{\psi}$ is also Lipschitz.

On the other hand, the fact

$L(f)=L(Tf)=L(\pm\alpha^{-1}f\circ\varphi)\leq\alpha^{-1}L(f)L(\varphi),\quad\forall
f\in\mathrm{Lip}(X),$

implies that $L(\varphi)\geq\alpha$. Assume $L(\varphi)>\alpha$. Then there
are $p$ and $q$ in $Y$, such that

$d_{X}(\varphi(p),\varphi(q))>\alpha d_{Y}(p,q).$

Define $\tilde{f}:X\to\mathbb{R}$ by

$\tilde{f}(x)=\min\\{d_{X}(x,\varphi(p)),d_{X}(\varphi(p),\varphi(q))\\}.$

Then

$\displaystyle|\tilde{f}(x)-\tilde{f}(y)|$
$\displaystyle\leq|d(x,\varphi(p))-d(y,\varphi(p))|$ $\displaystyle\leq
d_{X}(x,y),\quad\text{for all $x$, $y$ in $X$,}$

and

$\|\tilde{f}(\varphi(q))-\tilde{f}(\varphi(p))\|=d(\varphi(q),\varphi(p)).$

Hence, $\tilde{f}\in\mathrm{Lip}^{b}(X)$ with $L(\tilde{f})=1$. But

$\displaystyle|T\tilde{f}(p)-T\tilde{f}(q)|=\,$
$\displaystyle|h(p)\tilde{f}\circ\varphi(p)-h(q)\tilde{f}\circ\varphi(q)|$
$\displaystyle=\,$ $\displaystyle\alpha^{-1}d_{X}(\varphi(p),\varphi(q))$
$\displaystyle>\,$ $\displaystyle d_{Y}(p,q).$

This implies $L(T\tilde{f})>1$, which is a contradiction. Hence
$L(\varphi)=\alpha$. Similarly, $L(\psi)=\alpha^{-1}$.

If $u\neq v$ in $Y$ and $\varphi(u)=s$, $\varphi(v)=t$ in $X$, then

$\alpha=L(\varphi)\geq\frac{d_{X}(\varphi(u),\varphi(v))}{d_{Y}(u,v)}=\frac{d_{X}(s,t)}{d_{Y}(\psi(s),\psi(t))}\geq\frac{1}{L(\psi)}=\alpha,$

and thus

$d(\varphi(u),\varphi(v))=\alpha d_{Y}(u,v).$

In other words, $\varphi$ is an $\alpha$-dilation.

Finally, if $Y=\overline{Y}$ is complete then $X_{0}=\varphi(Y)$ is also
complete, and thus $\varphi(Y)=\overline{X_{0}}=X$. ∎

######  Corollary 2.4.

Assume either that $U,V$ are open sets and $U$ is connected, or that both
$U,V$ are convex bodies, in normed linear spaces $E,F$, respectively. Let the
weighed composition operator $Tf=h\cdot f\circ\varphi$ define a bijection from
$\mathrm{Lip}(U)$ onto $\mathrm{Lip}(V)$ preserving Lipschitz constants. Then
there is a linear isometry $A:F\to E$ with dense range, a scalar $\alpha>0$
and a vector $b\in E$ such that $\varphi(y)=\alpha Ay+b$ for all $y\in V$, and
$h$ is a constant function assuming value $\pm\alpha^{-1}$. In other words,

$Tf(y)=\pm\alpha^{-1}f(\alpha Ay+b),\quad\text{for all $f\in\mathrm{Lip}(U)$
and for all $y\in V$.}$

###### Proof.

By Theorem 2.3, we know that $h=\pm\alpha^{-1}$ is a constant function for
some $\alpha>0$, and $\varphi$ is an $\alpha$-dilation from $V$ onto a dense
subset of $U$. Indeed, $\varphi$ extends uniquely to an $\alpha$-dilation
$\overline{\varphi}$ from $\overline{V}$ onto $\overline{U}$, where
$\overline{U},\overline{V}$ are the closures of $U,V$ in the Banach space
completions $\overline{E},\overline{F}$ of $E,F$, respectively.

If $V$ is connected in $F$, then so is the interior of $\overline{V}$ in
$\overline{F}$. It is plain that $\overline{\varphi}$ sends the interior of
$\overline{V}$ in the Banach space $\overline{F}$ onto the interior of
$\overline{U}$ in the Banach space $\overline{E}$. Then $\overline{\varphi}$
extends uniquely to an affine $\alpha$-dilation from $\overline{F}$ onto
$\overline{E}$ by Proposition 2.1. In the other case, $U,V$ are both convex
bodies in $E,F$, and thus so are $\overline{U},\overline{V}$ in the Banach
spaces $\overline{E},\overline{F}$, respectively. It follows from Proposition
2.1 again that $\overline{\varphi}$ extends uniquely to an affine
$\alpha$-dilation from $\overline{F}$ onto $\overline{E}$. In both cases,
$\varphi$ extends to a unique affine $\alpha$-dilation from $F$ into $E$ with
dense range. The assertion follows. ∎

######  Corollary 2.5.

Let $U,V$ be convex bodies in normed linear spaces $E,F$, respectively. Let
the weighed composition operator $Tf=h\cdot f\circ\varphi$ define a bijection
from $\mathrm{Lip}^{b}(U)$ onto $\mathrm{Lip}^{b}(V)$ preserving Lipschitz
constants. Then there is a surjective linear isometry $A:F\to E$, a scalar
$\alpha>0$ and a vector $b\in E$ such that $\varphi(y)=\alpha Ay+b$ for all
$y\in V$, and $h$ is a constant function assuming value $\pm\alpha^{-1}$. In
other words,

$Tf(y)=\pm\alpha^{-1}f(\alpha Ay+b),\quad\text{for all $f\in\mathrm{Lip}(U)$
and for all $y\in V$.}$

###### Proof.

Note that convex bodies in normed spaces are quasi-convex. The proof now goes
the same way as in Corollary 2.4. ∎

######  Example 2.6.

(a) Let $Tf=h\cdot f\circ\varphi$ define a bijection
$T:\mathrm{Lip}(\mathbb{R}^{n})\to\mathrm{Lip}(\mathbb{R}^{n})$ preserving
Lipschitz constants. It follows from Theorem 2.3 that $\varphi$ is Lipschitz,
and indeed an $L(\varphi)$-dilation of $\mathbb{R}^{n}$. Moreover, $h$ is the
constant function assuming either $1/L(\varphi)$ or $-1/L(\varphi)$. By
Proposition 2.1, there is an $n\times n$ orthogonal matrix $A$ such that
$\varphi(x)=L(\varphi)Ax+\varphi(0)$. Let $\alpha=L(\varphi)$ and
$b=\varphi(0)$, we have

$Tf(x)=\pm\alpha^{-1}f(\alpha Ax+b)\quad\text{for all $x\in\mathbb{R}^{n}$.}$

(b) Let $Tf=h\cdot f\circ\varphi$ define a bijection
$T:\mathrm{Lip}([0,1])\to\mathrm{Lip}([0,1])$ preserving Lipschitz constants.
Applying Theorem 2.3, we see that $\varphi$ is an $L(\varphi)$-dilation of
$[0,1]$. This forces $L(\varphi)=1$, and either $\varphi(x)=x$ or
$\varphi(x)=1-x$. Consequently, $T$ is given by

$Tf(x)=\pm f(x)\quad\text{or}\quad Tf(x)=\pm f(1-x).$

(c) More generally, let $Tf=h\cdot f\circ\varphi$ define a bijection
$T:\mathrm{Lip}([a,b])\to\mathrm{Lip}([c,d])$ preserving Lipschitz constants.
Then $L(\varphi)=\frac{b-a}{d-c}$, $h=\pm\frac{d-c}{b-a}$, and either

$\varphi(x)=\frac{b-a}{d-c}(x-c)+a\quad\text{or}\quad\varphi(x)=\frac{b-a}{d-c}(d-x)+a.$

Consequently,

$T(f)=\pm\frac{d-c}{b-a}f\left(\frac{b-a}{d-c}(x-c)+a\right),\quad\text{or}\quad
T(f)=\pm\frac{d-c}{b-a}f\left(\frac{b-a}{d-c}(d-x)+a\right).$

(d) Let $T:\mathrm{Lip}([0,1]^{n})\to\mathrm{Lip}([0,1]^{n})$ be a bijective
weighted composition operator preserving Lipschitz constants. It follows from
Corollary 2.4 and the structure of the symmetric group of the $n$-cube that

$Tf(x)=\pm f(Px+b)\quad\text{for all $x\in[0,1]^{n}$,}$

for an $n\times n$ signed permutation matrix $P$ (in the sense that exactly
one entry in each row and each column is $\pm 1$, and elsewhere $0$), and a
vector $b\in\mathbb{R}^{n}$ in which all entries are either $0$ or $1$.

(e) There are similar versions for bounded Lipschitz functions in all above
examples. The conclusions are identical.

##  3\. Weighted composition operators preserving local/pointwise Lipschitz
constants

We say that a weighted composition operator $Tf=h\cdot f\circ\varphi$ from
$\mathrm{Lip}^{\mathrm{loc}}(X)$ into $\mathrm{Lip}^{\mathrm{loc}}(Y)$, or
from $\mathrm{Lip}^{\mathrm{pt}}(X)$ into $\mathrm{Lip}^{\mathrm{pt}}(Y)$,
preserves the local or pointwise Lipschitz constants (with respect to
$\varphi$), if

$L^{\mathrm{loc}}_{p}(Tf)=L^{\mathrm{loc}}_{\varphi(p)}(f)\quad\text{for all
$f\in\mathrm{Lip}(X)$ and all $p\in Y$,}$

or

$L^{\mathrm{pt}}_{p}(Tf)=L^{\mathrm{pt}}_{\varphi(p)}(f)\quad\text{for all
$f\in\mathrm{Lip}(X)$ and all $p\in Y$.}$

In this section we consider weighted composition operators between
locally/pointwise Lipschitz functions on Euclidean spaces preserving
local/pointwise Lipschitz constants.

######  Proposition 3.1.

Let $(X,d_{X})$ and $(Y,d_{Y})$ be metric spaces without isolated point, and
let $\varphi:Y\to X$ be a map. Suppose that

$f\circ\varphi\in\mathrm{Lip}^{\mathrm{loc}}(Y)\ \text{{\rm(}resp.\
$\mathrm{Lip}^{\mathrm{pt}}(Y)${\rm)} \quad for all
$f\in\mathrm{Lip}^{\mathrm{loc}}(X)$ {\rm(}resp.\
$\mathrm{Lip}^{\mathrm{pt}}(X)${\rm)}.}$

Then $\varphi$ is locally (resp. pointwise) Lipschitz from $Y$ into $X$. If
the composition map $f\mapsto f\circ\varphi$ preserves local (resp. pointwise)
Lipschitz constants then $L^{\mathrm{loc}}_{q}(\varphi)=1$ (resp.
$L^{\mathrm{pt}}_{q}(\varphi)=1$) for every $q\in Y$.

###### Proof.

Let $q\in Y$, and let $f_{q}(x)=\min\\{d_{X}(x,\varphi(q)),1\\}$. Then $f_{q}$
is bounded and pointwise Lipschitz on $X$. In particular,
$L^{\mathrm{pt}}_{\varphi(q)}(f_{q})=1$. Since $q$ is not an isolated point in
$Y$, we see that $d_{X}(\varphi(y),\varphi(q))<1$ eventually when $y\to q$.
Hence,

$\displaystyle L^{\mathrm{pt}}_{q}(f_{q}\circ\varphi)$
$\displaystyle=\limsup_{y\to
q}\frac{|f_{q}(\varphi(y))-f_{q}(\varphi(q))|}{d_{Y}(y,q)}$
$\displaystyle=\limsup_{y\to
q}\frac{\min\\{d_{X}(\varphi(y),\varphi(q)),1\\}}{d_{Y}(y,q)}<+\infty.$

Thus,

$L^{\mathrm{pt}}_{q}(\varphi)=\limsup_{y\to
q}\frac{d_{X}(\varphi(y),\varphi(q))}{d_{Y}(y,q)}=L^{\mathrm{pt}}_{q}(f_{q}\circ\varphi)<+\infty.$

Since this holds for every point $q$ in $Y$, we see that $\varphi$ is
pointwise Lipschitz from $Y$ into $X$. Moreover,
$L^{\mathrm{pt}}_{q}(\varphi)=1$ for all $q\in Y$ if the composition map
$f\mapsto f\circ\varphi$ preserves pointwise Lipschitz constants.

The case for local Lipschitzness is proved in [5, Lemma 3.15]. As an
alternative proof, consider

$\displaystyle L^{\mathrm{loc}}_{\varphi(q)}(f_{q})$
$\displaystyle=\limsup_{y,z\to\varphi(q)}\frac{|f_{q}(y)-f_{q}(z)|}{d_{X}(y,z)}$
$\displaystyle\leq\limsup_{y,z\to\varphi(q)}\frac{|d_{X}(y,\varphi(q))-d_{X}(z,\varphi(q))|}{d_{X}(y,z)}\leq
1,$

while, in general,

$L^{\mathrm{loc}}_{\varphi(q)}(f_{q})\geq
L^{\mathrm{pt}}_{\varphi(q)}(f_{q})=1.$

Thus, $L^{\mathrm{loc}}_{\varphi(q)}(f_{q})=1$. In a similar fashion, we can
verify that $\varphi$ is locally Lipschitz, and
$L^{\mathrm{loc}}_{q}(\varphi)=1$ when the composition map $f\mapsto
f\circ\varphi$ preserves local Lipschitz constants. ∎

######  Lemma 3.2.

Let $\varphi:[a,b]\to\mathbb{R}$ be a locally (resp. pointwise) Lipschitz
function satisfying that

$L^{\mathrm{loc}}_{p}(\varphi)=\alpha\quad\text{(resp.\
$L^{\mathrm{pt}}_{p}(\varphi)=\alpha$)},\quad\text{for all $p\in[a,b]$.}$

If $\alpha=0$ then $\varphi(x)=c$ for some fixed scalar $c$. In general, if
$\varphi$ is injective then $\varphi(x)=\alpha x+c$ or $\varphi(x)=-\alpha
x+c$ on $[a,b]$ for some fixed scalar $c$.

###### Proof.

Suppose

$L_{p}^{\mathrm{loc}}(\varphi)=\limsup_{\begin{subarray}{c}x,y\to p\\\
x,y\in[a,b]\end{subarray}}\frac{|\varphi(x)-\varphi(y)|}{|x-y|}=\alpha\quad\text{for
all $p\in[a,b]$.}$

Let $\epsilon>0$. For any point $p\in[a,b]$, there is an open interval
$B(p,\delta_{p})$ centered at $p$ with radius $\delta_{p}>0$ such that

$\frac{|\varphi(x)-\varphi(y)|}{|x-y|}<\alpha+\epsilon\quad\text{for all
$x,y\in B(p,\delta_{p})\cap[a,b]$.}$

By the Lebesgue’s number lemma, there is a $\delta>0$ such that for any
partition $[a,b]=\bigcup_{i=1}^{m}[x_{i-1},x_{i}]$ with all
$|x_{i}-x_{i-1}|<\delta$, we have $x_{i-1},x_{i}\in B(p_{i},\delta_{p_{i}})$
for some $p_{i}\in[a,b]$, and thus

$\displaystyle\sum_{i=1}^{m}|\varphi(x_{i})-\varphi(x_{i-1})|<$
$\displaystyle\sum_{i=1}^{m}(\alpha+\epsilon)|x_{i}-x_{i-1}|$ (3.1)
$\displaystyle=$ $\displaystyle(\alpha+\epsilon)(b-a)<+\infty.$

In particular, $\varphi$ is of bounded variation on $[a,b]$. Consequently,
$\varphi$ is differentiable almost everywhere in $[a,b]$, and
$|\varphi^{\prime}(p)|=\alpha$ for almost all $p\in[a,b]$. If $\alpha=0$ then
$\varphi$ assumes constant value $c$ on $[a,b]$.

Suppose $\varphi$ is injective now. Since $\varphi$ is continuous and
injective, it is monotone on $[a,b]$. Thus, $\varphi^{\prime}=\alpha$ or
$\varphi^{\prime}=-\alpha$ almost everywhere on $[a,b]$. Hence, in the sense
of Lebesgue integral,

$\displaystyle\varphi(x)-\varphi(a)=\int_{a}^{x}\varphi^{\prime}(t)\,dt=\pm\alpha(x-a).$

Consequently, $\varphi(x)=\alpha x+c$ or $\varphi(x)=-\alpha x+c$ on $[a,b]$,
where $c=\mp\alpha a+\varphi(a)$.

The other case when

$L^{\mathrm{pt}}_{p}(\varphi)=\limsup_{x\to
p}\frac{|\varphi(x)-\varphi(p)|}{|x-p|}=\alpha,\quad\text{for all
$p\in[a,b]$,}$

follows similarly, except that in (3.1) we might break
$|\varphi(x_{i})-\varphi(x_{i-1})|\leq|\varphi(x_{i})-\varphi(p_{i})|+|\varphi(p_{i})-\varphi(x_{i-1})|$
where $x_{i-1},x_{i}\in B(p_{i};\delta_{p_{i}})$. ∎

The following example tells us that the injectivity condition is
indispensable.

######  Example 3.3.

Define $\varphi:[0,1]\to[\frac{1}{2},1]$ by

$\varphi(x)=\left\\{\begin{array}[]{ll}x,&\frac{1}{2}\leq x\leq 1,\\\
1-x,&0\leq x\leq\frac{1}{2}.\end{array}\right.$

Then $L^{\mathrm{loc}}_{x}(\varphi)=1$ for all $x\in[0,1]$. But $\varphi$ is
not linear.

######  Lemma 3.4.

Let $V$ be either an open connected set or a convex body in a normed linear
space. Let $h$ be locally or pointwise Lipschitz function on $V$ with
$L^{\mathrm{loc}}_{q}(h)=0$ or $L^{\mathrm{pt}}_{q}(h)=0$ for all $q\in V$.
Then $h$ is a constant function on $V$.

###### Proof.

Suppose $h\in\mathrm{Lip}^{\mathrm{pt}}(V)$ with $L^{\mathrm{pt}}_{q}(h)=0$
for all $q\in V$. Let $(1-t)x+ty$ for $t\in[0,1]$ be a path lying in the
interior of $V$. Define $f:[0,1]\to\mathbb{R}$ by $f(t)=h((1-t)x+ty)$. Then
$f\in\mathrm{Lip}^{\mathrm{pt}}([0,1])$ with $L^{\mathrm{pt}}(f)(t)=0$ for all
$t\in[0,1]$. By Lemma 3.2, $f$ is a constant function. In other words,
$h(x)=h(y)$. A connected argument shows that $h$ is constant on $V$ if $V$ is
open and connected. If $V$ is a convex body, then we can see that $h$ is
constant on the interior of $V$. By continuity, $h$ is constant on $V$. ∎

We also have the following well known results.

######  Proposition 3.5 (Rademacher/Stepanov Theorem; see, e.g., [3, 8]).

Let $V$ be an open subset of $\mathbb{R}^{n}$. Every locally/pointwise
Lipschitz function
$\varphi(x)=(\varphi_{1}(x),\varphi_{2}(x),\cdots,\varphi_{n}(x))$ from $V$
into $\mathbb{R}^{n}$ is differentiable on $V$ almost everywhere. In
particular, for every $v\neq 0$ in $\mathbb{R}$, the directional derivative
$D_{v}\varphi_{i}(x)=v\cdot\nabla\varphi_{i}(x)$ exists for almost every $x$
in $V$ for $i=1,2,\cdots,n$.

######  Theorem 3.6.

Let $U$ and $V$ be two open connected sets or two convex bodies in
$\mathbb{R}^{n}$. Let
$T:\mathrm{Lip}^{\mathrm{loc}}(U)\to\mathrm{Lip}^{\mathrm{loc}}(V)$ (resp.
$T:\mathrm{Lip}^{\mathrm{pt}}(U)\to\mathrm{Lip}^{\mathrm{pt}}(V)$) be a
bijective weighted composition operator defined by $Tf=h\cdot f\circ\varphi$
preserving local (resp. pointwise) Lipschitz constants. Then $h$ assumes
constant value $\pm\alpha^{-1}$ on $V$ for some $\alpha>0$, and $\varphi$
assumes the form $\varphi(v)=\alpha Av+b$ for an $n\times n$ orthogonal matrix
$A$ and a point $b\in\mathbb{R}^{n}$.

###### Proof.

We present the proof for the case when $U,V$ are open connected sets in
$\mathbb{R}^{2}$, and
$T:\mathrm{Lip}^{\mathrm{loc}}(U)\to\mathrm{Lip}^{\mathrm{loc}}(V)$ preserves
local Lipschitz constants. The other cases follow similarly.

It is clear that $\varphi$ is injective and $\varphi(V)$ is a dense subset of
$U$. Since $h=T\mathbf{1}_{U}$ is locally Lipschitz with
$L^{\mathrm{loc}}_{\varphi(p)}(h)=L^{\mathrm{loc}}_{p}(\mathbf{1}_{U})=0$ for
all $p\in V$, we see that $h=\pm\alpha^{-1}$ is a constant function for some
$\alpha>0$ by Lemma 3.4. It then follows from Proposition 3.1 that both
$\varphi$ and $\varphi^{-1}$ are locally Lipschitz.

We write $\varphi(x,y)=(\varphi_{1}(x,y),\varphi_{2}(x,y))$. It follows from
Proposition 3.5 that all partial derivatives
$\dfrac{\partial\varphi_{1}}{\partial x}$,
$\dfrac{\partial\varphi_{1}}{\partial y}$,
$\dfrac{\partial\varphi_{2}}{\partial x}$ and
$\dfrac{\partial\varphi_{2}}{\partial y}$ exist, and
$L^{\mathrm{loc}}_{(x,y)}(\varphi_{i})=\|\nabla\varphi_{i}(x,y)\|$ for
$i=1,2$, for almost every point $(x,y)$ in $V$. Let $I_{1}(x,y)=x$ and
$I_{2}(x,y)=y$. Then $I_{1}$ and $I_{2}$ belong to
$\mathrm{Lip}^{\mathrm{loc}}(V)$ with
$L^{\mathrm{loc}}_{(x,y)}(I_{1})=L^{\mathrm{loc}}_{(x,y)}(I_{2})=1$. It
follows that

$\alpha^{-1}L^{\mathrm{loc}}_{\varphi(x,y)}(\varphi_{1})=L^{\mathrm{loc}}_{\varphi(x,y)}(h\cdot
I_{1}\circ\varphi)=L^{\mathrm{loc}}_{(x,y)}(I_{1})=1$

for almost every point $(x,y)$ in $V$. Thus

$(\frac{\partial\varphi_{1}}{\partial
x}(x,y))^{2}+(\frac{\partial\varphi_{1}}{\partial y}(x,y))^{2}=\alpha^{2}.$

Dealing with $I_{2}$ instead, we also have

$(\frac{\partial\varphi_{2}}{\partial
x}(x,y))^{2}+(\frac{\partial\varphi_{2}}{\partial y}(x,y))^{2}=\alpha^{2}$

for almost all $(x,y)$ in $V$.

In general, for any $f$ in $\mathrm{Lip}^{\mathrm{loc}}(U)$, by Proposition
3.5 we have

$L^{\mathrm{loc}}_{(u,v)}(f)=\sqrt{\left(\frac{\partial f}{\partial
x}\right)^{2}+\left(\frac{\partial f}{\partial y}\right)^{2}}_{\mid(u,v)}$

for almost every $(u,v)$ in $U$. Now let $f(x,y)=xy$ in
$\mathrm{Lip}^{\mathrm{loc}}(U)$. We have
$L^{\mathrm{loc}}_{(u,v)}(f)=\sqrt{v^{2}+u^{2}}$ for all $(u,v)$ in $U$. In
particular,

$L^{\mathrm{loc}}_{\varphi(x,y)}(f)=\sqrt{\varphi_{1}(x,y)^{2}+\varphi_{2}(x,y)^{2}}\quad\text{for
all $(x,y)$ in $U$.}$

Hence

$\displaystyle\alpha\sqrt{\varphi_{1}^{2}+\varphi_{2}^{2}}\mid_{(x,y)}$
$\displaystyle=\alpha L^{\mathrm{loc}}_{\varphi(x,y)}(f)$
$\displaystyle=\alpha
L^{\mathrm{loc}}_{(x,y)}(Tf)=L^{\mathrm{loc}}_{(x,y)}(\varphi_{1}(x,y)\varphi_{2}(x,y))$
$\displaystyle=\sqrt{(\frac{\partial\varphi_{1}}{\partial
x}\varphi_{2}+\frac{\partial\varphi_{2}}{\partial
x}\varphi_{1})^{2}+(\frac{\partial\varphi_{1}}{\partial
y}\varphi_{2}+\frac{\partial\varphi_{2}}{\partial
y}\varphi_{1})^{2}}\mid_{(x,y)}$
$\displaystyle=\sqrt{\alpha^{2}(\varphi_{1}^{2}+\varphi_{2}^{2})+2(\frac{\partial\varphi_{1}}{\partial
x}\frac{\partial\varphi_{2}}{\partial x}+\frac{\partial\varphi_{1}}{\partial
y}\frac{\partial\varphi_{2}}{\partial y})\varphi_{1}\varphi_{2}}\mid_{(x,y)}$

for almost all $(x,y)$ in $V$. This implies

$\frac{\partial\varphi_{1}}{\partial
x}(x,y)\frac{\partial\varphi_{2}}{\partial
x}(x,y)+\frac{\partial\varphi_{1}}{\partial
y}(x,y)\frac{\partial\varphi_{2}}{\partial y}(x,y)=0$

for almost all $(x,y)$ in $V$. Therefore,

$D[\varphi]_{\mid(x,y)}=\left(\begin{array}[]{cc}\dfrac{\partial\varphi_{1}}{\partial
x}&\dfrac{\partial\varphi_{1}}{\partial y}\\\
\dfrac{\partial\varphi_{2}}{\partial x}&\dfrac{\partial\varphi_{2}}{\partial
y}\\\ \end{array}\right)_{\mid(x,y)}$

exists, and $\alpha^{-1}D[\varphi]_{\mid(x,y)}$ is an orthogonal matrix for
almost all $(x,y)$ in $V$.

For any two points $(x_{1},y_{1})$ and $(x_{2},y_{2})$ in an open ball $B$
contained in $V$, let $C:[0,1]\to V$ be any smooth curve in $B$ joining
$(x_{1},y_{1})$ to $(x_{2},y_{2})$. Using Lebesgue integration, we have

$\displaystyle\|\varphi(x_{1},y_{1})-\varphi(x_{2},y_{2})\|$
$\displaystyle\leq\int_{0}^{1}\|\frac{d}{dt}(\varphi(C(t)))\|\,dt$
$\displaystyle=\int_{0}^{1}\|D[\varphi(C(t))]\frac{d}{dt}C(t)\|\,dt=\alpha\int_{0}^{1}\|\frac{d}{dt}C(t)\|\,dt.$

Hence, taking infimum over all such smooth curves $C$, we have

$\|\varphi(x_{1},y_{1})-\varphi(x_{2},y_{2})\|\leq\alpha\|(x_{1},y_{1})-(x_{2},y_{2})\|.$

In particular, the injective map $\varphi$ is continuous on the open set
$V\subset\mathbb{R}^{n}$. By the invariance of domain, $U_{0}=\varphi(V)$ is
an open dense subset of the open set $U\subset\mathbb{R}^{n}$. It is clear
that $T^{-1}g\mid_{U_{0}}=\alpha g\circ\varphi^{-1}$ preserves local Lipschitz
constants. By a similar argument, we have $\alpha D[\varphi^{-1}]_{\mid q}$
exists as an orthogonal matrix for almost every point $q\in U_{0}$. Hence, the
reverse inequality

$\|\varphi(x_{1},y_{1})-\varphi(x_{2},y_{2})\|\geq\alpha\|(x_{1},y_{1})-(x_{2},y_{2})\|$

also holds. In other words, $\varphi$ is an $\alpha$-dilation from $B$ onto
$\varphi(B)$ for any open ball $B$ contained in $V$. It follows from
Proposition 2.1 that $\varphi\\!\mid_{B}$ can be uniquely extended to an
$\alpha$-dilation from $\mathbb{R}^{n}$ onto itself. By a connectedness
argument, we see that $\varphi$ can be extended uniquely to the same
$\alpha$-dilation of $\mathbb{R}^{n}$ onto itself. In other words,
$\varphi(v)=\alpha Av+b$ for an $n\times n$ orthogonal matrix $A$ and a vector
$b\in\mathbb{R}^{n}$, as asserted. ∎

######  Example 3.7.

Let
$T:\mathrm{Lip}^{\mathrm{loc}}([0,1]^{n})\to\mathrm{Lip}^{\mathrm{loc}}([0,1]^{n})$
be a bijective weighted composition operator preserving local Lipschitz
constants. Then

$Tf=\pm f(Px+b),$

where $P$ is an $n\times n$ signed permutation matrix and $b\in\mathbb{R}^{n}$
has entries either $0$ or $1$.

######  Example 3.8.

Let
$T:\mathrm{Lip}^{\mathrm{loc}}([a,b])\to\mathrm{Lip}^{\mathrm{loc}}([c,d])$
defined by $Tf=h\cdot f\circ\varphi$ be a bijection and preserve local
Lipschitz constants. Then $h=\frac{d-c}{b-a}$ or $h=-\frac{d-c}{b-a}$ and
$\varphi(x)=\frac{b-a}{d-c}(x-c)+a$ or $\varphi(x)=\frac{b-a}{d-c}(d-x)+a$.

##  4\. Local/pointwise Lipschitz constant preservers of flat manifolds

In this section we consider locally (resp. pointwise) Lipschitz functions
defined on flat manifolds. A _flat manifold_ of dimension $n$ is a set $M$
with a family of injective mappings, called _charts_ ,
$\phi_{\alpha}:U_{\alpha}\subseteq\mathbb{R}^{n}\to\phi_{\alpha}(U_{\alpha})\subseteq
M$ of open connected sets $U_{\alpha}$ containing $0$ such that:

  1. (1)

$M\subseteq\cup_{\alpha}\phi_{\alpha}(U_{\alpha})$;

  2. (2)

For any pair $\alpha$, $\beta$ with
$W=\phi_{\alpha}(U_{\alpha})\cap\phi_{\beta}(U_{\beta})\neq\emptyset$, the
transition map $\phi_{\alpha}^{-1}\circ\phi_{\beta}|_{\phi_{\beta}^{-1}(W)}$
is a diffeomorphism from $\phi_{\beta}^{-1}(W)$ onto $\phi_{\alpha}^{-1}(W)$,
and $D[\phi_{\alpha}^{-1}\circ\phi_{\beta}]$ is orthogonal matrix-valued
everywhere;

  3. (3)

The family $\\{(U_{\alpha},\phi_{\alpha})\\}_{\alpha}$ is maximal with respect
to the conditions (1) and (2).

For example, lines, circles, planes, spheres and the Möbius strip are all flat
manifolds. Note that a flat manifold becomes a metric space when it is
equipped with the geodesic distance between points.

######  Definition 4.1.

Let $M$ be a flat manifold of dimension $n$. A function $f:M\to\mathbb{R}$ is
_locally_ (resp.  _pointwise_) _Lipschitz_ if for all $p$ in $M$, there is a
chart $\phi_{p}:U\subseteq\mathbb{R}^{n}\to\phi_{p}(U)\subseteq M$ with
$\phi_{p}(0)=p$ such that
$f\circ\phi_{p}:U\subseteq\mathbb{R}^{n}\to\mathbb{R}$ is locally (resp.
pointwise) Lipschitz at $0$. Moreover, we define the _local_ (resp.
_pointwise_) _Lipschitz constant_ of $f$ at $p$ by
$L^{\mathrm{loc}}_{p}(f)=L^{\mathrm{loc}}_{0}(f\circ\phi_{p})$ (resp.
$L^{\mathrm{pt}}_{p}(f)=L^{\mathrm{pt}}_{0}(f\circ\phi_{p})$).

######  Lemma 4.2.

Let $M$ be a flat manifold. A function $f:M\to\mathbb{R}$ is locally (resp.
pointwise) Lipschitz at $p$ with respect to a chart $(\phi_{p},U)$ is
equivalent to the same property with respect to another chart $(\psi_{p},V)$
at $p$. Indeed, we have
$L^{\mathrm{loc}}_{0}(f\circ\phi_{p})=L^{\mathrm{loc}}_{0}(f\circ\psi_{p})$
(resp.
$L^{\mathrm{pt}}_{0}(f\circ\phi_{p})=L^{\mathrm{pt}}_{0}(f\circ\psi_{p})$).

###### Proof.

Let $W=\phi_{p}(U)\cap\psi_{p}(V)$. Observe that

$L^{\mathrm{pt}}_{0}(f\circ\phi_{p})=L^{\mathrm{pt}}_{0}(f\circ\phi_{p}\mid_{\phi_{p}^{-1}(W)})\quad\text{and}\quad
L^{\mathrm{pt}}_{0}(f\circ\psi_{p})=L^{\mathrm{pt}}_{0}(f\circ\psi_{p}\mid_{\psi_{p}^{-1}(W)}).$

It follows

$\displaystyle L^{\mathrm{pt}}_{0}(f\circ\phi_{p})$
$\displaystyle=L^{\mathrm{pt}}_{0}(f\circ\psi_{p}\circ\psi_{p}^{-1}\circ\phi_{p}\mid_{\phi_{p}^{-1}(W)})$
$\displaystyle\leq L^{\mathrm{pt}}_{0}(f\circ\psi_{p})\cdot
L^{\mathrm{pt}}_{0}(\psi_{p}^{-1}\circ\phi_{p}\mid_{\phi_{p}^{-1}(W)})=L^{\mathrm{pt}}_{0}(f\circ\psi_{p})$

and

$\displaystyle L^{\mathrm{pt}}_{0}(f\circ\psi_{p})$
$\displaystyle=L^{\mathrm{pt}}_{0}(f\circ\phi_{p}\circ\phi_{p}^{-1}\circ\psi_{p}\mid_{\psi_{p}^{-1}(W)})$
$\displaystyle\leq L^{\mathrm{pt}}_{0}(f\circ\phi_{p})\cdot
L^{\mathrm{pt}}_{0}(\phi_{p}^{-1}\circ\psi_{p}\mid_{\psi_{p}^{-1}(W)})=L^{\mathrm{pt}}_{0}(f\circ\phi_{p}).$

Hence
$L^{\mathrm{pt}}_{0}(f\circ\phi_{p})=L^{\mathrm{pt}}_{0}(f\circ\psi_{p})$.

The case for the local Lipschitz constants is similar. ∎

######  Theorem 4.3.

Let $M$, $N$ be two $n$-dimensional flat manifolds. Let $\sigma:N\to M$ such
that the composition operator $Tf=f\circ\sigma$ defines a bijective linear map
$T:\mathrm{Lip}^{\mathrm{pt}}(M)\rightarrow\mathrm{Lip}^{\mathrm{pt}}(N)$
satisfying that $L^{\mathrm{pt}}_{x}(Tf)=L^{\mathrm{pt}}_{\sigma(x)}(f)$
(resp.
$T:\mathrm{Lip}^{\mathrm{loc}}(M)\rightarrow\mathrm{Lip}^{\mathrm{loc}}(N)$
satisfying that $L^{\mathrm{loc}}_{x}(Tf)=L^{\mathrm{loc}}_{\sigma(x)}(f)$)
for all $x$ in $N$. Then $\sigma$ is a local isometry in the sense that for
any point $p\in N$, and any chart $\phi:U\to M$ of $\sigma(p)$ and $\psi:V\to
N$ of $p$ such that $\sigma(\psi(V))\subseteq\phi(U)$, the induced map
$\phi^{-1}\circ\sigma\circ\psi:V\to U$ is an isometry.

###### Proof.

Let $p$ be in $N$, equipped with charts $\phi:U\to M$ and $\psi:V\to N$ such
that $\psi(0)=p$, $\phi(0)=\sigma(p)$ and $\sigma(\psi(V))\subseteq\phi(U)$.
Note that both $U,V$ are open and connected in $\mathbb{R}^{n}$. The
composition map
$T(g\circ\phi^{-1})\circ\psi=g\circ(\phi^{-1}\circ\sigma\circ\psi)$ defines a
bijection from $\mathrm{Lip}^{\mathrm{pt}}(U)$ onto
$\mathrm{Lip}^{\mathrm{pt}}(V)$ preserving the pointwise Lipschitz constants.
It follows from Theorem 3.6 that $\phi^{-1}\circ\sigma\circ\psi$ extends to an
isometry from $\mathbb{R}^{n}$ onto $\mathbb{R}^{n}$.

The case for local Lipschitz functions is similar. ∎

######  Example 4.4.

Let $S^{2}$ be the unit sphere in $\mathbb{R}^{3}$. Let
$T:\mathrm{Lip}^{\mathrm{pt}}(S^{2})\rightarrow\mathrm{Lip}^{\mathrm{pt}}(S^{2})$
be a bijection such that $Tf=f\circ\sigma$, and
$L^{\mathrm{pt}}_{p}(Tf)=L^{\mathrm{pt}}_{\sigma(p)}(f)$ for all $p\in S^{2}$.
By Theorem 4.3, $\sigma$ is a local isometry, and thus a surjective isometry
with respect to the geodesic metric on $S^{2}$.

######  Example 4.5.

Let $0<r<R$ and

$S^{1}\times S^{1}$ =
$\\{((R+r\cos\theta)\cos\phi,(R+r\cos\theta)\sin\phi,r\sin\theta)\in\mathbb{R}^{3}$
: $0\leq\theta\leq 2\pi$, $0\leq\phi\leq 2\pi$ $\\}$

be a $2$-dimensional torus. Let $T:\mathrm{Lip}^{\mathrm{pt}}(S^{1}\times
S^{1})\rightarrow\mathrm{Lip}^{\mathrm{pt}}(S^{1}\times S^{1})$ be a bijection
such that $Tf=f\circ\sigma$ and
$L^{\mathrm{pt}}_{p}(Tf)=L^{\mathrm{pt}}_{\sigma(p)}(f)$ for all $p\in
S^{1}\times S^{1}$. It follows from Theorem 4.3 that $\sigma$ is a local
isometry, and thus it is a surjective isometry of $S^{1}\times S^{1}$ in the
geodesic metric.

## References

  * [1] J. Araujo and L. Dubarbie, Biseparating maps between Lipschitz function spaces, J. Math. Anal. Appl. 357 (2009), no. 1, 191–200.
  * [2] E. Durand-Cartagena and J. A. Jaramillo, Pointwise Lipschitz functions on metric spaces, J. Math. Anal. Appl. 363 (2010), no. 2, 525–548.
  * [3] H. Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Vol. 153, Berlin–Heidelberg–New York, Springer-Verlag, 1969.
  * [4] R. J. Fleming and J. E. Jamison, Isometries on Banach spaces: function spaces, Monographs and Surveys in Pure and Applied Mathematics, 129, Boca Raton, Chapman $\&$ Hall/CRC, 2003.
  * [5] M. I. Garrido and J. A. Jaramillo, Homomorphisms on function lattices, Monatsh. Math. 141 (2004), no. 2, 127-146.
  * [6] L. Li and N.-C. Wong, Kaplansky theorem for completely regular spaces, Proc. Amer. Math. Soc. 142 (2014), no. 4, 1381-1389.
  * [7] C.-N. Liu, Lipschitz constant preserving maps, PhD Dissertation, National Sun Yat-sen University, Kaohsiung, Taiwan, 2015. https://ethesys.lis.nsysu.edu.tw/eThesys-dbs/ETD-search/getfile-2.php?URN=etd-0705115-095101&filename=etd-0705115-095101.pdf
  * [8] J. Maly, A simple proof of the Stepanov theorem on differentiability almost everywhere, Exposition Math. 17 (1999), no. 1, 59–61.
  * [9] P. Mankiewicz, On extension of isometries in normed linear spaces, Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 20 (1972), 367-371.
  * [10] E. Mayer-Wolf, Isometries between Banach spaces of Lipschtiz functions, Israel J. Math. 38 (1981), 837-842.
  * [11] N. Weaver, Isometries of noncompact Lipschitz spaces, Canad. Math. Bull. 38 (1995), no. 2, 242-249.
  * [12] N. Weaver, Lipschitz Algebras, World Scientific, River Edge, NJ, 1999.
  * [13] T.-C. Wu, Disjointness preserving operators between Lipschitz spaces, Master Thesis, Kaohsiung, National Sun Yat-sen University, Kaohsiung, Taiwan, 2007. https://ethesys.lis.nsysu.edu.tw/eThesys-dbs/ETD-search/getfile-2.php?URN=etd-0903107-134219&filename=etd-0903107-134219.pdf