#  An FPTAS for Budgeted Laminar Matroid Independent Set

Ilan Doron-Arad Computer Science Department, Technion, Haifa, Israel.idoron-
<EMAIL_ADDRESS>Ariel Kulik CISPA Helmholtz Center for Information
Security, Germany<EMAIL_ADDRESS>Hadas Shachnai Computer Science
Department, Technion, Haifa, Israel<EMAIL_ADDRESS>
###### Abstract

We study the budgeted laminar matroid independent set problem. The input is a
ground set, where each element has a cost and a non-negative profit, along
with a laminar matroid over the elements and a budget. The goal is to select a
maximum profit independent set of the matroid whose total cost is bounded by
the budget. Several well known special cases, where we have, e.g., no matroid
constraint (the classic knapsack problem) or a uniform matroid constraint
(knapsack with a cardinality constraint), admit a fully polynomial-time
approximation scheme (FPTAS). In contrast, the budgeted matroid independent
set (BMI) problem with a general matroid has an efficient polynomial-time
approximation scheme (EPTAS) but does not admit an FPTAS. This implies an
EPTAS for our problem, which is the best known result prior to this work.

We present an FPTAS for budgeted laminar matroid independent set, improving
the previous EPTAS for this matroid family and generalizing the FPTAS known
for knapsack with a cardinality constraint and multiple-choice knapsack. Our
scheme is based on a simple dynamic program which utilizes the tree-like
structure of laminar matroids.

##  1 Introduction

Knapsack is one of the most fundamental problems in combinatorial
optimization, which has been continuously studied in the past half century.
[14, 24, 20, 3]. Considerable attention was given to a generalization of
knapsack including an additional matroid constraint [22, 4, 25, 23, 28, 1, 21,
10]. In this work we consider the knapsack problem with a laminar matroid
constraint.

A matroid is a set system $(S,{\mathcal{I}})$, where $S$ is a finite set and
${\mathcal{I}}\subseteq 2^{S}$ such that (i) $\emptyset\in{\mathcal{I}}$, (ii)
for all $A\in{\mathcal{I}}$ and $B\subseteq A$ it holds that
$B\in{\mathcal{I}}$, and (iii) for all $A,B\in{\mathcal{I}}$ where $|A|>|B|$
there is $e\in A\setminus B$ such that $B\cup\\{e\\}\in{\mathcal{I}}$. We
focus on the family of laminar matroids, defined below.

######  Definition 1.1.

Given a finite set $S$, ${\mathcal{F}}\subseteq 2^{S}\setminus\\{\emptyset\\}$
is a laminar family on $S$ if for any $X,Y\in{\mathcal{F}}$ one of the
following holds: $X\cap Y=\emptyset$, or $X\cap Y=X$, or $X\cap Y=Y$.

######  Definition 1.2.

Let ${\mathcal{F}}$ be a laminar family on a finite set $S$; also, let
$k:{\mathcal{F}}\rightarrow\mathbb{N}_{>0}$ and
${\mathcal{I}}_{{\mathcal{F}},k}=\\{A\subseteq S~{}:~{}|A\cap X|\leq
k(X)~{}\forall X\in{\mathcal{F}}\\}$. Then
$(S,{\mathcal{I}}_{{\mathcal{F}},k})$ is a laminar matroid.

The independent sets ${\mathcal{I}}_{{\mathcal{F}},k}$ in the laminar matroid
$(S,{\mathcal{I}}_{{\mathcal{F}},k})$ are all subsets of elements $A$ such
that for any set $X\in{\mathcal{F}}$ in the laminar family, $|A\cap X|$ does
not violate the cardinality constraint $k(X)$. It is well known (see, e.g.,
[19, 13]) that laminar matroids are indeed matroids.

In this paper, we study the budgeted laminar matroid independent set (BLM)
problem. The input is a tuple $I=(S,{\mathcal{F}},k,c,p,B)$, where $S$ is a
finite set, ${\mathcal{F}}$ is a laminar family on $S$ such that
$S\in{\mathcal{F}}$, $k:{\mathcal{F}}\rightarrow\mathbb{N}_{>0}$ gives
cardinality bounds to ${\mathcal{F}}$, $c:S\rightarrow\mathbb{N}$ is a cost
function, $p:S\rightarrow\mathbb{N}$ is a profit function, and
$B\in\mathbb{N}$ is a budget. A solution of $I$ is an independent set
$T\in{\mathcal{I}}_{{\mathcal{F}},k}$ of the laminar matroid
$(S,{\mathcal{I}}_{{\mathcal{F}},k})$ such that $c(T)=\sum_{e\in T}c(e)\leq
B$. The goal is to find a solution $T$ of $I$ such that $p(T)=\sum_{e\in
T}p(e)$ is maximized.

There are a few notable special cases of BLM; we use our notation to formally
define them. Consider an instance $I$ of BLM. If
${\mathcal{F}}\setminus\\{S\\}$ is a partition of $S$ and $k(S)\geq|S|$ then
$(S,{\mathcal{I}}_{{\mathcal{F}},k})$ is a partition matroid, and we say that
$I$ is a knapsack with partition matroid instance.111Adding the constraint
$k(S)\geq|S|$ is purely technical to instantiate a partition matroid using BLM
notation. Moreover, the special case of knapsack with partition matroid where
$k(X)=1~{}\forall X\in({\mathcal{F}}\setminus\\{S\\})$ is the multiple-choice
knapsack [28]. Alternatively, if ${\mathcal{F}}=\\{S\\}$ then
$(S,{\mathcal{I}}_{{\mathcal{F}},k})$ is a uniform matroid, and $I$ is a
cardinality constrained knapsack instance [22].

A natural application of BLM arises in the context of cloud computing, where
limited network bandwidth limit plays a vital role (see, e.g., [29, 27, 26]).
Consider a network $G=(V,E)$, that is a directed tree with a root $M$
associated with a cloud computer. Each leaf in $G$ represents a client. Each
client sends a job to $M$, which can process the job and broadcast the results
through the network back to the client. The jobs have processing times and
values. Also, $M$ has a bound on the total processing time of admitted jobs.
Moreover, each node $v\in V$ in the network has a limited bandwidth, $k(v)$,
so that $v$ can broadcast the results of at most $k(v)$ jobs to its descendant
clients. The goal is to maximize the total value of complete jobs subject to
the processing time and bandwidth bounds.

We can cast this problem as a BLM instance by taking the set of elements $S$
to be the se of jobs, where the profit and cost of each element are the value
and processing time of the corresponding job. Now, we define a laminar family
${\mathcal{F}}$ on the set of elements, where for each vertex $v\in V$ there
is a set $X_{v}\in{\mathcal{F}}$ containing all jobss that belong to clients
(i.e., leaves) in the subtree rooted by $v$, where the cardinality bound of
$X_{v}$ is the bandwidth limit $k(X_{v})=k(v)$. For other applications of
laminar matroids, see e.g., [13, 15, 19].

We focus in this paper on approximation schemes for BLM. Let
$\textnormal{OPT}(I)$ be the value of an optimal solution for an instance $I$
of a maximization problem $\Pi$. For $\alpha\in(0,1]$, we say that
${\mathcal{A}}$ is an $\alpha$-approximation algorithm for $\Pi$ if, for any
instance $I$ of $\Pi$, ${\mathcal{A}}$ outputs a solution of value at least
$\alpha\cdot\textnormal{OPT}(I)$. A polynomial-time approximation scheme
(PTAS) for $\Pi$ is a family of algorithms
$(A_{{\varepsilon}})_{{\varepsilon}>0}$ such that, for any ${\varepsilon}>0$,
$A_{{\varepsilon}}$ is a polynomial-time $(1-{\varepsilon})$-approximation
algorithm for $\Pi$. An efficient PTAS (EPTAS) is a PTAS
$(A_{{\varepsilon}})_{{\varepsilon}>0}$ with running time of the form
$f\left(\frac{1}{{\varepsilon}}\right)\cdot|I|^{O(1)}$, where $f$ is an
arbitrary computable function. The running time of an EPTAS might be
impractically high; this motivates the study of the following important
subclass of EPTAS: $(A_{{\varepsilon}})_{{\varepsilon}>0}$ is a fully PTAS
(FPTAS) if the running time of $A_{{\varepsilon}}$ is of the form
${\left(\frac{|I|}{{\varepsilon}}\right)}^{O(1)}$.

$0/1$-knapsack FPTASMultiple-choice knapsack FPTASCardinality constrained
knapsack FPTASKnapsack with partition matroid FPTASBudgeted laminar matroid
independent set (BLM) FPTAS (this paper)Budgeted matroid independent set
EPTAS, no FPTAS unless P=NP Figure 1: Complexity of knapsack generalizations
with various families of matroid constraints.

We note that budgeted independent set with a general matroid constraint admits
an EPTAS; however, the existence of an FPTAS was ruled out [11]. In contrast,
well known special cases of BLM such as cardinality constrained knapsack [22]
and multiple-choice knapsack [28] admit FPTAS. The question whether budgeted
independent set admits an FPTAS on other classes of matroids (e.g., laminar,
graphic, or linear matroid) remained open.

In this paper we resolve this open question for laminar matroids. Our main
result is an FPTAS for BLM, improving upon the existing EPTAS for this family,
and generalizing the FPTAS for the special cases of cardinality constrained
knapsack and multiple-choice knapsack. Specifically,

######  Theorem 1.3.

There is an algorithm FPTAS that given a BLM instance $I$ and
${\varepsilon}>0$ finds in time $O\left(|I|^{5}\cdot{\varepsilon}^{-2}\right)$
a solution $T$ for $I$ of profit
$p(T)\geq(1-{\varepsilon})\cdot\textnormal{OPT}(I)$.

We give in Figure 1 a complexity overview of the related problems. To derive
an FPTAS, we first find a pseudo-polynomial time algorithm for BLM. Our
technique is based on dynamic programming (DP), which exploits the tree-like
structure of laminar matroids. More concretely, let
$I=(S,{\mathcal{F}},k,c,p,B)$ be a BLM instance and $X\in{\mathcal{F}}$ a
maximal set in the laminar family, not contained in any other set except for
$S$. We first construct (recursively) DP tables for elements contained in $X$
and separately for elements contained in $S\setminus X$. Then, we combine the
two DP tables into a DP table for the original instance $I$. We rely on the
key property that combining any two independent sets $T_{1}\subseteq X$ and
independent set $T_{2}\subseteq S\setminus X$ yields an independent set
$T_{1}\cup T_{2}$ as long as the overall cardinality (i.e., $|T_{1}\cup
T_{2}|$) satisfies the cardinality bound of $S$. Finally, our FPTAS is
obtained by standard rounding of the profits. We remark that we did not
attempt to optimize the running time; instead, our goal is to obtain a simple
FPTAS for the problem.

###  1.1 Related Work

BLM is an immediate generalization of the classic $0/1$-knapsack problem.
While the knapsack problem is known to be NP-hard, it admits an FPTAS. Other
notable special cases of BLM that admit an FPTAS include cardinality
constrained knapsack [22, 4, 25, 23] and multiple choice knapsack [28, 1, 21].

Chakaravarthy et al. [5] considered the knapsack cover with a matroid
constraint (KCM) problem, which is dual to budgeted matroid independent set.
In this variant, we are given a matroid ${\mathcal{M}}=(S,{\mathcal{I}})$, a
cost function $c:S\rightarrow\mathbb{R}_{\geq 0}$, a size function
$s:S\rightarrow\mathbb{R}_{\geq 0}$, and a demand $D\in\mathbb{R}_{\geq 0}$.
The goal is to find $A\in{\mathcal{I}}$ such that $s(A)=\sum_{e\in A}s(e)\geq
D$ such that $c(A)=\sum_{e\in A}c(e)$ is minimized. They obtain a PTAS for a
general matroid ${\mathcal{M}}$, and an FPTAS when ${\mathcal{M}}$ is a
partition matroid. The constrained minimum spanning tree problem is a special
case of KCM where $(S,{\mathcal{I}})$ is a graphic
matroid.222$(S,{\mathcal{I}})$ is a graphic matroid if there is a graph
$G=(V,S)$ where ${\mathcal{I}}$ contains all the subsets $T\subseteq S$
satisfying $G^{\prime}=(V,T)$ is an acyclic graph. The constrained minimum
spanning tree problem admits an EPTAS [17] and an FPTAS which violates the
budget constraint by a factor of $(1+{\varepsilon})$ [18].

As BLM is a special case of the budgeted matroid independent set problem, a
PTAS for the problem follows from the works of [16, 6, 2]. An EPTAS for BMI
was recently presented in [10] and generalized for budgeted matroid
intersection in [9]. As shown in [11], this is the best possible.

###  1.2 Organization of the Paper

Section 2 gives preliminary results and notations. In Section 3 we give a
pseudo-polynomial time algorithm for BLM. Section 4 presents our FPTAS. We
conclude in Section 5 with a discussion.

##  2 Preliminaries

Given a set $S$, a function $f:S\rightarrow\mathbb{N}$, and $R\subseteq S$,
let $f(R)=\sum_{e\in R}f(e)$. Also, we sometimes use $f$ to denote a
restriction of $f$ to a subset of the domain $S^{\prime}\subseteq S$. Let
$I=(S,{\mathcal{F}},k,c,p,B)$ be a BLM instance; we use
${\mathcal{I}}(I)={\mathcal{I}}_{{\mathcal{F}},k}$ to denote the independent
sets of the instance. For some $G\subseteq S$ define ${\mathcal{F}}_{\subseteq
G}=\\{Y\in{\mathcal{F}}~{}|~{}Y\subseteq G\\}$ as all sets in ${\mathcal{F}}$
that are contained in $G$. We define below operations on $I$, generating
modified BLM instances. We say that a set $X\in{\mathcal{F}}\setminus\\{S\\}$
is a maximal set if it is not contained in any other set in
${\mathcal{F}}\setminus\\{S\\}$. For a maximal set
$X\in{\mathcal{F}}\setminus\\{S\\}$, define the BLM instances $I\cap
X=(X,{\mathcal{F}}_{\subseteq X},k,c,p,B)$ and $I\setminus X=\big{(}S\setminus
X,{\mathcal{F}}_{\subseteq(S\setminus X)}\cup\\{S\setminus
X\\},\bar{k},c,p,B\big{)}$ such that for all
$Y\in{\mathcal{F}}_{\subseteq(S\setminus X)}\cup\\{S\setminus X\\}$

$\bar{k}(Y)=\begin{cases}k(Y)~{}~{}&Y\in{\mathcal{F}}\\\
k(S),~{}~{}&\textnormal{otherwise}.\end{cases}$

Note that the only set $Y$ that potentially does not belong to ${\mathcal{F}}$
is $Y=S\setminus X$. Observe that $I\cap X$ and $I\setminus X$ can be viewed
as restrictions of $I$ to $X$ and $S\setminus X$, respectively. The next
observations follow from the above definitions and the properties of laminar
families.

######  Observation 2.1.

For a BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$ and a maximal set
$X\in({\mathcal{F}}\setminus\\{S\\})$ it holds that $I\cap X$ and $I\setminus
X$ are BLM instances.

We use $\uplus$ to denote disjoint union.

######  Observation 2.2.

For a BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$ and a maximal set
$X\in({\mathcal{F}}\setminus\\{S\\})$ the following holds.

  1. 1.

For any $Q_{1}\in{\mathcal{I}}(I\cap X)$ and $Q_{2}\in{\mathcal{I}}(I\setminus
X)$ such that $|Q_{1}\uplus Q_{2}|\leq k(S)$ it holds that $Q_{1}\uplus
Q_{2}\in{\mathcal{I}}(I)$.

  2. 2.

For any $Q\in{\mathcal{I}}(I)$ it holds that $Q\cap X\in{\mathcal{I}}(I\cap
X)$ and $Q\setminus X\in{\mathcal{I}}(I\setminus X)$.

##  3 A Pseudo-polynomial Time Algorithm

In this section we give a pseudo-polynomial time algorithm for BLM. Let
$I=(S,{\mathcal{F}},k,c,p,B)$ be a BLM instance, and define
$P_{I}=\\{0,1,\ldots,|S|\cdot\max_{e\in S}p(e)\\}$. Observe that for any
solution $T\subseteq S$ it holds that $p(T)\in P_{I}$. Also, there may be
$t\in P_{I}$ such that $t\neq p(T)$ for any $T\subseteq S$. Our algorithm
computes the following table.

######  Definition 3.1.

For any BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$, define the DP table of $I$
as the function $\textnormal{{DP}}_{I}:\\{0,....|S|\\}\times
P_{I}\to\mathbb{N}\cup\infty$ such that for all $q\in\\{0,1,\ldots,|S|\\}$ and
$t\in P_{I}$,

$\textnormal{{DP}}_{I}(q,t)=\min_{Q\in{\mathcal{I}}_{{\mathcal{F}},k}\textnormal{
s.t. }|Q|=q,~{}p(Q)=t}c(Q).$

For any $q\in\\{0,1,\ldots,|S|\\}$ and $t\in P_{I}$, the entry
$\textsf{DP}_{I}(q,t)$ gives the minimum cost of an independent set in
${\mathcal{I}}_{{\mathcal{F}},k}$ of exactly $q$ elements and profit equal to
$t$; if there is no such independent set then $\textsf{DP}_{I}(q,t)=\infty$.
Also, $\textsf{DP}_{I}(q,t)=\infty$ if $q$ or $t$ do not belong to the domain
of $\textsf{DP}_{I}$ (e.g., $q=|S|+1$).

We formulate a dynamic program which computes the table $\textsf{DP}_{I}$.
Informally, the table $\textsf{DP}_{I}$ is constructed by taking a maximal set
$X\in{\mathcal{F}}\setminus\\{S\\}$ in the laminar family (recall that a
maximal set is not a subset of any other set in
${\mathcal{F}}\setminus\\{S\\}$). Our algorithm computes the sub-tables
$\textsf{DP}_{I\cap X}$ and $\textsf{DP}_{I\setminus X}$ recursively. An
important observation is that the instances $I\cap X$ and $I\setminus X$ are
disjoint; thus, the table $\textsf{DP}_{I}$ can be computed from $DP_{I\cap
X}$ and $DP_{I\setminus X}$ using a convolution. Specifically, to compute an
entry $\textsf{DP}_{I}(q,t)$ for $q\in\\{0,1,\ldots,|S|\\}$ and $t\in P_{I}$,
we find the minimum solution induced by partitioning the values $q$ and $t$
between the complementary sub-instances $I\cap X$ and $I\setminus X$. This is
formalized by the next lemma.

######  Lemma 3.2.

Let $I=(S,{\mathcal{F}},k,c,p,B)$ be a BLM instance, and
$X\in{\mathcal{F}}\setminus\\{S\\}$ a maximal set. Then, for all
$q\in\\{0,1,\ldots,|S|\\}$ and $t\in P_{I}$,

$\textnormal{{DP}}_{I}(q,t)=\begin{cases}\min_{\begin{subarray}{c}q_{1},q_{2},t_{1},t_{2}\in\mathbb{N}\textnormal{
s.t. }\\\
q_{1}+q_{2}=q,~{}t_{1}+t_{2}=t\end{subarray}}\left\\{\textnormal{{DP}}_{I\cap
X}(q_{1},t_{1})+\textnormal{{DP}}_{I\setminus
X}(q_{2},t_{2})\right\\}~{}~{}&\textnormal{if}\ q\leq k(S)\\\
\infty~{}~{}&\textnormal{otherwise}\end{cases}$

###### Proof.

Let $q\in\\{0,1,\ldots,|S|\\}$ and $t\in P_{I}$. For simplicity, let

$M=\min_{\begin{subarray}{c}q_{1},q_{2},t_{1},t_{2}\in\mathbb{N}\textnormal{
s.t. }\\\
q_{1}+q_{2}=q,~{}t_{1}+t_{2}=t\end{subarray}}\left\\{\textnormal{{DP}}_{I\cap
X}(q_{1},t_{1})+\textnormal{{DP}}_{I\setminus X}(q_{2},t_{2})\right\\}.$

We first consider the case where $\textnormal{{DP}}_{I}(q,t)$ and $M$ differ
from $\infty$. We use the following auxiliary claims.

######  Claim 3.3.

If $\textnormal{{DP}}_{I}(q,t)\neq\infty$ then
$M\leq\textnormal{{DP}}_{I}(q,t)$.

###### Proof.

As $\textnormal{{DP}}_{I}(q,t)\neq\infty$ there is
$Q^{*}\in{\mathcal{I}}_{{\mathcal{F}},k}$ such that

$Q^{*}=\operatorname*{arg\,min}_{Q\in{\mathcal{I}}_{{\mathcal{F}},k}\textnormal{
s.t. }|Q|=q,~{}p(Q)=t}c(Q).$ (1)

Let $q^{*}_{1}=|Q^{*}\cap X|,q^{*}_{2}=|Q^{*}\setminus
X|,t^{*}_{1}=p(Q^{*}\cap X)$, and $t^{*}_{2}=p(Q^{*}\setminus X)$. By (1), and
since $S=X\uplus(S\setminus X)$, it holds that

$|Q^{*}|=|Q^{*}\cap X|+|Q^{*}\setminus X|=q^{*}_{1}+q^{*}_{2}=q$

and

$p(Q^{*})=p(Q^{*}\cap X)+p(Q^{*}\setminus X)=t^{*}_{1}+t^{*}_{2}=t.$

Moreover, by Observation 2.2, since $Q^{*}\in{\mathcal{I}}_{{\mathcal{F}},k}$,
it holds that $Q^{*}\cap X\in{\mathcal{I}}(I\cap X)$ and $Q^{*}\setminus
X\in{\mathcal{I}}(I\setminus X)$ . Thus,

$\displaystyle\textnormal{{DP}}_{I}(q,t)=c(Q^{*})=c(Q^{*}\cap
X)+c(Q^{*}\setminus X)\geq\textnormal{{DP}}_{I\cap
X}(q^{*}_{1},t^{*}_{1})+\textnormal{{DP}}_{I\setminus
X}(q^{*}_{2},t^{*}_{2})\geq M.$

The first inequality holds since $\textnormal{{DP}}_{I\cap
X}(q^{*}_{1},t^{*}_{1})$ is the minimum cost of $Q\in{\mathcal{I}}(I\cap X)$
such that $|Q|=q^{*}_{1}$ and $p(Q)=t^{*}_{1}$; since $Q^{*}\cap X$ satisfies
these conditions (by Observation 2.2), we conclude that $c(Q^{*}\cap
X)\geq\textnormal{{DP}}_{I\cap X}(q^{*}_{1},t^{*}_{1})$. Similar arguments
show that $c(Q^{*}\setminus X)\geq\textnormal{{DP}}_{I\setminus
X}(q^{*}_{2},t^{*}_{2})$. The second inequality holds since $M$ is the minimum
value of $\textnormal{{DP}}_{I\cap
X}(q_{1},t_{1})+\textnormal{{DP}}_{I\setminus X}(q_{2},t_{2})$ over all
$q_{1},q_{2},t_{1},t_{2}\in\mathbb{N}$ such that
$q_{1}+q_{2}=q,t_{1}+t_{2}=t$. As
$q^{*}_{1},q^{*}_{2},t^{*}_{1},t^{*}_{2}\in\mathbb{N}$ and
$q^{*}_{1}+q^{*}_{2}=q,t^{*}_{1}+t^{*}_{2}=t$, the inequality follows.
$\square$

######  Claim 3.4.

If $M\neq\infty$ and $q\leq k(S)$ then $\textnormal{{DP}}_{I}(q,t)\leq M$.

###### Proof.

Let
$q^{\prime}_{1},q^{\prime}_{2},t^{\prime}_{1},t^{\prime}_{2}\in\mathbb{N},q^{\prime}_{1}+q^{\prime}_{2}=q,t^{\prime}_{1}+t^{\prime}_{2}=t$
such that

$\textnormal{{DP}}_{I\cap
X}(q^{\prime}_{1},t^{\prime}_{1})+\textnormal{{DP}}_{I\setminus
X}(q^{\prime}_{2},t^{\prime}_{2})=M.$

Since $M\neq\infty$, there exist

$Q^{\prime}_{1}=\operatorname*{arg\,min}_{Q\in{\mathcal{I}}(I\cap
X)\textnormal{ s.t.
}|Q|=q^{\prime}_{1},~{}p(Q)=t^{\prime}_{1}}c(Q),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}Q^{\prime}_{2}=\operatorname*{arg\,min}_{Q\in{\mathcal{I}}(I\setminus
X)\textnormal{ s.t. }|Q|=q^{\prime}_{2},~{}p(Q)=t^{\prime}_{2}}c(Q).$ (2)

By (2),

$\displaystyle M={}$ $\displaystyle\textnormal{{DP}}_{I\cap
X}(q^{\prime}_{1},t^{\prime}_{1})+\textnormal{{DP}}_{I\setminus
X}(q^{\prime}_{2},t^{\prime}_{2})$ $\displaystyle={}$ $\displaystyle
c(Q^{\prime}_{1})+c(Q^{\prime}_{2})$ $\displaystyle={}$ $\displaystyle
c(Q^{\prime}_{1}\uplus Q^{\prime}_{2})$ $\displaystyle\geq{}$
$\displaystyle\min_{Q\in{\mathcal{I}}_{{\mathcal{F}},k}\textnormal{ s.t.
}|Q|=q,~{}p(Q)=t}c(Q)$ $\displaystyle={}$ $\displaystyle\textsf{DP}_{I}(q,t).$

The above inequality follows from the next arguments. As
$q^{\prime}_{1}+q^{\prime}_{2}=q$ and $q\leq k(S)$, by Observation 2.2
$Q^{\prime}_{1}\uplus Q^{\prime}_{2}\in{\mathcal{I}}_{{\mathcal{F}},k}$; also,
$|Q^{\prime}_{1}\uplus Q^{\prime}_{2}|=q$, and $p(Q^{\prime}_{1}\uplus
Q^{\prime}_{2})=t^{\prime}_{1}+t^{\prime}_{2}=t$. The inequality follows, as
the minimum in the right-hand side of the inequality considers
$Q=Q^{\prime}_{1}\uplus Q^{\prime}_{2}$ in particular. $\square$

To complete the proof of the lemma, we consider four complementary cases.

  * •

If $q>k(S)$ then $\textsf{DP}_{I}(q,t)=\infty$ by Definition 3.1.

  * •

If $M=\infty$ then $\textsf{DP}_{I}(q,t)=\infty$ by Claim 3.3.

  * •

If $q\leq k(S)$ and $\textsf{DP}_{I}(q,t)=\infty$ then by Claim 3.4 $M=\infty$
.

  * •

If $q\leq k(S)$ and $\textsf{DP}_{I}(q,t)\neq\infty$ then, by Claims 3.3 and
3.4, $\textsf{DP}_{I}(q,t)=M$.

∎

Note that computing the table $\textsf{DP}_{I}$ by Lemma 3.2 is possible only
if there is a maximal set $X\in{\mathcal{F}}\setminus\\{S\\}$; this requires
more than one set in the laminar family. If $|{\mathcal{F}}|=1$, we compute
the table $\textsf{DP}_{I}$ using two alternative ways, depending on whether
$|S|=1$ or $|S|>1$. The next observation considers the case where the instance
consists of a single element; it follows immediately from Definition 3.1.

######  Observation 3.5.

For a BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$ such that $|S|=1$ it holds
that $\textnormal{{DP}}_{I}(1,p(S))=c(S)$, $\textnormal{{DP}}_{I}(0,0)=0$, and
for any other $(q,t)\in\\{0,\ldots,|S|\\}\times P_{I}$ it holds that
$\textnormal{{DP}}_{I}(q,t)=\infty$.

We now consider the case where $|S|>1$ and ${\mathcal{F}}=\\{S\\}$. Here, we
define a new instance which adds a (redundant) partition of S into two
subsets. This partition allows us to use the recursive computation as given in
Lemma 3.2. For a BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$ such that
${\mathcal{F}}=\\{S\\}$ and $|S|>1$, we say that the BLM instance
$\tilde{I}=(S,\tilde{{\mathcal{F}}},\tilde{k},c,p,B)$ is a partitioned-
instance of $I$ if the following holds.

  * •

$\tilde{{\mathcal{F}}}=\\{S_{1},S_{2},S\\}$ where $S_{1},S_{2}$ is a partition
of $S$.

  * •

$\tilde{k}:\tilde{{\mathcal{F}}}\rightarrow\mathbb{N}$ and
$\tilde{k}(S_{1})=\tilde{k}(S_{2})=\tilde{k}(S)=k(S)$.

Note that $S_{1},S_{2}\neq\emptyset$ since $|S|>1$. The next lemma states that
the independent sets of an instance $I$ and of a partitioned-instance of $I$
are identical.

######  Lemma 3.6.

For any BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$ such that
${\mathcal{F}}=\\{S\\}$ and $|S|>1$, and a partitioned-instance
$\tilde{I}=(S,\tilde{{\mathcal{F}}},\tilde{k},c,p,B)$ of $I$ it holds that
${\mathcal{I}}_{{\mathcal{F}},k}={\mathcal{I}}_{\tilde{{\mathcal{F}}},\tilde{k}}$.

###### Proof.

Let $\tilde{{\mathcal{F}}}=\\{S_{1},S_{2},S\\}$ and
$Q\in{\mathcal{I}}_{{\mathcal{F}},k}$. Then $|Q|\leq k(S)=\tilde{k}(S)$, and

$|Q\cap S_{1}|\leq|Q|\leq k(S)=\tilde{k}(S_{1}).$

Similarly, $|Q\cap S_{2}|\leq\tilde{k}(S_{2})$. Thus,
$Q\in{\mathcal{I}}_{\tilde{{\mathcal{F}}},\tilde{k}}$. For the other
direction, let $\tilde{Q}\in{\mathcal{I}}_{\tilde{{\mathcal{F}}},\tilde{k}}$.
Then, $|\tilde{Q}|\leq\tilde{k}(S)=k(S)$ and it follows that
$\tilde{Q}\in{\mathcal{I}}_{{\mathcal{F}},k}$. We conclude that
${\mathcal{I}}_{{\mathcal{F}},k}={\mathcal{I}}_{\tilde{{\mathcal{F}}},\tilde{k}}$.
∎

The next result follows immediately from Lemma 3.6 and Definition 3.1.

######  Corollary 3.7.

For any BLM instance $I$ such that ${\mathcal{F}}=\\{S\\}$ and $|S|>1$, and a
partitioned-instance $\tilde{I}$ of $I$, it holds that
$\textnormal{{DP}}_{\tilde{I}}=\textnormal{{DP}}_{I}$.

Figure 2: An illustration of the recursive calls of Algorithm 1 for a BLM
instance $I$ with five elements $S=\\{1,2,3,4,5\\}$, represented by the
circles. The underbraces indicate the sets in the laminar family
${\mathcal{F}}$ of the instance in each node of the tree. For example, in the
root node, ${\mathcal{F}}=\\{S,\\{2,3\\},\\{4,5\\}\\}$.

Using the above, we derive a pseudo-polynomial time algorithm which computes
$\textsf{DP}_{I}$. If there is one element, the algorithm computes
$\textsf{DP}_{I}$ using Observation 3.5; otherwise, if there is one set
${\mathcal{F}}=\\{S\\}$ in the laminar family, the algorithm computes
$\textsf{DP}_{I}$ by a recursive call to the algorithm with a partitioned-
instance. The remaining case is that there exists a maximal set
$X\in{\mathcal{F}}\setminus\\{S\\}$ for which we can apply the recursive
computation of the table via Lemma 3.2. We give an illustration of recursive
calls the algorithm initiates in Figure 2. The pseudocode of the algorithm is
given in Algorithm 1. For a BLM instance $I$, we use $d(I)$ to denote the
recursion depth in the execution of $\textsf{ComputeDP}\left(I\right)$.

1

input : A BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$.

2

output : The table $\textsf{DP}_{I}$ as defined in Definition 3.1.

3

4Initialize $\textnormal{{DP}}_{I}(q,t)=\infty$ for all
$q\in\\{0,1,\ldots,|S|\\}$ and $t\in P_{I}$.

5if  _$|S|=1$_ then

6

7 Set $\textnormal{{DP}}_{I}(1,p(S))\leftarrow c(S)$ and
$\textnormal{{DP}}_{I}(0,0)\leftarrow 0$.

8 Return the table $\textnormal{{DP}}_{I}$.

9 end if

10

11if  _$|{\mathcal{F}}|=1$_ then

12

13 Return $\textsf{ComputeDP}\left(\tilde{I}\right)$ where $\tilde{I}$ is a
partitioned-instance of $I$.

14 end if

15

16Find a maximal set $X\in{\mathcal{F}}\setminus\\{S\\}$ .

17Compute $\textsf{DP}_{I\cap X}\leftarrow\textsf{ComputeDP}(I\cap X)$ and
$\textsf{DP}_{I\setminus X}\leftarrow\textsf{ComputeDP}(I\setminus X)$.

18For $q\in\\{0,1,\ldots,|S|\\}$ and $t\in P_{I}$ set
$\textnormal{{DP}}_{I}(q,t)=\begin{cases}\min_{\begin{subarray}{c}q_{1},q_{2},t_{1},t_{2}\in\mathbb{N}\textnormal{
s.t. }\\\
q_{1}+q_{2}=q,t_{1}+t_{2}=t\end{subarray}}\left\\{\textnormal{{DP}}_{I\cap
X}(q_{1},t_{1})+\textnormal{{DP}}_{I\setminus
X}(q_{2},t_{2})\right\\}~{}~{}&\textnormal{if}\ q\leq k(S)\\\
\infty~{}~{}&\textnormal{otherwise}\end{cases}$

Return the table $\textnormal{{DP}}_{I}$.

Algorithm 1 $\textsf{ComputeDP}(I)$

######  Lemma 3.8.

For any BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$ Algorithm 1 returns the
table $\textnormal{{DP}}_{I}$.

###### Proof.

We show that for every BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$ it holds
that $\textsf{ComputeDP}\left(I\right)=\textsf{DP}_{I}$. The proof is by
induction on $d(I)$. For the base case, let $I$ be a BLM instance such that
$d(I)=1$. Then, it holds that $|S|=1$ and the algorithm returns
$\textsf{DP}_{I}$ by Observation 3.5 and Steps 1, 1 of Algorithm 1. For some
$n\in\mathbb{N}_{>0}$, assume that for every BLM instance $I^{\prime}$ for
which $d(I^{\prime})\leq n$, it holds that
$\textsf{ComputeDP}\left(I^{\prime}\right)=\textsf{DP}_{I^{\prime}}$. For the
induction step, let $I=(S,{\mathcal{F}},k,c,p,B)$ be a BLM instance such that
$d(I)=n+1$. We consider two cases.

  1. 1.

$|{\mathcal{F}}|=1$. Then Algorithm 1 returns
$\textsf{ComputeDP}\left(\tilde{I}\right)$ by Step 1, where $\tilde{I}$ is a
partitioned-instance of $I$. By the induction hypothesis, it holds that
$\textsf{ComputeDP}\left(\tilde{I}\right)=\textsf{DP}_{\tilde{I}}$. Thus, by
Corollary 3.7, we have
$\textsf{ComputeDP}\left(I\right)=\textsf{ComputeDP}\left(\tilde{I}\right)=\textsf{DP}_{I}$.

  2. 2.

$|{\mathcal{F}}|>1$. In Step 1 in the (non-recursive) computation of
$\textsf{ComputeDP}\left(I\right)$, the algorithm finds a maximal set
$X\in{\mathcal{F}}\setminus\\{S\\}$. By the assumption of the induction it
follows that $\textsf{ComputeDP}(I\cap X)=\textsf{DP}_{I\cap X}$ and
$\textsf{ComputeDP}(I\setminus X)=\textsf{DP}_{I\setminus X}$. Therefore, by
Step 18 and Lemma 3.2 it holds that
$\textsf{ComputeDP}\left(I\right)=\textsf{DP}_{I}$.

∎

For the running time of Algorithm 1, assume that the laminar family is
represented by a linked list of sets, and that the elements in each set are
represented by a bit map.

######  Lemma 3.9.

For any BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$, the running time of
Algorithm 1 on $I$ is $O(|S|^{3}\cdot|P_{I}|^{2})$.

###### Proof.

We use the next claim.

######  Claim 3.10.

For any BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$, Algorithm 1 makes at most
$3\cdot|S|$ recursive calls during the execution of
$\textnormal{{ComputeDP}}(I)$.

###### Proof.

Consider the tree of recursive calls generated throughout the execution of
$\textnormal{{ComputeDP}}(I)$. Each element in $S$ has a unique leaf in the
tree; therefore, the number of leaves is bounded by $|S|$. Moreover, since
there are $|S|$ leaves, the number of internal nodes in the tree that have two
children is bounded by $|S|-1$; thus, the number of recursive calls initiated
in Step 1 is at most $|S|$. Finally, after each recursive call from Step 1 the
algorithm applies a recursive call from Step 1. Therefore, the number of
recursive calls from Step 1 is at most $|S|$. Overall, Algorithm 1 makes at
most $3\cdot|S|$ recursive calls. $\square$

To complete the proof, we show that the running time of the algorithm,
excluding the recursive calls, is $O(|S|^{2}\cdot|P_{I}|^{2})$. As the
recursive calls in the algorithm use instances in which the number of elements
is bounded by $|S|$, and the set of profits is of size at most $P_{I}$, the
statement of the lemma follows from Claim 3.10. Computing Step 1 takes
$O(|S|\cdot|P_{I}|)$. Moreover, Step 1 can be computed in time $O(|S|)$ using
an arbitrary partition of the elements. Step 1 can be computed in time
$O(|S|)$ by iterating over all sets in the laminar family ${\mathcal{F}}$.
Also, computing each entry in the table $\textsf{DP}_{I}$ in Step 18 takes
$O(|S|\cdot|P_{I}|)$; thus, computing the entire table takes
$O(|S|^{2}\cdot|P_{I}|^{2})$. Overall, the running time is
$O(|S|^{3}\cdot|P_{I}|^{2})$. ∎

##  4 An FPTAS for BLM

In this section we use the dynamic program in Section 3 to derive an FPTAS for
BLM, leading to the proof of Theorem 1.3. Let $I=(S,{\mathcal{F}},k,c,p,B)$ be
a BLM instance and let ${\varepsilon}>0$ be an error parameter. Note that the
computation time of $\textsf{DP}_{I}$ depends on $|P_{I}|$, may not be
polynomial in the input size. To obtain a polynomial-time algorithm, we round
down the profit of each item $e$ to
$\left\lfloor\frac{p(e)}{\alpha}\right\rfloor$, where
$\alpha=\frac{{\varepsilon}\cdot\max_{e\in S}p(e)}{|S|}$. This generates a
reduced instance $\bar{I}$, for which the table $\textsf{DP}_{I}$ can be
computed efficiently. Then, by iterating over all possible values in
$\textsf{DP}_{I}$, we compute the value of the optimum for $\bar{I}$; this
gives an almost optimal solution for $I$, where the solution itself is
computed using standard backtracking. The pseudocode of the algorithm is given
in Algorithm 2.

1

input : A BLM instance $I=(S,{\mathcal{F}},k,c,p,B)$ and an error parameter
${\varepsilon}>0$.

2

output : A solution $T$ of $I$ with profit
$p(T)\geq(1-{\varepsilon})\cdot\textnormal{OPT}(I)$.

3

4Let $\alpha\leftarrow\frac{{\varepsilon}\cdot\max_{e\in S}p(e)}{|S|}$ and
define
$\bar{p}(e)\leftarrow\left\lfloor\frac{p(e)}{\alpha}\right\rfloor~{}\forall
e\in S$.

5Compute $\textsf{DP}_{\bar{I}}\leftarrow\textsf{ComputeDP}(\bar{I})$, where
$\bar{I}=(S,{\mathcal{F}},k,c,\bar{p},B)$.

6Let $\lambda\leftarrow\bigg{\\{}(q,t)\in\\{0,\ldots,|S|\\}\times
P_{\bar{I}}~{}\bigg{|}~{}\textsf{DP}_{\bar{I}}(q,t)\leq B\bigg{\\}}$.

Use backtracking to find a solution $T$ for $I$ of value
$\max_{(q,t)\in\lambda}t$.

Algorithm 2 $\textsf{FPTAS}(I,{\varepsilon})$

Proof of Theorem 1.3: We show that Algorithm 2 is an FPTAS for BLM. Let
$\bar{I}=(S,{\mathcal{F}},k,c,\bar{p},B)$ be the instance with the rounded
profits as given in Algorithm 2. By Lemma 3.8, $\textsf{ComputeDP}(\bar{I})$
returns the table $\textsf{DP}_{\bar{I}}$ as given in Definition 3.1. Thus,
for all $(q,t)\in\lambda$ there is a solution for $\bar{I}$ of profit $t$ if
and only if $\textsf{DP}_{\bar{I}}(q,t)\leq B$. Let $T$ be an optimal solution
for $\bar{I}$. By the above, we have

$\bar{p}(T)=\max_{(q,t)\in\lambda}t=\textnormal{OPT}(\bar{I})$ (3)

Let $T^{*}$ be an optimal solution of $I$. Then,

$\displaystyle\bar{p}(T^{*})=\sum_{e\in
T^{*}}\left\lfloor\frac{p(e)}{\alpha}\right\rfloor\geq\sum_{e\in
T^{*}}\left(\frac{p(e)}{\alpha}-1\right)\geq\sum_{e\in
T^{*}}\left(\frac{p(e)}{\alpha}\right)-|S|=\frac{\textnormal{OPT}(I)}{\alpha}-|S|.$
(4)

Hence,

$p(T)\geq\alpha\cdot\bar{p}(T)\geq\alpha\cdot\bar{p}(T^{*})\geq\alpha\cdot\left(\frac{\textnormal{OPT}(I)}{\alpha}-|S|\right)=\textnormal{OPT}(I)-{\varepsilon}\cdot\max_{e\in
S}p(e)\geq(1-{\varepsilon})\cdot\textnormal{OPT}(I).$

The first inequality holds by Step 2. The second inequality follows from the
optimality of $\bar{p}(T)$ by (3). The third inequality holds by (4). The last
inequality holds since $\textnormal{OPT}(I)\geq\max_{e\in S}p(e)$ (assuming
that $c(e)\leq B~{}\forall e\in S$).

We now analyze the running time of the scheme. We note that Step 2 takes
linear time. The running time of Step 2 is $O(|S|^{3}\cdot|P_{\bar{I}}|^{2})$
by Lemma 3.9. Finally, Steps 2 and 2 can be computed in time
$O(|S|\cdot|P_{\bar{I}}|)$ by the definition of $\lambda$. Hence, the overall
running time is

$O\left(|S|^{3}\cdot|P_{\bar{I}}|^{2}\right)=O\left(|I^{5}|\cdot{\varepsilon}^{-2}\right).$

The equality follows since $|\bar{P}_{\bar{I}}|=O(|S|\cdot{\varepsilon}^{-1})$
by Step 2. $\blacksquare$

##  5 Discussion

In this paper we showed that the budgeted laminar matroid independent set
(BLM) problem admits an FPTAS, thus improving upon the existing EPTAS for this
matroid family, and generalizing the FPTAS for the special cases of
cardinality constrained knapsack and multiple-choice knapsack. Our FPTAS is
based on a natural dynamic program which utilizes the tree-like structure of
laminar matroids. It seems that with slight modifications our scheme yields an
FPTAS for the more general problem of budgeted $k$-laminar matroid independent
set, where $k\in\mathbb{N}$ is fixed.333For a definition of $k$-laminar
matroids see, e.g. [12].

An intriguing open question is whether BMI admits an FPTAS on other families
of matroids, such as graphic matroids, transversal matroids, or linear
matroids.

We note that the running time of our scheme is
$O(|I|^{5}\cdot{\varepsilon}^{-2})$, whereas the running time of the state of
the art FPTAS for knapsack is $O(|I|+{\varepsilon}^{-2.2})$ [8], which almost
matches the lower bound of
$\tilde{O}\left((|I|+{\varepsilon}^{-1})^{2-o(1)}\right)$ for the problem [7].
It would be interesting to design an FPTAS for BLM that matches the running
time of [8], or to obtain a stronger lower bound for this problem.

## References

  * [1] Bansal, M., Venkaiah, V.: Improved fully polynomial time approximation scheme for the 0-1 multiple-choice knapsack problem. International Institute of Information Technology Tech Report pp. 1–9 (2004)
  * [2] Berger, A., Bonifaci, V., Grandoni, F., Schäfer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Mathematical Programming 128(1), 355–372 (2011)
  * [3] Cacchiani, V., Iori, M., Locatelli, A., Martello, S.: Knapsack problems-an overview of recent advances. part ii: Multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research p. 105693 (2022)
  * [4] Caprara, A., Kellerer, H., Pferschy, U., Pisinger, D.: Approximation algorithms for knapsack problems with cardinality constraints. European Journal of Operational Research 123(2), 333–345 (2000)
  * [5] Chakaravarthy, V.T., Choudhury, A.R., Natarajan, S.R., Roy, S.: Knapsack cover subject to a matroid constraint. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) (2013)
  * [6] Chekuri, C., Vondrák, J., Zenklusen, R.: Multi-budgeted matchings and matroid intersection via dependent rounding. In: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. pp. 1080–1097 (2011)
  * [7] Cygan, M., Mucha, M., Wegrzycki, K., Włodarczyk, M.: On problems equivalent to (min,+)-convolution. ACM Transactions on Algorithms (TALG) 15(1), 1–25 (2019)
  * [8] Deng, M., Jin, C., Mao, X.: Approximating knapsack and partition via dense subset sums. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 2961–2979 (2023)
  * [9] Doron-Arad, I., Kulik, A., Shachnai, H.: An EPTAS for budgeted matching and budgeted matroid intersection. arXiv preprint arXiv:2302.05681 (2023)
  * [10] Doron-Arad, I., Kulik, A., Shachnai, H.: An EPTAS for budgeted matroid independent set. In: Symposium on Simplicity in Algorithms (SOSA). pp. 69–83 (2023)
  * [11] Doron-Arad, I., Kulik, A., Shachnai, H.: Hardness of weighted matroid problems. Manuscript (2023)
  * [12] Fife, T., Oxley, J.: Generalized laminar matroids. European Journal of Combinatorics 79, 111–122 (2019)
  * [13] Gabow, H., Kohno, T.: A network-flow-based scheduler: Design, performance history, and experimental analysis. Journal of Experimental Algorithmics (JEA) 6, 3–es (2001)
  * [14] Gilmore, P., Gomory, R.E.: The theory and computation of knapsack functions. Operations Research 14(6), 1045–1074 (1966)
  * [15] Gourvès, L., Monnot, J., Tlilane, L.: Worst case compromises in matroids with applications to the allocation of indivisible goods. Theoretical Computer Science 589, 121–140 (2015)
  * [16] Grandoni, F., Zenklusen, R.: Approximation schemes for multi-budgeted independence systems. In: European Symposium on Algorithms. pp. 536–548 (2010)
  * [17] Hassin, R., Levin, A.: An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM Journal on Computing 33(2), 261–268 (2004)
  * [18] Hong, S.P., Chung, S.J., Park, B.H.: A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. Operations Research Letters 32(3), 233–239 (2004)
  * [19] Im, S., Wang, Y.: Secretary problems: Laminar matroid and interval scheduling. In: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. pp. 1265–1274 (2011)
  * [20] Kellerer, H., Pferschy, U., Pisinger, D.: Multidimensional knapsack problems. Springer (2004)
  * [21] Kellerer, H., Pferschy, U., Pisinger, D.: The multiple-choice knapsack problem. In: Knapsack Problems, pp. 317–347 (2004)
  * [22] Knuth, D.E.: Computer Programming as an Art. Commun. ACM 17(12), 667–673 (1974)
  * [23] Li, W., Lee, J., Shroff, N.: A faster FPTAS for knapsack problem with cardinality constraint. Discrete Applied Mathematics 315, 71–85 (2022)
  * [24] Martello, S., Toth, P.: Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. (1990)
  * [25] Mastrolilli, M., Hutter, M.: Hybrid rounding techniques for knapsack problems. Discrete applied mathematics 154(4), 640–649 (2006)
  * [26] Popa, L., Kumar, G., Chowdhury, M., Krishnamurthy, A., Ratnasamy, S., Stoica, I.: Faircloud: Sharing the network in cloud computing. In: Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication. pp. 187–198 (2012)
  * [27] Popa, L., Yalagandula, P., Banerjee, S., Mogul, J.C., Turner, Y., Santos, J.R.: Elasticswitch: Practical work-conserving bandwidth guarantees for cloud computing. In: Proceedings of the ACM SIGCOMM 2013 conference. pp. 351–362 (2013)
  * [28] Sinha, P., Zoltners, A.A.: The multiple-choice knapsack problem. Operations Research 27(3), 503–515 (1979)
  * [29] Zhu, J., Li, D., Wu, J., Liu, H., Zhang, Y., Zhang, J.: Towards bandwidth guarantee in multi-tenancy cloud computing networks. In: 2012 20th IEEE International Conference on Network Protocols (ICNP). pp. 1–10 (2012)


# Spectral invariants for non-compactly supported Hamiltonians on the disc,
and an application to the mean action spectrum

Barney Bramham, Abror Pirnapasov  Ruhr-Universität Bochum
<EMAIL_ADDRESS>University of Maryland, College Park<EMAIL_ADDRESS>
###### Abstract.

For a symplectic isotopy on the two-dimensional disc we show that the
classical spectral invariants of Viterbo [20] can be extended in a meaningful
way to non-compactly supported Hamiltonians. We establish some basic
properties of these extended invariants and as an application we show that
Hutchings’ inequality in [8] between the Calabi invariant and the mean action
spectrum holds without any assumptions on the isotopy; in [8] it is assumed
that the Calabi invariant is less than the rotation number (or action) on the
boundary.

##  1\. Introduction

We begin with the application. In [8] Hutchings used embedded contact homology
to prove a striking inequality relating the mean action spectrum with the
Calabi invariant of a Hamiltonian isotopy of the disc. Recall that if
$\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ is a smooth symplectic isotopy
on a closed two-dimensional symplectic disc $(\mathbb{D},\omega)$, starting at
the identity $\varphi_{0}=\mathrm{id}_{\mathbb{D}}$, then the Calabi invariant
$\mathrm{CAL\,}(\tilde{\varphi})\in\mathbb{R}$ can be defined as an average
action of $\tilde{\varphi}$, or equivalently as the integral
$\int_{0}^{1}\int_{\mathbb{D}}H\,\omega\,dt$ of the unique generating
Hamiltonian $H:\mathbb{R}/\mathbb{Z}\times\mathbb{D}\to\mathbb{R}$ that has
been normalized to vanish pointwise on the boundary of the disc. Unless stated
otherwise, all objects are smooth.

######  Theorem 1 (Hutchings’ inequality [8]).

Consider a symplectic isotopy $\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$
on the closed symplectic disc $(\mathbb{D},\omega_{0})$, normalized to have
area $1$ 111Some such normalization is necessary, as
$\mathrm{CAL\,}(\tilde{\varphi})$ has different dimensions to the action
$\sigma_{\tilde{\varphi},\lambda}$. Alternatively, in the statement and
throughout the paper, one could replace the Calabi invariant by the spatial
average $\frac{1}{\int_{\mathbb{D}}\omega_{0}}\mathrm{CAL\,}(\tilde{\varphi})$
and replace $a$ by the average
$\frac{1}{\int_{\partial\mathbb{D}}\lambda_{0}}\int_{\partial\mathbb{D}}\sigma_{\tilde{\varphi},\lambda_{0}}\lambda_{0}$.
. Let
$a:=\overline{\sigma}_{\tilde{\varphi}}|_{\partial\mathbb{D}}\in\mathbb{R}$
denote the mean action on the boundary. If

(1) $\mathrm{CAL\,}(\tilde{\varphi})<a$

then

(2) $\inf\mathcal{S}_{\mathrm{mean}}(\tilde{\varphi})\ \leq\
\mathrm{CAL\,}(\tilde{\varphi})$

where $\mathcal{S}_{\mathrm{mean}}(\tilde{\varphi})$ is the set of all mean
actions at interior periodic points of $\varphi$, also called the mean
spectral values. See 2.1 for precise definitions.

Note that $a$ is also the rotation number of $\tilde{\varphi}$ restricted to
$\partial\mathbb{D}$, which is how the statement is formulated in [8]. This
agreement is due to the normalization of the action function chosen in (10),
see also Remark 6. In [8] it is assumed that the time-$1$ map $\varphi$ is a
rigid rotation on a neighborhood of the boundary of the disc. This boundary
condition was later removed by the second author, see [16].

Our main application in this article is that assumption (1) can be removed:

######  Theorem 2.

For any symplectic isotopy $\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ on
the disc $(\mathbb{D},\omega_{0})$, normalized to have unit area, there holds

$\inf\mathcal{S}_{\mathrm{mean}}(\tilde{\varphi})\ \leq\
\mathrm{CAL\,}(\tilde{\varphi}).$

This result can also be applied to the inverse isotopy
$\tilde{\varphi}^{-1}=\\{\varphi^{-1}_{t}\\}_{t\in[0,1]}$, something which
could not be done from the original statement, because condition (1) can never
hold simultaneously for $\tilde{\varphi}$ and $\tilde{\varphi}^{-1}$.
Therefore:

######  Corollary 1.

For any symplectic isotopy $\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ on
the disc $(\mathbb{D},\omega_{0})$, normalized to have unit area, the
associated Calabi invariant and the mean spectral values satisfy

(3) $\inf\mathcal{S}_{\mathrm{mean}}(\tilde{\varphi})\ \leq\
\mathrm{CAL\,}(\tilde{\varphi})\ \leq\
\sup\mathcal{S}_{\mathrm{mean}}(\tilde{\varphi}).$

In [11] Le Calvez proved inequality (3) for $C^{1}$ pseudo-rotations that are
a rotation on the boundary using his method of transverse foliations. In this
case the inequalities are equalities.

Let us point out that we do not give a new proof of Theorem 1: The proof in
[8] ultimately relies on deep connections between the ECH spectrum and contact
volume in three dimensions, see [4], and as far as we are aware no alternative
proof is known; either using tools from dynamical systems or more classical
Floer-theoretic methods. An approach using periodic Floer homology (PFH) is
also not known, despite connections between the PFH spectrum and the Calabi
invariant [3]. One difficulty is that the twisted PFH action is different to
the Hamiltonian action. However there are some related results: In [17] the
second author and Prasad used PFH to prove a weaker version of (3) for
$C^{\infty}$-generic Hamiltonian diffeomorphisms of compact surfaces, possibly
with boundary; in [21, 13] Weiler and Nelson-Weiler use ECH to obtain results
similar to Theorem 1 for symplectic diffeomorphisms of the annulus and for
higher-genus surfaces with one boundary component.

###  1.1. Overview of extending the spectral invariants

Recall that the classical spectral invariants [20] are a pair of continuous
sections of the action spectrum $\tilde{\varphi}\mapsto
c_{-}(\tilde{\varphi})$ and $\tilde{\varphi}\mapsto c_{+}(\tilde{\varphi})$,
that are defined on any smooth Hamiltonian isotopy
$\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ on the standard symplectic
vector space $(\mathbb{R}^{2n},\omega_{0})$, provided the isotopy can be
generated by a compactly supported, time-dependent Hamiltonian $H\in
C^{\infty}(\mathbb{R}/\mathbb{Z}\times\mathbb{R}^{2n},\mathbb{R})$. This is
recalled more precisely in 2.2. The action spectrum of $\tilde{\varphi}$
refers to the set of actions of the $1$-periodic orbits:

(4) $\mathcal{S}(\tilde{\varphi}):=\big{\\{}\mathcal{A}_{H}(p)\in\mathbb{R}\
\big{|}\ p\in\mathrm{Fix}(\varphi_{1})\big{\\}}$

where the action is defined by (11). The spectral invariants
$c_{-}(\tilde{\varphi})$ and $c_{+}(\tilde{\varphi})$ enjoy many nice
properties recalled in Theorem 6. In particular $c_{-}(\tilde{\varphi})$ and
$c_{+}(\tilde{\varphi})$ depend only on the time-one map $\varphi_{1}$ and
they depend continuously with respect to the Hofer metric.

To extend $c_{+}$ and $c_{-}$ to a symplectic isotopy $\tilde{\varphi}$ on the
disc, not necessarily compactly supported in the interior, we use a limiting
procedure along the following lines: $\tilde{\varphi}$ is uniquely generated
by a time-dependent Hamiltonian function on $\mathbb{D}$ that vanishes
pointwise on the boundary $\partial\mathbb{D}$ for all times, even though in
general it is not supported in the interior
$\dot{\mathbb{D}}=\mathbb{D}\backslash\partial\mathbb{D}$. Thus we can extend
the Hamiltonian function continuously to
$H:\mathbb{R}/\mathbb{Z}\times\mathbb{R}^{2}\to\mathbb{R}$ by setting $H\equiv
0$ on the complement $\mathbb{R}^{2}\backslash\mathbb{D}$. Thus $H$ is
continuous everywhere, and smooth away from the circle
$\partial\mathbb{D}\subset\mathbb{R}^{2}$. Then we take a sequence of smooth
approximations $H_{n}:\mathbb{R}/\mathbb{Z}\times\mathbb{R}^{2}\to\mathbb{R}$
with compact support, which converge to $H$ (only) in a $C^{0}$-sense. The
spectral invariants for each $H_{n}$ are well defined and one can define

$c_{\pm}(\tilde{\varphi}):=\lim_{n\to\infty}c_{\pm}(H_{n}).$

Indeed, it follows easily from the continuity properties with respect to
Hofer’s norm, that the above limits exist and are independent of the choice of
approximating sequence $H_{n}$. The limits also trivially inherit a number of
fundamental properties listed in Proposition 12, including the non-triviality
property that at least one of $c_{+}(\tilde{\varphi})$ and
$c_{-}(\tilde{\varphi})$ is non-zero if $\varphi\neq\mathrm{Id}$. However, two
highly desirable properties are not obvious, because the convergence of the
Hamiltonians is not in $C^{1}$:

  1. (1)

First, that $c_{+}(\tilde{\varphi})$ and $c_{-}(\tilde{\varphi})$ depend only
on the time-one map - or rather on the homotopy class of $\tilde{\varphi}$
with fixed ends.

  2. (2)

Secondly, that the values $c_{+}(\tilde{\varphi})$, $c_{-}(\tilde{\varphi})$
are indeed spectral values, i.e. that they represent the actions of fixed
points of the time-one map.

Note that for the classical spectral invariants, i.e. for compactly supported
Hamiltonians on $\mathbb{R}^{2n}$, one usually shows the first property after
establishing the second together with the continuity properties. But this
strategy doesn’t work here as the second of the desired properties above will
no longer be true in general. What remains true, is that
$c_{+}(\tilde{\varphi})$, $c_{-}(\tilde{\varphi})$ lie in a discrete set,
which is enough. We will show:

######  Theorem 3.

Let $\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ be a symplectic isotopy on
the disc $(\mathbb{D},\omega)$ with area
$A:=\mathrm{area}_{\omega}(\mathbb{D})$ (not necessarily supported in
$\mathbb{D}\backslash\partial\mathbb{D}$). Then the extended definition of
spectral invariants $c_{+}(\tilde{\varphi}),c_{-}(\tilde{\varphi})$ depend
only on the homotopy class of $\tilde{\varphi}$ with fixed ends, and

(5)
$c_{+}(\tilde{\varphi})\in\mathcal{S}(\tilde{\varphi})\cup\\{0\\}\cup\\{A\\},$

and

(6)
$c_{-}(\tilde{\varphi})\in\mathcal{S}(\tilde{\varphi})\cup\\{0\\}\cup\\{-A\\}$

where $\mathcal{S}(\tilde{\varphi})\subset\mathbb{R}$ is the set of actions at
the $1$-periodic orbits in $\mathbb{D}$.

######  Example 1.

There are simple examples on $(\mathbb{D},\omega)$ where
$c_{\pm}(\tilde{\varphi})\notin\mathcal{S}(\tilde{\varphi})$, i.e. where the
spectral invariants are not spectral values. Indeed, consider the case that
$\tilde{\varphi}$ is the path of rotations on $\mathbb{D}$ about the origin
through a total angle $\rho\in\mathbb{R}$. Then the single fixed point (at the
origin) has action $A\rho$. On the other hand, from standard properties we
will see that $c_{+}(\tilde{\varphi})\in[0,A]$. Thus $c_{+}(\tilde{\varphi})$
cannot be a spectral value if $\rho>1$ or if $\rho<0$. Similarly
$c_{-}(\tilde{\varphi})$ cannot be a spectral value in this example if either
$\rho>0$ or $\rho<-A$.

In contrast to Example 1, if the isotopy does not make more than a full
rotation on the boundary of the disc, then at least one of the spectral
invariants is a spectral value, i.e. represents the action of a fixed point,
which is important for existence results. More precisely:

######  Theorem 4.

Let $\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ be a symplectic isotopy on
the disc $(\mathbb{D},\omega)$, as in Theorem 3, and denote by
$\rho:=\rho({\tilde{\varphi}}|_{\partial\mathbb{D}})$ the rotation number on
the boundary. Then:

  1. i)

If $-1<\rho\leq 1$ then
$c_{+}(\tilde{\varphi})\in\mathcal{S}(\tilde{\varphi})\cup\\{0\\}$.

  2. ii)

If $0\leq\rho\leq 1$ then
$c_{+}(\tilde{\varphi})\in\mathcal{S}(\tilde{\varphi})$.

  3. iii)

If $-1\leq\rho<1$ then
$c_{-}(\tilde{\varphi})\in\mathcal{S}(\tilde{\varphi})\cup\\{0\\}$.

  4. iv)

If $-1\leq\rho\leq 0$ then
$c_{-}(\tilde{\varphi})\in\mathcal{S}(\tilde{\varphi})$.

By Example 1 this statement is in some sense optimal.

In proving Theorem 4 we also use the following fact, which may be of
independent interest:

######  Proposition 5.

For a symplectic isotopy on the disc
$\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ with rotation number
$\rho:=\rho({\tilde{\varphi}}|_{\partial\mathbb{D}})$ on the boundary, we
have: $\rho>0$ implies $c_{+}(\tilde{\varphi})>0$, while $\rho<0$ implies
$c_{-}(\tilde{\varphi})<0$.

######  Remark 1.

We do not carry out any analogous program of extending the spectral invariants
in higher dimensions. This is a much more challenging problem and is not
needed for our application.

######  Remark 2.

Note that the extension of the spectral invariants in this article is of a
different nature to the $C^{0}$-extensions of the spectral invariants in [15,
19, 2, 9]. Indeed, in these works the goal is to extend the spectral
invariants to Hamiltonian homeomorphisms, i.e. the $C^{0}$-topology referred
to is on the time-one maps, while in this article the $C^{0}$-convergence is
on the level of the Hamiltonians. In particular, in general the time-one maps
on the plane undergo a discontinuity in the limit, namely on the boundary of
the disc.

######  Remark 3.

In [8] Hutchings’ inequality was stated for the mean action spectrum, rather
than the interior mean action spectrum
$\mathcal{S}_{\mathrm{mean}}(\tilde{\varphi})$. This distinction is trivial in
the statement of Theorem 1 because of the assumption (1). But it is relevant
to Theorem 2 and to Corollary 1. It also has bearing on Remark 1.4 from [8],
where it is noted that the approach in [8] does not seem to prove the reverse
inequality (i.e. the second inequality in (3)) and that this reverse
inequality may be less interesting since, when the rotation number on the
boundary is rational, the periodic points on the boundary will trivially
satisfy the reverse inequality. Hence we emphasize that Theorem 2 and
Corollary 1 refer to interior periodic points, which make the statements
somewhat more interesting.

######  Remark 4.

The spectral invariants of Viterbo were extended by Schwarz and Oh [18, 14] to
Hamiltonian diffeomorphisms on closed symplectic manifolds using Hamiltonian
Floer theory. They were further extended by Frauenfelder-Schlenk [5] and
Lanzat [10] to compact symplectic manifolds $(M,\omega)$ with contact type
boundary (also called convex boundary). In these latter cases the Hamiltonians
are compactly supported in $M\backslash\partial M$, in contrast, we allow non-
compactly supported Hamiltonians, albeit restricted to this $2$-dimensional
setting.

###  1.2. Proof of Theorem 2

Here we show how to remove the assumption on the Calabi invariant (1), by
combining Theorem 1 of Hutchings’ with the properties of the extended spectral
invariants described above. We begin with the following Corollary to Theorem
4:

######  Corollary 2.

Consider a symplectic isotopy $\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$
as in Theorem 3. Then the mean action on the boundary
$a:=\overline{\sigma}_{\tilde{\varphi}}|_{\partial\mathbb{D}}\in\mathbb{R}$
lies in the closure of the interior mean action spectrum:

(7) $a\in\overline{\mathcal{S}}_{\mathrm{mean}}(\tilde{\varphi}).$

###### Proof.

It suffices to show that $\varphi$ has an interior fixed point $x$ satisfying

(8) $|\sigma_{\tilde{\varphi}}(x)-\pi k|\leq\pi$

where $k\in\mathbb{Z}$ is unique so that $a\in[k\pi,(k+1)\pi)$. Indeed, then
applying (8) to each iterate $\tilde{\varphi}^{j}$ yields a sequence of
$j$-periodic points $x_{j}\in\mathbb{D}\backslash\partial\mathbb{D}$ with
action $|\sigma_{\tilde{\varphi}^{j}}(x)-\pi k_{j}|\leq\pi$, where
$k_{j}\in\mathbb{Z}$ is such that $aj\in[k_{j}\pi,(k_{j}+1)\pi)$, which after
dividing through by $j$ implies
$\lim_{j\to\infty}\overline{\sigma}_{\tilde{\varphi}}(x_{j})=\lim_{j\to\infty}\pi
k_{j}/j=a$ as required.

To prove (8), first suppose $a\in[0,\pi)$, i.e. $k=0$. If $\tilde{\varphi}$ is
isotopic, with fixed ends, to the identity isotopy, then $a=0$ is also the
action of each interior fixed point of $\tilde{\varphi}$, so that (7) is
trivially true. If $\tilde{\varphi}$ is not isotopic, with fixed ends, to the
identity, then at least one of $c_{+}(\tilde{\varphi})$ and
$c_{-}(\tilde{\varphi})$ is non-zero and so, due to our assumption on $a$, it
follows from items (i) or (iii) in Theorem 4 that this non-zero spectral
invariant is represented by the action at a fixed point $x$. This fixed point
cannot be on the boundary; if it were, it would have action zero, whereas $x$
has non-zero action. Therefore
$|\sigma_{\tilde{\varphi}}(x)|=|\mathcal{A}_{H}(x)|$ equals
$|c_{+}(\tilde{\varphi})|\leq\pi$ or $|c_{-}(\tilde{\varphi})|\leq\pi$. Thus
(8) holds, as $k=0$ in this case.

Now suppose $a\notin[0,\pi)$, i.e. $k\neq 0$. Let $\tilde{R}_{2\pi k}$ denote
the isotopy from the identity to the identity that rotates a total of $k$
times around the origin: $\tilde{R}_{2\pi k}=\\{R_{2\pi kt}\\}_{t\in[0,1]}$.
Then the mean action on the boundary of $\tilde{R}_{-2\pi
k}\circ\tilde{\varphi}$ is $a-\pi k\in[0,\pi)$, so that we can apply the
argument above to the isotopy $\tilde{R}_{-2\pi k}\circ\tilde{\varphi}$ and
conclude that $\varphi$ has an interior fixed point $x$ satisfying
$|\sigma_{\tilde{R}_{-2\pi k}\circ\tilde{\varphi}}(x)|\leq\pi$, in other
words, $|\sigma_{\tilde{\varphi}}(x)-\pi k|\leq\pi$. Thus (8) holds in
general. ∎

######  Remark 5.

Note that inequality (8) can be interpreted as a quantitative version of
Brouwer’s fixed point theorem. Curiously, applying it to the inverse isotopy
can yield a slightly different inequality, depending on the boundary behavior.

###### Proof of Theorem 2.

Let
$a:=\overline{\sigma}_{\tilde{\varphi}}|_{\partial\mathbb{D}}\in\mathbb{R}$
denote the mean action on the boundary. By Hutchings’ theorem, Theorem 1, the
conclusion holds if $\mathrm{CAL\,}(\tilde{\varphi})<a$, so we may assume that
$a\leq\mathrm{CAL\,}(\tilde{\varphi})$. By Corollary 2 $a$ lies in the closure
of the mean action spectrum, thus

$\inf\mathcal{S}_{\mathrm{mean}}(\tilde{\varphi})\leq
a\leq\mathrm{CAL\,}(\tilde{\varphi})$

as required. ∎

Thus it remains to prove Theorems 3 and 4, which is done in Section 4, as is
Proposition 5. Section 3 discusses the limiting process used to extend the
spectral invariants, and establishes some of their basic properties.

#### Acknowledgments.

We would like to thank Alberto Abbondandolo for helpful discussions. A. P. is
greatful to Dan Cristofaro-Gardiner and Marco Mazzucchelli for their support.
B. B. is partially supported by the DFG under the Collaborative Research
Center SFB/TRR 191 - 281071066 (Symplectic Structures in Geometry, Algebra and
Dynamics). A. P. is partially supported by the DFG Walter Benjamin Fellowship,
Projektnummer 518128580.

##  2\. Preliminaries

###  2.1. The action and Calabi invariant for symplectic isotopies on the disc

In the following $\omega$ is a smooth symplectic form on the closed disc
$\mathbb{D}\subset\mathbb{R}^{2}$, so without loss of generality
$\omega=cdx\wedge dy$ for some constant $c>0$. We will denote by $\omega_{0}$
the normalization for which $\int_{\mathbb{D}}\omega_{0}=1$. By a symplectic
isotopy on $(\mathbb{D},\omega)$ we mean a smooth path
$\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ of diffeomorphisms
$\varphi_{t}:\mathbb{D}\to\mathbb{D}$, starting at the identity map
$\varphi_{0}=\mathrm{Id}$, with $\varphi_{t}^{*}\omega=\omega$ for each
$t\in[0,1]$. Note that we are not assuming these maps are the identity on or
near to the boundary of the disc. Given a smooth primitive $\lambda$ of
$\omega$, the action function of $\tilde{\varphi}$

$\sigma=\sigma_{\tilde{\varphi},\lambda}:\mathbb{D}\to\mathbb{R}$

is defined to be the unique solution to

(9) $\displaystyle d\sigma=\varphi^{*}\lambda-\lambda\qquad\ \ \ \ \mbox{on
}\mathbb{D}$ (10)
$\displaystyle\sigma(z)=\int_{t\mapsto\varphi_{t}(z)}\lambda\qquad\mbox{for
all }z\in\partial\mathbb{D}.$

It is not hard to show that $\sigma_{\tilde{\varphi},\lambda}$ exists, is
unique, and depends only on the isotopy class of $\tilde{\varphi}$ with fixed
ends, [1, 12]. At fixed points $\sigma_{\tilde{\varphi},\lambda}$ is
independent of $\lambda$, so we may write $\sigma_{\tilde{\varphi}}(z)$. The
mean action at a $k$-periodic point $z\in\mathbb{D}$ of $\varphi$ is defined
by $\frac{1}{k}\sum_{j=0}^{k}\sigma_{\tilde{\varphi},\lambda}(\varphi^{j}(z))$
and is independent of $\lambda$, since it coincides with
$(1/k)\sigma_{\tilde{\varphi}^{k},\lambda}(z)$, being the value at a fixed
point of $\varphi^{k}$. More generally, by the ergodic theorem, the asymptotic
mean action function

$\overline{\sigma}_{\tilde{\varphi}}:\mathbb{D}\to\mathbb{R},\qquad\overline{\sigma}_{\tilde{\varphi}}(z):=\lim_{k\to\infty}\frac{1}{k}\sum_{j=0}^{k}\sigma_{\tilde{\varphi},\lambda}(\varphi^{j}(z))$

is well defined almost everywhere on $\mathbb{D}$ and at the periodic points.
It is also not hard to show that $\overline{\sigma}_{\tilde{\varphi}}$ is
independent of $\lambda$, see Lemma 2.2 in [1], and that it is defined at each
point on the boundary $\partial\mathbb{D}$, where it is constant and coincides
with $\mathrm{area}(\mathbb{D},\omega)\rho$, where $\rho\in\mathbb{R}$ is the
rotation number of $\tilde{\varphi}$ restricted to the boundary of the disc.

Finally, we define the interior mean action spectrum of $\tilde{\varphi}$ to
be the set of mean actions at interior periodic points:

$\mathcal{S}_{\mathrm{mean}}(\tilde{\varphi}):=\Big{\\{}\
\overline{\sigma}_{\tilde{\varphi}}(z)\in\mathbb{R}\ \Big{|}\
z\in\mathbb{D}\backslash\partial\mathbb{D},\ \ \varphi^{k}(z)=z\mbox{ some
}k\in\mathbb{N}\ \Big{\\}}.$

Another important quantity is the space average of the action:

$\mathrm{CAL\,}_{\omega}(\tilde{\varphi}):=\int_{\mathbb{D}}\sigma_{\tilde{\varphi},\lambda}\,\omega,$

called the Calabi invariant, which is infact independent of the primitive
$\lambda$.

######  Remark 6.

The validity of Hutchings’ inequality is independent of whether we add a
constant to the action function $\sigma_{\tilde{\varphi},\lambda}$. In other
words, the choice of the boundary condition (10) is irrelevant.

###  2.2. The classical spectral invariants on $(\mathbb{R}^{2n},\omega_{0})$

Let $\omega_{0}=\sum_{i=1}^{n}dx_{i}\wedge dy_{i}$ be the standard symplectic
structure on $\mathbb{R}^{2n}$ and $\lambda_{0}$ the primitive
$\frac{1}{2}\sum_{i=1}^{n}\big{(}x_{i}dy_{i}-y_{i}dx_{i}\big{)}$. Consider a
smooth and time-dependent Hamiltonian function
$H:\mathbb{R}/\mathbb{Z}\times\mathbb{R}^{2n}\to\mathbb{R}$ with compact
support.

For any smooth loop $x\in C^{\infty}(\mathbb{R}/\mathbb{Z},\mathbb{R}^{2n})$
the associated action is defined by

(11) $\mathcal{A}_{H}(x):=\int_{\mathbb{R}/\mathbb{Z}}x^{*}\lambda_{0}\ +\
\int_{0}^{1}H(t,x(t))\,dt.$

Formally the critical points of $\mathcal{A}_{H}$ correspond to the
$1$-periodic orbits of the time-dependent Hamiltonian vector field defined by
$i_{X_{H^{t}}}\omega=dH^{t}$, where $H^{t}(\cdot)=H(t,\cdot)$. These sign
conventions are convenient for two reasons; first, signs of rotation numbers
of trajectories are aligned with the sign of the Hamiltonian - see for example
the statement of Proposition 5; secondly, so that the action function
$\mathcal{A}_{H}$ on the loop space agrees with the action function from the
previous section at periodic points in the following sense: Suppose $n=1$ and
$H^{t}=0$ on $\partial\mathbb{D}$ for each $t\in[0,1]$. Then $X_{H^{t}}$ is
tangent to $\partial\mathbb{D}$, and so it generates a symplectic isotopy
$\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ on $\mathbb{D}$. With these
sign conventions, at each fixed point $p\in\mathbb{D}$ of the time-one map
$\varphi$, we have

$\sigma_{\tilde{\varphi},\lambda_{0}}(p)=\mathcal{A}_{H}(x)$

where $x$ is the $1$-periodic orbit starting at $p$, i.e.
$x(t)=\varphi_{t}(p)$. For a proof see [12] or [1]. More generally, the set

$\mathcal{S}(H):=\big{\\{}\mathcal{A}_{H}(x)\ \big{|}\
x\in\mathcal{P}_{1}(H)\big{\\}}.$

where $\mathcal{P}_{1}(H)$ is the collection of $1$-periodic trajectories of
$H$ in $\mathbb{R}^{2n}$, are called the spectral values of $H$. We also write
$\mathcal{S}(\tilde{\varphi})$ instead of $\mathcal{S}(H)$, see (4), where
$\tilde{\varphi}$ is the path of Hamiltonian diffeomorphisms generated by $H$.

Spectral invariants were first introduced by Viterbo [20]. See also the so
called spectral selector in Hofer-Zehnder [6]. The fundamental properties are
contained in the following statement:

######  Theorem 6 ([20]).

For any compactly supported Hamiltonian diffeomorphism $\varphi=\varphi_{H}$
generated as the time-$1$ map of $H\in
C_{c}^{\infty}(\mathbb{R}/\mathbb{Z}\times\mathbb{R}^{2n})$ the spectral
invariants $c_{+}(\varphi)$ and $c_{-}(\varphi)$ have the following
fundamental properties:

  1. (1)

$c_{+}(\varphi^{-1})=-c_{-}(\varphi)$.

  2. (2)

$c_{-}(\varphi)\leq 0\leq c_{+}(\varphi)$.

  3. (3)

$c_{+}(\varphi\psi)\leq c_{+}(\varphi)+c_{+}(\psi)$.

  4. (4)

$\gamma(\varphi)\geq\mathrm{area}(U)$ for every displaceable open disc $U$;
meaning $\varphi(U)\cap U=\emptyset$.

  5. (5)

$\gamma(\varphi)\leq\mathrm{area}(D)$ if $H$ has support in $D$.

  6. (6)

$\gamma(\varphi)\leq\vvvert\varphi\vvvert$.

  7. (7)

$H\mapsto c_{+}(\varphi_{H})$ and hence $H\mapsto c_{-}(\varphi_{H})$ and
$H\mapsto\gamma(\varphi_{H})$ are continuous, infact $1$-Lipschitz, with
respect to the Hofer norm, see Definition 7. For example for $c_{+}$ this
means

(12) $|c_{+}(\varphi_{H})-c_{+}(\varphi_{H^{\prime}})|\leq\vvvert
H-H^{\prime}\vvvert$

for all $H,H^{\prime}\in C_{c}^{\infty}([0,1]\times\mathbb{R}^{2n})$.

When convenient we sometimes write $c_{+}(H)$ instead of $c_{+}(\varphi_{H})$,
similarly for $c_{-}$.

######  Definition 7.

Here $\gamma(\varphi):=c_{+}(\varphi)-c_{-}(\varphi)$ is called the
$\gamma$-norm of $\varphi$, and

$\vvvert\varphi\vvvert:=\inf_{H}\vvvert H\vvvert$

is called the Hofer norm of $\varphi$, where the infimum is taken over all
compactly supported $H$ with time-$1$ map $\varphi$ and $\vvvert
H\vvvert:=\vvvert H\vvvert_{\mathbb{R}^{2n}}$ we call the Hofer norm of $H$,
where more generally

$\vvvert H\vvvert_{E}:=\int_{0}^{1}\max_{z\in E}H(t,z)-\min_{z\in
E}H(t,z)\,dt$

for any subset $E\subset\mathbb{R}^{2n}$.

Another important feature of the spectral invariants is the following well-
known monotonicity property, which is typically used to prove Theorem 6.

######  Theorem 8 ([20]).

If $H,G\in C_{c}^{\infty}(\mathbb{R}/\mathbb{Z}\times\mathbb{R}^{2n})$ are two
compactly supported Hamiltonians, generating diffeomorphisms $\varphi_{H}$ and
$\varphi_{G}$ as the time-$1$ maps, then

(13) $H\geq G\ \implies\ c_{+}(H)\geq c_{+}(G).$

##  3\. Extending $c_{-}(\varphi)$ and $c_{+}(\varphi)$ to non-compactly
supported isotopies

In this section we explain how to construct the spectral invariants for a non-
compactly supported Hamiltonian on the disc and show that many of the usual
properties for compactly supported Hamiltonians extend, see Proposition 12 and
Lemma 14. Throughout this section $H\in
C^{\infty}\big{(}\mathbb{R}/\mathbb{Z}\times\mathbb{D}\big{)}$ satisfies

(14) $H_{t}(z)=0\qquad\forall t\in\mathbb{R}/\mathbb{Z},\
z\in\partial\mathbb{D}.$

Note that each symplectic isotopy
$\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ on the disc, starting at the
identity, is generated by a unique such $H$.

######  Definition 9.

We define an _approximating sequence_ for $H$ to be any sequence $H_{n}\in
C_{c}^{\infty}\big{(}\mathbb{R}/\mathbb{Z}\times\mathbb{R}^{2}\big{)}$, for
$n\in\mathbb{N}$, satisfying the following two properties:

  1. (1)

(Extension) $H_{n}$ restricted to $[0,1]\times\mathbb{D}$ is equal to $H$.

  2. (2)

(Convergence)
$\lim_{n\to\infty}\|H_{n}\|_{C^{0}(\mathbb{R}^{2}\backslash\mathbb{D})}=0$.

It is straightforward to see that an approximating sequence always exists. In
Lemma 13 and Remark 7 below we give constructions with additional properties.
Now set:

######  Definition 10.

For any approximating sequence $(H_{n})_{n\in\mathbb{N}}$ for $H$, define

$c_{+}(H):=\lim_{n\to\infty}c_{+}(H_{n}),\qquad
c_{-}(H):=\lim_{n\to\infty}c_{-}(H_{n})$

where $c_{+}(H_{n})$ and $c_{-}(H_{n})$ are the standard spectral invariants
for compactly supported Hamiltonians on $\mathbb{R}^{2}$, as referred to in
Theorem 6.

This definition agrees with the original one if $H$ has compact support in
$\mathbb{D}\backslash\partial\mathbb{D}$ (take $H_{n}=H$ to be the constant
sequence), and is justified by:

######  Lemma 11.

If $(H_{n})_{n\in\mathbb{N}}$ is an approximating sequence for $H$ then
$c_{+}(H_{n})$ and $c_{-}(H_{n})$ are both Cauchy sequences in $\mathbb{R}$.

Indeed, it follows that the limit $\lim_{n\to\infty}c_{+}(H_{n})$
(respectively $\lim_{n\to\infty}c_{-}(H_{n})$) is independent of the
approximating sequence: If $H^{\prime}_{n}$ and $H^{\prime\prime}_{n}$ are two
approximating sequences for $H$ then so is the mixed sequence that has
$H^{\prime}_{n}$ for $n$ even and $H^{\prime\prime}_{n}$ for $n$ odd. The
proof is trivial:

###### Proof.

For each $j,k\in\mathbb{N}$,

$\displaystyle|c_{+}(H_{j})-c_{+}(H_{k})|\ $ $\displaystyle\leq\ \vvvert
H_{j}-H_{k}\vvvert_{\mathbb{R}^{2}}=\ \vvvert
H_{j}-H_{k}\vvvert_{\mathbb{R}^{2}\backslash\mathbb{D}}\leq\
2\|H_{j}-H_{k}\|_{C^{0}(\mathbb{R}^{2}\backslash\mathbb{D})}\to 0,$

where the first inequality is item (7) in Theorem 6 (since clearly
$c_{+}(H)\leq\gamma(H)$). The same reasoning applies to $c_{-}$. ∎

######  Proposition 12.

Suppose $\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$ is a smooth path of
area preserving diffeomorphisms of the disc starting at the identity. Then the
associated spectral invariants $c_{+}(\tilde{\varphi})$ and
$c_{-}(\tilde{\varphi})$ defined in Definition 10 satisfy:

  1. (1)

$c_{+}(\tilde{\varphi}^{-1})=-c_{-}(\tilde{\varphi})$.

  2. (2)

$c_{-}(\tilde{\varphi})\leq 0\leq c_{+}(\tilde{\varphi})$.

  3. (3)

$c_{+}(\tilde{\varphi}\tilde{\psi})\leq
c_{+}(\tilde{\varphi})+c_{+}(\tilde{\psi})$.

  4. (4)

$\gamma(\tilde{\varphi})\geq\mathrm{area}(U)$ for every displaceable open disc
$U$; meaning $\varphi_{1}(U)\cap U=\emptyset$.

  5. (5)

$\gamma(\tilde{\varphi})\leq\pi$.

  6. (6)

$\gamma(\tilde{\varphi})\leq\vvvert\tilde{\varphi}\vvvert_{\mathbb{D}}$
(notation from Definition 7).

  7. (7)

$H\mapsto c_{+}(\tilde{\varphi}_{H})$ and hence $H\mapsto
c_{-}(\tilde{\varphi}_{H})$ and $H\mapsto\gamma(\tilde{\varphi}_{H})$ are
$1$-Lipschitz with respect to the Hofer norm
$\vvvert\cdot\vvvert_{\mathbb{D}}$, where the latter is in the sense of
Definition 7 for Hamiltonians which may not be supported in the interior of
the disc.

###### Proof.

The proofs of all properties except for Property 5 follow trivially from
Theorem 6 and Definition 10. Property 5 also follows easily from Property 5 of
Theorem 6 if we choose a sequence of approximating Hamiltonians whose support
shrinks to that of the disc in the limit. The existence of such an
approximating sequence with shrinking supports is also easy, but we postpone
this to the next Lemma, since we will there construct an approximating
sequence with additional properties. ∎

For the proofs of Theorems 3 and 4 we will use an approximating sequence with
additional properties:

######  Lemma 13.

Suppose $H\in C^{\infty}\big{(}\mathbb{R}/\mathbb{Z}\times\mathbb{D}\big{)}$
vanishes identically on $\mathbb{R}/\mathbb{Z}\times\partial\mathbb{D}$. Then
there exists an approximating sequence $H_{n}$ for $H$ which satisfies

  1. (1)

$\mathrm{supp\,}H_{n}\subset\mathbb{D}_{1+1/n}$,

  2. (2)

$\sup_{n\in\mathbb{N}}\|\nabla
H_{n}\|_{C^{0}(\mathbb{R}^{2}\backslash\mathbb{D})}<\infty$.

Note that if the supports converge to $\mathbb{D}$ then this is the best we
can expect; in general the second order derivatives of the Hamiltonians
$H_{n}$ will blow up.

###### Proof.

Fix a smooth function $\rho:\mathbb{R}\to\mathbb{R}$ satisfying $\rho(r)=r$ on
$r\leq 0$, $\rho(r)\geq 0$ on $r\geq 0$, and $\rho(r)=0$ on $r\geq 1$. Then
for each $n\in\mathbb{N}$ the function $\rho_{n}:\mathbb{R}\to\mathbb{R}$
given by

$\rho_{n}(r):=\frac{\rho(nr)}{n}$

satisfies: $\rho_{n}(r)=r$ on $r\leq 0$, $\rho_{n}(r)=0$ on $r\geq 1/n$, while
on $r\geq 0$ we have $\rho_{n}\geq 0$,
$\|{\rho_{n}}^{\prime}\|_{C^{0}}\leq\|{\rho}^{\prime}\|_{C^{0}}$ and
$\|{\rho_{n}}\|_{C^{0}}\leq\|{\rho}\|_{C^{0}}/n$. Fix any smooth extension of
$H$ to the whole plane, and denote this also by $H$. In polar coordinates this
is a map
$H:\mathbb{R}/\mathbb{Z}\times[0,\infty)\times\mathbb{R}\to\mathbb{R},(t,r,\theta)\mapsto
H(t,r,\theta)$. Now set

(15) $H_{n}(t,1+r,\theta):=H(t,1+\rho_{n}(r),\theta)\qquad\forall
n\in\mathbb{N}.$

Then $H_{n}(t,\cdot)$ coincides with $H(t,\cdot)$ on the unit disc in
$\mathbb{R}^{2}$ because $\rho_{n}(r)=r$ on $r\leq 0$, and $H_{n}$ is
everywhere smooth. Moreover, $H_{n}$ has compact support, indeed,
$H_{n}(t,\cdot)$ vanishes outside of $\mathbb{D}_{1+1/n}$ because
$\rho_{n}(r)$ vanishes on $r\geq 1/n$ and $H(t,\cdot)$ vanishes
$\partial\mathbb{D}$. The $\theta$-derivative is independent of $n$ so it
suffices to bound the $r$-derivative: From the chain rule
$\|\partial_{r}H_{n}\|_{C^{0}}\leq\|\nabla
H\|_{C^{0}}\|{\rho_{n}}^{\prime}\|_{C^{0}}\leq\|\nabla
H\|\|{\rho}^{\prime}\|_{C^{0}}$ is uniformly bounded in $n$. Finally
$\|H_{n}(t,\cdot)\|_{C^{0}(\mathbb{R}^{2}\backslash\dot{\mathbb{D}})}\to 0$
for $n\to\infty$, uniformly in $t$, because

$\displaystyle\sup\big{\\{}|H_{n}(t,1+r,\theta)|\ \big{|}\ 0\leq r\big{\\}}\ $
$\displaystyle=\ \sup\big{\\{}|H(t,1+\rho_{n}(r),\theta)|\ \big{|}\ 0\leq
r\big{\\}}$ $\displaystyle=\ \sup\big{\\{}|H(t,1+r,\theta)|\ \big{|}\ 0\leq
r\leq\|{\rho_{n}}\|_{C^{0}}\big{\\}}$

which decays to zero as $n\to\infty$, because
$\|{\rho_{n}}\|_{C^{0}}\leq\|{\rho}\|_{C^{0}}/n\to 0$ and $H$ is continuous
and vanishes on $[0,1]\times\partial\mathbb{D}$. ∎

######  Remark 7.

In the proof of Lemma 16 it will be convenient to use a more refined sequence
of approximations $H_{n}$.

In the refined version $H_{n}$ still has the form of (15) and satisfies the
conditions of Lemma 13, but now each $\rho_{n}$ satisfies

(16) $\rho^{\prime}_{n}(r)\geq-1/n$

in addition to the previous properties: $\rho_{n}(r)=r$ on $r\leq 0$,
$\rho_{n}(r)=0$ on $r\geq 1/n$, while on $r\geq 0$ we have $\rho_{n}\geq 0$,
$\|{\rho_{n}}^{\prime}\|_{C^{0}}\leq 1$ and $\|{\rho_{n}}\|_{C^{0}}\leq 1/n$.

One way to achieve this with (16) is to set
$\rho_{n}(r):=\tilde{\rho}_{n}(nr)/n$, where
$\tilde{\rho}_{n}:\mathbb{R}\to\mathbb{R}$ is a smooth function satisfying the
following properties: $\tilde{\rho}_{n}(r)=r$ on $r\leq 0$,
$\tilde{\rho}_{n}(r)\geq 0$ on $r\geq 0$ and $\tilde{\rho}_{n}(r)=0$ on $r\geq
1$, and $1\geq\tilde{\rho}_{n}^{\prime}(r)\geq-1/n$ for all $r$, which can
easily be achieved.

We end this section by showing that the monotonicity property of Theorem 8
extends to non-compactly supported Hamiltonians:

######  Lemma 14.

Suppose $H,G\in C_{c}^{\infty}(\mathbb{R}/\mathbb{Z}\times\mathbb{D})$ are two
Hamiltonians on the disc, both satisfying the boundary condition (14). Then
the extended spectral invariants satisfy

(17) $H\geq G\ \implies\ c_{+}(H)\geq c_{+}(G).$

In general the condition $H\geq G$ on $\mathbb{D}$ cannot hold for smooth
extensions to the plane. So there is something small to check.

###### Proof.

Assume $H\geq G$ and let $H_{n}$ and $G_{n}$ be approximating sequences with
supports in $\mathbb{D}_{1+1/n}$ as in Lemma 13. Let
$\chi:\mathbb{R}^{2}\to[0,1]$ be a smooth function with compact support with
$\chi\equiv 1$ on the disc $\mathbb{D}_{2}$ of radius $2$. For $\epsilon>0$
sufficiently small $2\epsilon\chi$ is sufficiently $C^{2}$-small that
$c_{+}(2\epsilon\chi)\leq\max 2\epsilon\chi=2\epsilon$.

For $n_{0}\in\mathbb{N}$ sufficiently large we have
$\|G_{n}|_{\mathbb{R}^{2}\backslash\mathbb{D}}\|_{\infty}\leq\epsilon$ and
$\|H_{n}|_{\mathbb{R}^{2}\backslash\mathbb{D}}\|_{\infty}\leq\epsilon$ for all
$n\geq n_{0}$, and therefore that $G_{n}$ and $H_{n}$ are smooth extensions of
$G$ and $H$ respectively to the plane, having compact support and satisfying
$G_{n}\leq H_{n}+2\epsilon\chi$ on $\mathbb{R}^{2}$. So by Theorem 8
$c_{+}(G_{n})\leq c_{+}(H_{n}+2\epsilon\chi)$. Therefore, for all $n\geq
n_{0}$,

$c_{+}(G_{n})\leq c_{+}(H_{n}+2\epsilon\chi)\leq
c_{+}(H_{n})+c_{+}(2\epsilon\chi)\leq c_{+}(H_{n})+2\epsilon$

where the second inequality is from the Lipschitz continuity of $c_{+}$ with
respect to the Hofer norm, (12). Letting $n\to\infty$ we conclude
$c_{+}(G)\leq c_{+}(H)+2\epsilon$ for each $\epsilon>0$ as required.

∎

##  4\. Proof of Theorems 3 and 4

Now we can prove Theorem 3 using an approximating sequence of Hamiltonians
that have the properties provided by Lemma 13. Throughout this section we
assume for convenience that the area of the disc is $\pi$, which leads to
Theorem 3 with $A=\pi$. We begin with:

######  Lemma 15.

For any $C^{1}$-differentiable loop
$x:[0,1]\to\mathbb{D}_{1+\delta}\backslash\dot{\mathbb{D}}$, $\delta>0$, there
holds

(18) $\left|\int_{D}u^{*}\omega-\pi\deg(x)\right|\ \leq\ L(x)\delta$

where $u$ is any capping disc for $x$, and $\deg(x)\in\mathbb{Z}$ is the
winding number of $x$ about the disc, i.e. about any point in $\mathbb{D}$,
and $L(x)$ is the Euclidean length of $x$.

###### Proof.

Let $x:[0,1]\to\mathbb{D}_{1+\delta}\backslash\dot{\mathbb{D}}$ be a
continuously differentiable closed curve. Note that each of the three terms in
(18) is additive with respect to concatenation of closed curves, and that $x$
can be written as a finite sum (more precisely a concatenation) of simple
closed curves, because it is $C^{1}$. Hence it suffices to prove (18) for
simple closed curves. Therefore let us suppose that $x$ is simple, i.e.
$x(t_{1})=x(t_{2})$ implies $t_{1}=t_{2}$ or $t_{1},t_{2}\in\\{0,1\\}$. If $x$
is contractible in $\mathbb{D}_{1+\delta}\backslash\dot{\mathbb{D}}$, then we
can lift it to a simple closed curve $\tilde{x}$ in the covering
$\mathbb{R}\times[0,\delta]$ via the projection $\pi(u,v)=(1+v)e^{2\pi iu}$.
If the image of $\tilde{x}$ lies in the rectangle $[a,b]\times[0,\delta]$,
then it encloses an area at most $2\pi(b-a)\delta$ with respect to
$\pi^{*}\omega$. Clearly $2\pi(b-a)$ is bounded by half of the (euclidean)
length of $\tilde{x}$ in $\mathbb{R}\times[0,\delta]$, which is bounded by
$L(x)/2$. So the area enclosed by $x$ equals the $\pi^{*}\omega$-area enclosed
by $\tilde{x}$, is bounded by $L(x)\delta/2$, i.e.,
$\left|\int_{D}u^{*}\omega-\pi\deg(x)\right|\leq L(x)\delta/2$ as the degree
term vanishes. If however the simple closed curve $x$ is non-contractible in
$\mathbb{D}_{1+\delta}\backslash\dot{\mathbb{D}}$ then $\deg(x)\in\\{\pm 1\\}$
and we see that
$\left|\int_{D}u^{*}\omega-\pi\deg(x)\right|\leq(1+\delta)^{2}\pi-\pi\leq(2\pi)\delta\leq
L(x)\delta$. This completes the proof of (18) when $x$ is simple, and
therefore also the general case. ∎

###### Proof.

(Of Theorem 3) It suffices to prove the statements for $c_{+}$, as the
statement for $c_{-}$ follows then from the first property of Proposition 12.
For $c_{+}$ it suffices to show that

(19)
$c_{+}(\tilde{\varphi})\in\mathcal{S}(\tilde{\varphi})\cup\\{0\\}\cup\\{\pi\\}$

and the usual arguments will then imply that $c_{+}(\tilde{\varphi})$ is
invariant under homotopies of $\tilde{\varphi}$ through isotopies with fixed
endpoints: Indeed, $\mathcal{S}(\tilde{\varphi})\cup\\{0\\}\cup\\{\pi\\}$ is a
closed nowhere dense set (closed is straightforward to see, and after
extending a generating Hamiltonian for $\tilde{\varphi}$ to all of
$\mathbb{R}^{2}$ with compact support it is a classical result that the
spectrum is nowhere dense, see for example [18], and the extension only
increases the set of spectral values) and we already showed that
$c_{+}(\tilde{\varphi})$ depends continuously on $\tilde{\varphi}$ in the
$C^{0}$-topology.

We now show (19). Fix a generating Hamiltonian $H\in
C^{\infty}\big{(}\mathbb{R}/\mathbb{Z}\times\mathbb{D}\big{)}$ with
$H_{t}(z)=0$ for all $t\in[0,1]$, $z\in\partial\mathbb{D}$, for the given path
$\tilde{\varphi}=\\{\varphi_{t}\\}_{t\in[0,1]}$. Let $H_{n}\in
C^{\infty}\big{(}\mathbb{R}/\mathbb{Z}\times\mathbb{R}^{2}\big{)}$ for
$n\in\mathbb{N}$ be an approximating sequence for $H$ as in Lemma 13. In
particular $\mathrm{supp\,}H_{n}\subset\mathbb{D}_{1+1/n}$ and the gradients
are uniformly bounded. Since $\lim_{n\to\infty}c_{+}(H_{n})=c_{+}(H)$ and
$0\leq c_{+}(H_{n})\leq\mathrm{Area}(\mathrm{supp\,}H_{n})\to\pi$ it follows
that $c_{+}(H)\in[0,\pi]$. Therefore let us assume that $0<c_{+}(H)<\pi$ and
show that $c_{+}(H)\in\mathcal{S}(\tilde{\varphi})$. For sufficiently large
$n$ we must have

(20) $\varepsilon<c_{+}(H_{n})<\pi-\varepsilon$

for some sufficiently small $\varepsilon>0$. By definition we find for each
$n\in\mathbb{N}$ a $1$-periodic orbit $x_{n}\in
C^{\infty}(\mathbb{R}/\mathbb{Z},\mathbb{R}^{2})$ for $H_{n}$ with action
$\mathcal{A}_{H}(x_{n})=c_{+}(H_{n})$. By (20) this is non-zero, so $x_{n}$
lies in the support of $H_{n}$, namely in $\mathbb{D}_{1+1/n}$. Now if $x_{n}$
is contained in $\mathbb{D}$ for some subsequence, then we are done, since
$H_{n}$ agrees with $H$ on $\mathbb{D}$. So without loss of generality let us
assume $x_{n}\subset A_{n}:=\mathbb{D}_{1+1/n}\backslash\mathbb{D}$ for all
$n\in\mathbb{N}$. Using (11)

(21) $\displaystyle c_{+}(H_{n})$
$\displaystyle=\int_{0}^{1}H_{n}(t,x_{n}(t))\,dt\ +\ \int_{D}u_{n}^{*}\omega$

where $u_{n}:D\to\mathbb{R}^{2}$ is any capping disc for $x_{n}$. As
$n\to\infty$ the first term on the right decays to zero, because $H_{n}$
converges uniformly to zero outside of the interior $\dot{\mathbb{D}}$. It
remains to understand the second term on the right of (21). Applying Lemma 15
we have

$\left|\int_{D}u_{n}^{*}\omega-\pi\deg(x_{n})\right|\ \leq\
L(x_{n})\frac{1}{n}$

for each $n\in\mathbb{N}$. As $\|\dot{x}_{n}\|=\|X_{H_{n}}(x_{n})\|$ are
uniformly bounded, so is $L(x_{n})$ uniformly bounded. Thus letting
$n\to\infty$ in the last line yields
$\lim_{n\to\infty}d(\int_{D}u_{n}^{*}\omega,\pi\mathbb{Z})=0$, where
$d(\cdot,\cdot)$ denotes the distance, and so from (21) we have
$\lim_{n\to\infty}d(c_{+}(H_{n}),\pi\mathbb{Z})=0$, contradicting (20). This
completes the proof. ∎

Now we prove Proposition 5:

###### Proof.

(Of Proposition 5) Suppose $\rho>0$. By Theorem 3 $c_{+}(\tilde{\varphi})$
depends only on the homotopy class of $\tilde{\varphi}$ with fixed ends. So we
may assume, after such a homotopy, that the Hamiltonian vector field is
autonomous on the boundary of the disc - this is stronger than necessary, it
suffices that $X_{H^{t}}$ is nowhere vanishing on $\partial\mathbb{D}$. It
follows that at each point $p\in\partial\mathbb{D}$, we have
$-\partial_{r}H^{t}(p)=d\theta[X_{H^{t}}]>0$ on $\partial\mathbb{D}$, and
therefore there exists $\epsilon>0$ so that

(22) $H^{t}(z)>0\qquad\mbox{for all}\quad 1-2\epsilon\leq|z|^{2}<1.$

We now construct a Hamiltonian function $G$ on the disc, so that $G\leq H$ and
so that $c_{+}(\varphi_{G})>0$. Then the result will follow from Lemma 14.

We construct $G$ to be time independent, compactly supported in
$\dot{\mathbb{D}}$, and radial. Indeed, for each parameter $\lambda\leq 0$
consider $G_{\lambda}(z)=g_{\lambda}(|z|^{2})$ for some smooth function
$g_{\lambda}:[0,\infty)\to\mathbb{R}$ whose graph has the following features:
$g_{0}\geq 0$ is compactly supported in the interior of the region
$1-\epsilon\leq r\leq 1$ and has a single positive bump, meaning it has a
unique maximum and no other critical points in its support. We can arrange
that $g_{0}$ is sufficiently small that $G_{0}<H$ on the annulus
$1-2\epsilon\leq|z|^{2}<1$, which is possible because of (22). For
$\lambda\leq 0$ we choose $g_{\lambda}$ to satisfy the following:
$g_{\lambda}=\lambda$ on $0\leq r\leq 1-2\epsilon$, $g_{\lambda}$ is a
monotonic increasing function on $1-2\epsilon\leq r\leq 1-\epsilon$ with
$g_{\lambda}=0$ near to $r=1-\epsilon$, and $g_{\lambda}=g_{0}$ on $r\geq
1-\epsilon$. For example, fix $g_{0}$ and $g_{-1}$ satifying the above
properties, then set $g_{\lambda}=|\lambda|g_{-1}$ on $r\leq 1-\varepsilon$
and $g_{\lambda}=g_{0}$ on $r\geq 1-\epsilon$, then the dependence on
$\lambda$ is also smooth.

Figure 1. Here the graph of $g_{\lambda}$ at $\lambda=\lambda_{0}$

Clearly the maximum value $M>0$ is independent of $\lambda\leq 0$. For
$\lambda=0$ we have $G_{0}\geq 0$, and it is somewhere strictly positive so
$c_{+}(G_{0})>0$. Therefore $c_{+}(G_{0})$ is a positive spectral value, i.e.
lies in $\mathcal{S}(G_{0})\cap(0,\infty)$. More generally for $\lambda\leq
0$, we know that $G_{\lambda}$ lies in
$\mathcal{S}(G_{\lambda})\cap[0,\infty)$. Since $G_{\lambda}$ is radial it
follows from a computation that the values in
$\mathcal{S}(G_{\lambda})\cap[0,\infty)$ are precisely the points on the non-
negative $y$-axis where each tangent line to the graph of $g_{\lambda}$ having
integer slope $k\geq 0$, meets the $y$-axis, see [7]. From this it is easy to
see that $\mathcal{S}(G_{\lambda})\cap[0,\infty)$ lies in the set
$\\{0\\}\cup[M,\infty)$. Therefore $\lambda\mapsto c_{+}(G_{\lambda})$ is a
continuous map into $\\{0\\}\cup[M,\infty)$ which takes the value $M>0$ at
$\lambda=0$. Hence $c_{+}(G_{\lambda})\geq M>0$ for all $\lambda\leq 0$.
Finally we set $G=G_{\lambda}$ for some
$\lambda<\min\\{H^{t}(z)\,|\,t\in\mathbb{R}/\mathbb{Z}\\}$. Then $G\leq H$.

If $\rho<0$ then the result follows from the case above together with item 1
of Proposition 12. ∎

To prove Theorem 4 we will use:

######  Lemma 16.

Suppose that the rotation number on the boundary satisfies
$|\rho(\tilde{\varphi}|_{\partial\mathbb{D}})|<1$, and that the generating
Hamiltonian $H$ has autonomous Hamiltonian vector field on the boundary of the
disc. Let $H_{n}$ be the approximating sequence of Lemma 13 with the extra
property described in Remark 7. Then if $n$ is sufficiently large, every
time-$1$ orbit segment $x_{n}:[0,1]\to\mathbb{R}^{2}$ for $H_{n}$ that lies in
$\mathbb{R}^{2}\backslash\dot{\mathbb{D}}$ has winding about the origin
satisfying $|\mathrm{wind}(x_{n})|<1$.

In the above statement $\mathrm{wind}(x_{n}):=(\theta(1)-\theta(0))/2\pi$, if
$x_{n}(t)=(r(t),e^{i\theta(t)})$.

###### Proof.

By assumption each $X_{H}$-trajectory on the boundary of the disc
$t\mapsto(1,\theta):[0,1]\to\partial\mathbb{D}$ satisfies
$|\theta(1)-\theta(0)|/2\pi<1-\epsilon$ for some uniform $\epsilon>0$. We
consider two cases separately.

Case 1: Here we consider the case that $\partial_{r}H(1,\theta)\geq 0$ for all
$\theta\in\mathbb{R}$. The case $\partial_{r}H(1,\theta)\leq 0$ can be handled
similarly.

Note that the vector field $X_{H^{t}}$ at a point
$(1,\theta)\in\partial\mathbb{D}$ has angular component
$d\theta\big{[}X_{H^{t}}(1,\theta)\big{]}=-\partial_{r}H^{t}(1,\theta)$.
Applying Gronwall’s Lemma to the vector fields
$\partial_{r}H|_{\partial\mathbb{D}}$ and
$-\partial_{r}H|_{\partial\mathbb{D}}$ there exists $\delta>0$ so that if $V$
is any smooth vector field on $\partial\mathbb{D}$ with
$\|V-\partial_{r}H|_{\partial\mathbb{D}}\|<2\delta$ or
$\|V+\partial_{r}H|_{\partial\mathbb{D}}\|<2\delta$, then each $V$-trajectory
$[0,1]\to\partial\mathbb{D}$, $t\mapsto(1,\psi(t))$ satisfies
$|\psi(1)-\psi(0)|/2\pi<1-\epsilon/2<1$.

Recall, as in Lemma 13, that by slight abuse of notation, $H$ also refers to a
fixed smooth extension (of $H$) to all of $\mathbb{R}^{2}$. Choose
$n_{0}\in\mathbb{N}$ sufficiently large that

(23)
$|\partial_{r}H^{t}(1+\rho_{n}(r),\theta)-\partial_{r}H(1,\theta)|<\delta$

for all $r\geq 0$, $\theta\in\mathbb{R}$, $t\in[0,1]$, $n\geq n_{0}$. The
vector field $X_{H^{t}_{n}}$ has angular component
$d\theta\big{[}X_{H^{t}_{n}}(1+r,\theta)\big{]}=-\partial_{r}H^{t}_{n}(1+r,\theta)=-\rho^{\prime}_{n}(r)\partial_{r}H^{t}(1+\rho_{n}(r),\theta)$,
and so

(24)
$\left|d\theta\big{[}X_{H^{t}_{n}}(1+r,\theta)\big{]}\right|\leq\left|\partial_{r}H(1,\theta)\right|+\delta$

by (23), when $n\geq n_{0}$. Consider an arbitrary $X_{H^{t}_{n}}$-trajectory
$x(t)=(r(t),\theta(t))$ in $\mathbb{R}^{2}\backslash\dot{\mathbb{D}}$. Then by
(24) and our assumption that $\partial_{r}H(1,\theta)\geq 0$ everywhere,

$-\partial_{r}H(1,\theta(t))-\delta\leq\dot{\theta}(t)\leq\partial_{r}H(1,\theta(t))+\delta$

for all $t$. Hence $t\mapsto\theta(t)$ is squeezed:
$\psi_{-}(t)\leq\theta(t)\leq\psi_{+}(t)$, where
$\dot{\psi}_{+}(t)=\partial_{r}H(1,\psi_{+}(t))+\delta$ with initial condition
$\psi_{+}(0)=\theta(0)$, and
$\dot{\psi}_{-}(t)=-\partial_{r}H(1,\psi_{-}(t))-\delta$ with
$\psi_{-}(0)=\theta(0)$. Thus
$\mathrm{wind}(x)\leq(\psi_{+}(1)-\psi_{+}(0))/2\pi<1$, where the last
inequality is from Gronwall, since the vector field
$V(1,\theta)=\partial_{r}H(1,\theta)+\delta$ is within $\delta$ of
$\partial_{r}H(1,\theta)$. Similarly
$\mathrm{wind}(x)\geq(\psi_{-}(1)-\psi_{-}(0))/2\pi>-1$ where the last
inequality is from Gronwall, since
$V(1,\theta)=-\partial_{r}H(1,\theta)-\delta$ is within $\delta$ of
$-\partial_{r}H(1,\theta)$. This proves the Lemma in Case 1.

Case 2: Here we consider the case that $\partial_{r}H(1,\theta)$ changes sign:
Then the sets

$\Omega^{+}=\\{(1,\theta)\in\partial\mathbb{D}|\partial_{r}H(1,\theta)>0\\},\qquad\Omega^{-}=\\{(1,\theta)\in\partial\mathbb{D}|\partial_{r}H(1,\theta)<0\\}$

are both non-empty and open. We claim that for any $\delta>0$ there exists
$n_{0}\in\mathbb{N}$ sufficiently large so that if $x(t)=(r(t),\theta(r))$ is
an $X_{H^{t}_{n}}$-trajectory in $\mathbb{R}^{2}\backslash\dot{\mathbb{D}}$,
and $n\geq n_{0}$, then

(25)
$\qquad\theta(t)\in\Omega^{-}\implies\dot{\theta}(t)\geq-\delta,\qquad\theta(t)\in\Omega^{+}\implies\dot{\theta}(t)\leq\delta.$

Assuming this claim for the moment, let’s see how to complete the proof of the
Lemma in Case 2: Fix two intervals of positive length
$I^{+}\subset\Omega^{+}$, $I^{-}\subset\Omega^{-}$, and choose $\delta>0$ so
that $\delta<(1/2)\min\\{|I^{+}|,|I^{-}|\\}$. If $n$ is sufficiently large
then by the first statement in (25) $t\mapsto\theta(t)$ can never get more
than half way across $I^{-}$ in a negative direction, so
$\mathrm{wind}(x_{n})\geq-1+(1/2)|I^{-}|$. Similarly, from the second
statement in (25), $t\mapsto\theta(t)$ can never get more than half way across
$I^{+}$ in a positive direction, so $\mathrm{wind}(x_{n})\leq 1-(1/2)|I^{+}|$.
Thus $|\mathrm{wind}(x_{n})|<1$.

It remains to prove the claim (25). Let us show
$\theta(t)\in\Omega^{-}\implies\dot{\theta}(t)\geq-\delta$, as the proof of
the second inequality in (25) is analogous. Since
$\partial_{r}H^{t}|_{\partial\mathbb{D}}=\partial_{r}H|_{\partial\mathbb{D}}<0$
on $\Omega^{-}$, there exists $\epsilon_{0}>0$ so that
$-M\leq\partial_{r}H^{t}(1+r,\theta)\leq\delta$ for all $0\leq
r\leq\epsilon_{0}$ and all $\theta\in\Omega^{-}$, where
$M:=2\|\partial_{r}H|_{\partial\mathbb{D}}\|_{\infty}$. Choose
$n_{0}\in\mathbb{N}$ sufficiently large that $\max\rho_{n_{0}}<\epsilon_{0}$
and $\min\rho^{\prime}_{n_{0}}>-\delta/M$ (this latter condition is possible
because we are using $\rho_{n}$ as in Remark 7). Now, suppose
$\theta(t)\in\Omega^{-}$ and $n\geq n_{0}$. Then

(26)
$\dot{\theta}(t)=d\theta\big{[}X_{H^{t}_{n}}(1+r(t),\theta(t))\big{]}=\rho_{n}^{\prime}(r(t))\big{[}-\partial_{r}H^{t}(1+\rho_{n}(r(t)),\theta(t))\big{]}.$

If $0\leq\rho^{\prime}_{n}(r(t))\leq 1$ then the right hand side is bounded
from below by $-\partial_{r}H^{t}(1+\rho_{n}(r(t)),\theta(t))$, which in turn
is bounded from below by $-\delta$ because
$0\leq\rho_{n}(r(t))\leq\max\rho_{n_{0}}<\epsilon_{0}$. The alternative is
that $0>\rho^{\prime}_{n}(r(t))\geq\min\rho^{\prime}_{n}>-\delta/M$. In this
case the right hand side of (26) is bounded from below by
$(-\delta/M)M=-\delta$, as required. ∎

###### Proof.

(Of Theorem 4)

We will prove statements (i) and (ii) which concern $c_{+}(\tilde{\varphi})$,
as $c_{-}$ then follows from the first item in Proposition 12.

By Theorem 3 $c_{+}(\tilde{\varphi})$ depends only on the homotopy class of
$\tilde{\varphi}$ with fixed ends. So we may assume, after such a homotopy,
that the Hamiltonian vector field is autonomous on the boundary of the disc.
We do this to apply Lemma 16.

First we show (i) when $\rho=1$. In this case the boundary of the disc has a
fixed point and it will have action $A$, so $A$ lies in the spectrum. So then
(i) follows from Theorem 3.

Now we show (i) when $|\rho|<1$. Fix an approximating sequence of Hamiltonians
$H_{n}$ for $H$, that satisfy the conditions of Lemma 13 as well as those in
Remark 7. We have $c_{+}(H_{n})=\mathcal{A}_{H_{n}}(x_{n})\to
c_{+}(\tilde{\varphi})$ for $n\to\infty$, for some $1$-periodic orbits $x_{n}$
of $H_{n}$. If each $x_{n}$ lies in the disc $\mathbb{D}$, then
$c_{+}(H_{n})=\mathcal{A}_{H_{n}}(x_{n})=\mathcal{A}_{H}(x_{n})$ is a spectral
value of $H$, so we are done, since $\mathcal{S}(H)$ is closed222Or we note
that the sequence $H_{n}$ lies in a continuous family of Hamiltonians with
$n\in[1,\infty)$ (since $\rho_{n}$ makes sense for non-integer values of $n$),
and so by continuity of the spectral invariants and discreteness of the
spectrum of $H|_{\mathbb{D}}$ we conclude that the sequence $c_{+}(H_{n})$ is
constant in $n$ since each $x_{n}$ lies in $\mathbb{D}$.. The alternative,
after restricting to a subsequence, is that each $x_{n}$ is in
$\mathbb{R}^{2}\backslash\mathbb{D}$.

Since $|\rho|<1$ we have $|\mathrm{wind}(x_{n})|<1$ by Lemma 16, i.e.
$\deg(x_{n})=0$, for each $n$. It follows from Lemma 15 that
$|\int_{D}u_{n}^{*}\omega|\to 0$ (the length of each $x_{n}$ is uniformly
bounded because $\nabla H_{n}$ is uniformly bounded). Clearly
$\int_{0}^{1}H_{n}^{t}(x_{n}(t))dt\to 0$ also, because $H_{n}\to 0$ uniformly
on $\mathbb{R}^{2}\backslash\dot{\mathbb{D}}$. We conclude that
$c_{+}(\tilde{\varphi})=\lim_{n\to\infty}\mathcal{A}_{H_{n}}(x_{n})=0$ and
again we are done. This completes the proof of statement (i).

To show statement (ii): If $\rho=0$ then due to a fixed point on the boundary
we know that zero lies in the spectrum, so the statement follows from (i). If
instead $\rho>0$, then by Proposition 5 again the statement follows from (i).
∎

## References

  * [1] Alberto Abbondandolo, Barney Bramham, Umberto L Hryniewicz, and Pedro A. S. Salomão.  Sharp systolic inequalities for Reeb flows on the three-sphere.  Inventiones mathematicae, 211:687–778, 2018.
  * [2] Lev Buhovsky, Vincent Humiliere, and Sobhan Seyfaddini.  The action spectrum and ${C}^{0}$ symplectic topology.  Mathematische Annalen, 380(1-2):293–316, 2021.
  * [3] Dan Cristofaro-Gardiner, Rohil Prasad, and Boyu Zhang.  Periodic floer homology and the smooth closing lemma for area-preserving surface diffeomorphisms.  arXiv preprint arXiv:2110.02925, 2021.
  * [4] Daniel Cristofaro-Gardiner, Michael Hutchings, and Vinicius Gripp Barros Ramos.  The asymptotics of ECH capacities.  Inventiones mathematicae, 199(1):187–214, 2015.
  * [5] Urs Frauenfelder and Felix Schlenk.  Hamiltonian dynamics on convex symplectic manifolds.  Israel Journal of Mathematics, 159(1):1–56, 2007.
  * [6] Helmut Hofer and Eduard Zehnder.  A new capacity for symplectic manifolds.  In Analysis, et cetera, pages 405–427. Elsevier, 1990.
  * [7] Vincent Humilière, Frédéric Le Roux, and Sobhan Seyfaddini.  Towards a dynamical interpretation of Hamiltonian spectral invariants on surfaces.  Geometry & Topology, 20(4):2253–2334, 2016.
  * [8] Michael Hutchings.  Mean action and the Calabi invariant.  Journal of Modern Dynamics, 10(2):511–539, 2016.
  * [9] Yusuke Kawamoto.  On ${C}^{0}$-continuity of the spectral norm for symplectically non-aspherical manifolds.  International Mathematics Research Notices, 2022(21):17187–17230, 2022.
  * [10] Sergei Lanzat.  Hamiltonian Floer homology for compact convex symplectic manifolds.  Beiträge zur Algebra und Geometrie/Contributions to Algebra and Geometry, 57:361–390, 2016.
  * [11] Patrice Le Calvez.  A finite dimensional proof of a result of Hutchings about irrational pseudo-rotations.  Journal de l’École polytechnique — Mathématiques, 10:837–866, 2023.
  * [12] Dusa McDuff and Dietmar Salamon.  Introduction to symplectic topology, volume 27.  Oxford University Press, 2017.
  * [13] Jo Nelson and Morgan Weiler.  Torus knotted reeb dynamics and the calabi invariant.  arXiv preprint arXiv:2310.18307, 2023.
  * [14] Yong-Geun Oh.  Construction of spectral invariants of Hamiltonian paths on closed symplectic manifolds.  In The Breadth of Symplectic and Poisson Geometry: Festschrift in Honor of Alan Weinstein, pages 525–570. Springer, 2005.
  * [15] Yong-Geun Oh.  Locality of continuous Hamiltonian flows and Lagrangian intersections with the conormal of open subsets.  Journal of Gökova Geometry Topology, 1:1–32, 2007.
  * [16] Abror Pirnapasov.  Hutchings’ inequality for the Calabi invariant revisited with an application to pseudo-rotations.  arXiv preprint arXiv:2102.09533, 2021.
  * [17] Abror Pirnapasov and Rohil Prasad.  Generic equidistribution for area-preserving diffeomorphisms of compact surfaces with boundary.  arXiv preprint arXiv:2211.07548, 2022.
  * [18] Matthias Schwarz.  On the action spectrum for closed symplectically aspherical manifolds.  Pacific Journal of Mathematics, 193(2):419–461, 2000.
  * [19] Sobhan Seyfaddini.  ${C}^{0}$-limits of Hamiltonian paths and the Oh–Schwarz spectral invariants.  International Mathematics Research Notices, 2013(21):4920–4960, 2013.
  * [20] Claude Viterbo.  Symplectic topology as the geometry of generating functions.  Mathematische Annalen, 292(1):685–710, 1992.
  * [21] Morgan Weiler.  Mean action of periodic orbits of area-preserving annulus diffeomorphisms.  Journal of Topology and Analysis, 13(04):1013–1074, 2021.