# Low-level Pose Control of Tilting Multirotor for Wall Perching Tasks Using
Reinforcement Learning

Hyungyu Lee1, Myeongwoo Jeong2, Chanyoung Kim2, Hyungtae Lim1, Changgue Park3,
Sungwon Hwang1, and Hyun Myung1, Senior Member, IEEE This research was
supported by the National Research Foundation of Korea (NRF) Grant funded by
the Ministry of Science and ICT for First-Mover Program for Accelerating
Disruptive Technology Development (NRF-2018M3C1B9088328). The students are
supported by the BK21 FOUR from the Ministry of Education (Republic of
Korea).1Hyungyu Lee, 1Hyungtae Lim, 1Sungwon Hwang, and 1Hyun Myung are with
Urban Robotics Lab, KAIST2Myeongwoo Jeong and 2Chanyoung Kim are undergraduate
interns of Urban Robotics Lab, KAIST3Changgue Park is with Korea Electronics
Technology Institute(KETI)

###### Abstract

Recently, needs for unmanned aerial vehicles (UAVs) that are attachable to the
wall have been highlighted. As one of the ways to address the need, researches
on various tilting multirotors that can increase maneuverability has been
employed. Unfortunately, existing studies on the tilting multirotors require
considerable amounts of prior information on the complex dynamic model.
Meanwhile, reinforcement learning on quadrotors has been studied to mitigate
this issue. Yet, these are only been applied to standard quadrotors, whose
systems are less complex than those of tilting multirotors. In this paper, a
novel reinforcement learning-based method is proposed to control a tilting
multirotor on real-world applications, which is the first attempt to apply
reinforcement learning to a tilting multirotor. To do so, we propose a novel
reward function for a neural network model that takes power efficiency into
account. The model is initially trained over a simulated environment and then
fine-tuned using real-world data in order to overcome the sim-to-real gap
issue. Furthermore, a novel, efficient state representation with respect to
the goal frame that helps the network learn optimal policy better is proposed.
As verified on real-world experiments, our proposed method shows robust
controllability by overcoming the complex dynamics of tilting multirotors.

###### Index Terms:

UAV, tiltable multirotor UAV, reinforcement learning

##  I Introduction

The application of multirotors to replace various tasks in different fields
has gained popularity in recent years [1, 2, 3]. Despite the rapid development
of multirotors, they are not yet suitable for tasks related to the maintenance
of large structures such as skyscrapers or bridges that require external
cleaning and inspection. That is because conventional quadcopters cannot
maintain their position while changing the orientation due to the limited
maneuverability.

Figure 1: Schematic diagram of our entire process. In the simulation, the
platform learns to hover, tilt, and perch sequentially using the policy and
value networks. Through the learning with actual flight experiences, the
nonlinear sim-to-real gap has been reduced. This learning process using real-
world data can be seen as transfer learning.

Various tilting multirotor UAVs have been studied to increase maneuverability
[4, 5, 6, 10, 7, 8, 9]. Some of the studies demonstrate a superior ability to
respond to disturbances faster [11, 12] and perform complex tasks owing to
improved mobility [13]. However, because it is challenging to control the
tilting multirotor owing to increased maneuverability, the control plays
another critical role in tilting multirotor systems. Generally, multirotor
control tasks are mainly categorized into two methodologies: a high-level
control that performs mission, navigation, planning, and a low-level control
that performs stabilization and motion control. In this study, we place more
emphasis on low-level control, particularly pose control. A multirotor is an
unstable and nonlinear system by nature, which makes the control task to be
challenging. Furthermore, in tilting multirotors, as servomotors are added to
the multirotor system, the nonlinearity of the system increases due to
interference caused by airflow between the tilting propellers. It is also more
challenging to control due to the difference in response times between the
servomotor and the rotor. To tackle these issues, various control strategies
have been proposed. For instance, proportional-integral-derivative (PID)
controllers are the renowned method [4, 5, 6, 10, 7, 8, 9], yet it requires
accurate modeling and measurement of the system. Furthermore, many trials and
errors are necessary to determine the optimal PID gain.

Meanwhile, various attempts have been made toward the control of multirotors
at low levels using reinforcement learning to solve this classical control
technique [14, 16, 15]. These studies have broadened the scope of researches
on controlling multirotors through reinforcement learning. A previous study
used a controller learned in the simulation in an actual quadrotor to enable
stable control under hovering and dynamic initial conditions [14]. This
approach shows that reinforcement learning trained in simulation environments
opens the possibilities to low-level control real-world multirotors. However,
the methodology does not directly address the sim-to-real gap issue.

To resolve the sim-to-real gap, a novel online learning method was proposed
[15] that uses real-world flight data to overcome the gap, showing the
feasibility of learning real-world data on a quadrotor. Furthermore, another
methodology attempt to learn directly on a real quadrotor using model-based
reinforcement learning [16]. However, the previous approaches are solely
conducted on a quadrotor, where the sim-to-real gap is relatively smaller than
that of a tilting multirotor. Furthermore, there has been a study to reduce
the sim-to-real gap based on a previously trained module before the training
on simulations called actuator net, which helps the network learn the
nonlinear relationship between input and output better [17]. Unfortunately, it
is a quadruped robot-based method, so it is not directly applicable on
quadrotor platforms.

The higher complexity of the system due to additional actuators and the
difference of response time between actuators are two main causes that make
the tilting multirotor control a challenging problem. We leverage the
nonlinearity of the neural networks to tackle the issue, which can adapt to
complex nonlinear approximation. Additionally, rotor outputs cannot be
uniquely determined if the number of the actuators is larger than the force
and moment expressed in the body frame. We have overcome these problems and
present a novel control strategy that controls the tilting multirotor using
reinforcement learning.

In summary, the contributions of this paper are fourfold:

  * •

To the best of our knowledge, it is the first attempt to perform low-level
pose control of a tilting multirotor using reinforcement learning.

  * •

We propose a goal-centric representation of pose that minimizes the amount of
data required for optimal policy learning and reduces the ambiguity of the
conventional state representation. Because the tilting multirotor is more
complex than a conventional quadrotor system, more data is required for
learning. The proposed pose representation method helps to overcome the
problem.

  * •

An appropriate novel reward function is proposed by taking power consumption
into account, which can be applied to platforms such as hexacopters, where the
number of actuators is larger than the number of force and moment. The
proposed reward function is more power-efficient and converges to a more
stable policy compared to the conventional reward function used for the
quadrotors.

  * •

The data augmentation method using the symmetry of drone dynamics suitable for
the tilting multirotor domain was proposed. This can reduce the number of
training data required for training.

The remainder of the paper is organized as follows. Section II introduces the
background including the description of the platform. Section III describes
the method, network structure, value network, and policy network learning
method. Section IV presents the simulation environment, reward function, and
the curriculum learning. The settings and results of the experiment are
presented in Section V and conclusions are drawn in Section VI.

##  II Background

###  II-A Tilting Multirotor Platform

Figure 2: (a) The tilting mechanism of the platform. A servo motor rotates
with respect to the tilable axle. (b) Coordinate frames of the platform.
$\\{I\\}$,$\\{B\\}$,$\\{A\\}$ and $\\{G\\}$ stand for the inertial, body,
tilting axle, and goal frames, respectively.

In this section, the platform and terminologies used in the study are
summarized. The platform is based on a coaxial hexacopter, and in order for
the platform to stably perch against a wall, it must be able to maintain its
position even when the pitch of the drone is not zero. To make this physically
possible, a servo motor is added to allow the propeller to rotate about the
$y_{{A}}$-axis. To prevent the propeller from colliding to the wall during
rotation, an offset is set between the rotor and the tilting shaft. Rotation
angle of the servo motor angle $\alpha$ is constrained to range between 0° and
120°. Detailed effect of the rotor offset is not mentioned because it is
beyond the scope of this paper. $T_{i}$ represents the thrust of the $i$-th
rotor. Body frame of the drone $\\{B\\}$ is located at the center of gravity.
The arm frame $\\{A\\}$ is the frame rotated by $\mathrm{\alpha}$, and
$T_{1}\mathrm{\ \sim\ }T_{4}$ have the same frame as $\\{A\\}$.
$T_{5}\mathrm{\ \sim\ }T_{6}$ have the same frame as that of $\\{B\\}$. The
goal frame $\\{G\\}$ is a frame rotated at $\psi$ in the $z$-axis with respect
to the inertial frame. Assuming that the weight of the arm is negligible, the
equation of motion can be expressed using the Newton-Euler equation for a
single rigid body. The equation is as follows:

$\begin{bmatrix}m\mathbf{I_{3}}&0\\\
0&\mathbf{J}(\alpha)\end{bmatrix}\begin{bmatrix}\dot{\mathbf{v}}^{B}\\\
\dot{\boldsymbol{\upomega}}^{B}\end{bmatrix}+\begin{bmatrix}\boldsymbol{\upomega}^{B}\times(m\cdot\mathbf{v}^{B})\\\
\boldsymbol{\upomega}^{B}\times(\mathbf{J}(\alpha)\cdot\boldsymbol{\upomega}^{B})\end{bmatrix}=\begin{bmatrix}\mathbf{F}^{B}\\\
\mathbf{M}^{B}\end{bmatrix}$ (1)

where $m$ is the mass, $\mathbf{J}(\alpha)$ inertial tensor with respect to
$\mathbf{\alpha}$, $\mathbf{I_{3}}$ $3\times 3$ identity matrix, $\mathbf{v}$
the linear velocity, $\boldsymbol{\upomega}$ the angular velocity,
$\mathbf{F}=[F_{x}\;F_{y}\;F_{z}]^{T}$ the force, and
$\mathbf{M}=[M_{x}\;M_{y}\;M_{z}]^{T}$ the moment. The superscript $B$ denotes
the value represented in the body frame.

Additionally, the relationship between the frames can be established as
follows:

$\left[\begin{array}[]{l}F_{x}^{B}\\\ F_{z}^{B}\\\
\textbf{M}^{B}\end{array}\right]=\mathbf{A}(\alpha)\mathbf{T}$ (2)

where $\textbf{A}(\alpha)$ is a $5\times 6$ allocation matrix which is a
function of $\alpha$ and
$\mathbf{T}=[T_{1}\;T_{2}\;T_{3}\;T_{4}\;T_{5}\;T_{6}]^{T}$ is the thrust
vector.

##  III Method

###  III-A Network Structure

Because the network uses the Proximal Policy Optimization (PPO) algorithm
based on the actor-critic method [18], our proposed neural networks consist of
two parts: a) value network and b) policy network, which is shown in Fig. 3.
The networks receive 19-dimensional state vector as input respectively whose
element consists of $\textbf{R}_{B}^{G}$, which is the relative rotation from
the goal frame to the drone body frame, $\mathbf{{p}}_{{B}}^{G}$,
$\mathbf{{v}}_{{B}}^{G}$, and $\boldsymbol{{\upomega}}_{{B}}^{G}$ the relative
position, velocity, angular velocity of the drone expressed in the goal frame,
and a current servo angle $\alpha_{\text{cur}}$. Each of the networks consists
of two fully connected layers whose size is 128 with leaky ReLU. Finally, the
value network outputs the value of the input state that is used to train the
policy network that outputs $\mathbf{T}$.

Even though the platform can follow the desired pitch $\theta_{\text{des}}$
while hovering, the reason for using the desired tilting angle
$\alpha_{\text{des}}$ instead of $\theta_{\text{des}}$ is as follows. As a
servo motor rotates along with $y_{A}$-axis, the corresponding unique $\theta$
value that makes the platform stay in the equilibrium point exists. If
$\theta_{\text{des}}$ is used as an input, the neural networks must control
the rotor and servomotor simultaneously. As a result, the real-to-sim gap
increases due to the different response times between the servomotor and
rotors. Besides, the dimension of the action space also increases, making it
difficult to learn the optimal policy. Nevertheless, if $\alpha_{\text{cur}}$
is used by considering the characteristics of the platform whose hovering
attitude is uniquely determined according to $\alpha_{\text{des}}$, the real-
to-sim problem caused by the difference in the response time between the servo
motor and rotors is eliminated, and the action space is reduced. We used an
appropriate range of scaling such that the state follows a roughly normal
distribution.

Figure 3: Overview of the proposed network that consists of value network and
policy network. They both take $1\times 19$ state as input and output value,
and action, i.e. rotor thrust, respectively

###  III-B Goal-centric Representation

Figure 4: $xy$-plane view of the inertial frame. Trajectories 1 and 2 are
starting from the equivalent state in goal-centric representation.

Note that our pose control is based on the goal frame, not the inertial frame.
Intuitively, there will be a way to use the error between the drone’s current
pose and the goal pose based on a fixed inertial frame to control. In the
conventional PID control, this method has no problem. However, when neural
networks are used as the reinforcement learning controller, even if two
initial poses follow the same goal-centric trajectory, the neural networks may
recognize them as different states. In this case, the neural networks need an
additional process to learn that the corresponding states make the same
trajectory, slowing down the learning speed. A detailed description of this is
as follows. The dynamic model of the drone’s linear acceleration can be
represented by the modeling above as follows:

$\mathbf{R}_{B}^{I}\left(\mathbf{F}^{B}-\boldsymbol{\upomega}^{B}\times\left(m\mathbf{v}^{B}\right)\right)=m\left(\ddot{\mathbf{p}}^{I}-\mathbf{g}^{I}\right)$
(3)

where $\mathbf{g}^{I}$ is the gravity vector. Let $\mathbf{R}_{z^{I}}(\psi)$
be a rotation matrix that rotates by $\psi$ with respect to the $z$-axis
$z^{I}$ of the inertial frame. Then, the gravity $\mathbf{g}^{I}$ has only z
component, satisfying the following condition:

$\mathbf{R}_{z^{I}}(\psi)\mathbf{g}^{I}=\mathbf{g}^{I}.$ (4)

Therefore, the following equation can be obtained using the above equations
as:

$\mathbf{R}_{z^{I}}(\psi)\mathbf{p}_{i}^{I}(t)=\mathbf{R}_{z^{I}}(\psi)\mathbf{p}_{i,0}^{I}+\mathbf{R}_{z^{I}}(\psi)\mathbf{v}_{i,0}^{I}t\
+\\\
\frac{1}{m}\left\\{\mathbf{R}_{z^{I}}(\psi)\mathbf{R}_{B}^{I}(t)\int_{t_{0}}^{t}\int_{t_{0}}^{\tau^{\prime}}\Big{(}\mathbf{F}(\tau)^{B}-\boldsymbol{\upomega}^{B}(\tau)\right.\\\
\left.\times\left(m\cdot\mathbf{v}^{B}(\tau)\right)+\mathbf{g}^{I}\Big{)}\right.{d}\tau{d}\tau^{\prime}\Bigg{\\}}$
(5)

where $\mathbf{p}^{I}_{i}(t)$, $\mathbf{p}^{I}_{i,0}$ and
$\mathbf{v}^{I}_{i,0}$ represent the position at time $t$, the initial
position, and velocity of the ${i}$-th trajectory, respectively. The system
dynamics is deterministic, and the policy network that outputs the system’s
only input $\mathbf{F}(\tau)^{B}$ is also deterministic when learning is
complete. Therefore, when
$\mathbf{p}_{1,0}^{I}=\mathbf{R}_{z^{I}}(\psi)\mathbf{p}_{2,0}^{I},\mathbf{v}_{1,0}^{I}=\mathbf{R}_{z^{I}}(\psi)\mathbf{v}_{2,0}^{I},\mathbf{R}_{B_{1}}^{I}(t)=\mathbf{R}_{z^{I}}(\psi)\mathbf{R}_{B_{2}}^{I}(t)$,
and $\boldsymbol{\upomega}_{1,0}^{B}=\boldsymbol{\upomega}_{2,0}^{B}$ are
satisfied, $\mathbf{p}_{1}^{I}(t)$ and $\mathbf{p}_{2}^{I}(t)$ must be equal.
An example of this is shown in Fig. 4. Trajectories 1 and 2 are starting from
different initial positions $\mathbf{p}^{I}_{1,0}$ and $\mathbf{p}^{I}_{2,0}$
with zero initial linear/angular velocity, and flying toward goal frames
$\left\\{G_{1}\right\\}$ and $\left\\{G_{2}\right\\}$. Because the condition
of (5) is satisfied, the two trajectories have the same path when rotated
about the $z^{I}$-axis. Therefore, the two initial states are essentially the
same. However, there is a problem that the neural networks recognize it as a
different state. This problem can be solved by expressing
$\mathbf{p}_{B}^{I},\mathbf{v}_{B}^{I},\mathbf{R}_{B}^{I}$ vectors based on
the goal frame reflecting $\mathbf{R}_{z^{I}}(\psi)$, thereby reducing the
required data during learning.

###  III-C Data Augmentation

Figure 5: $xy$-plane view of the inertial frame. Trajectories 1 and 3 are
starting from opposite states in goal-centric representation

In addition, data augmentation can be performed using the left-right symmetry
of the drone. $\mathbf{T}^{\prime}$ represents the thrust vector when the
platform’s output thrust is geometrically inverted with respect to the
$xz$-plane, as follows:
$\mathbf{T}^{\prime}=\left(T_{3},T_{4},T_{1},T_{2},T_{5},T_{6}\right)^{T}$.
Then, the following property is satisfied:

$\left[\begin{array}[]{l}F_{x}^{B}\\\ F_{Z}^{B}\\\
\overline{\mathbf{{M}}}^{B}\end{array}\right]=\mathbf{A}(\alpha)\mathbf{T}^{\prime}$
(6)

where $\overline{\mathbf{M}}=\left({M}_{1},-{M}_{2},{M}_{3}\right)$. Inertial
to body rotation $\mathbf{R}_{B}^{I}(t)$ over time can be expressed as follows
[19]:

${\boldsymbol{\mathrm{R}}}^{I}_{B}(t)=\mathrm{exp}\left[\frac{1}{2}\int^{t}_{0}{\
}\boldsymbol{\upomega}^{B}\left(t^{\mathrm{\prime}}\right){d}t^{\mathrm{\prime}}\right]{\boldsymbol{\mathrm{R}}}^{I}_{B}(0)$
(7)

where $\boldsymbol{\upomega}^{B}$ is defined as:

${\boldsymbol{\upomega}}^{B}(t)={\int^{t}_{t_{0}}{{\boldsymbol{\mathrm{J}}}^{{\mathrm{-1}}}\left(\alpha(\mathrm{\tau})\right)\boldsymbol{\mathrm{A}}{\left(\mathrm{\alpha}\mathrm{(}\mathrm{\tau}\mathrm{)}\right)}_{({3:5})}\mathbf{T}d\mathrm{\tau}}}.$
(8)

With these equations, the following equation holds:

$\mathbf{p}_{i}^{G}(t)=\mathbf{p}_{i,0}^{G}+\mathbf{v}_{i,0}^{G}t\\\
+\frac{1}{m}\Bigg{\\{}\exp\left[\frac{1}{2}\int_{t_{0}}^{t}\int_{t_{0}}^{\tau^{\prime}}\mathbf{J}^{-{1}}(\alpha(\tau))\mathbf{A}(\alpha(\tau))_{(3:5)}\mathbf{T}{d}\tau{d}\tau^{\prime}\right]\\\
\mathbf{R}_{B}^{G}(0)\int_{t_{0}}^{\tau^{\prime}}\int_{t_{0}}^{\tau}\left(\mathbf{A}(\alpha(\tau))_{(1:2)}\mathbf{T}(\tau)\right.\\\
\left.\left.-\boldsymbol{\upomega}^{B}(\tau)\times\left(m\cdot\mathbf{v}^{B}(\tau)\right.)+\mathbf{g}^{I}\right)\right.{d}\tau{d}\tau^{\prime}\Bigg{\\}}.$
(9)

Simultaneously, the system and the optimal learned policy are deterministic
with the same logic as before. Therefore ${\mathbf{{p}}}^{G_{1}}_{1,0}$ =
${\overline{\mathbf{p}}}^{G_{1}}_{2,0}$, $\mathbf{\
}{\mathbf{v}}^{G_{1}}_{1,0}$ =
${\overline{\mathbf{v}}}^{G_{1}}_{2,0},\mathbf{\
}{\boldsymbol{\mathrm{R}}}^{G_{1}}_{{B_{1}}}(t)$ =
${\boldsymbol{\mathrm{R}}}_{z^{G_{1}}}(2\psi){\boldsymbol{\mathrm{R}}}^{G_{1}}_{{B_{2}}}(t),\
{\mathbf{p}}^{G_{1}}_{1,0}$ = ${\overline{\mathbf{p}}}^{G_{1}}_{2,0}$, and
${\boldsymbol{\upomega}}^{B_{\ }}_{1,0}$ =
${\overline{\boldsymbol{\upomega}}}^{B}_{2,0}$ are satisfied. From the
relationship between $\textbf{{A}}(\alpha)\mathbf{T}$ and
$\textbf{A}(\alpha)\mathbf{T^{\prime}}$, the two trajectories are symmetric
with respect to the plane passing through the origin that is perpendicular to
${{y}}_{{{G}}_{{1}}}$.

An example of this is shown in trajectories 1 and 3 in Fig. 5. Trajectories 1
and 3 are starting from different initial positions $\mathbf{p}^{G_{1}}_{1,0}$
and $\mathbf{p}^{G_{1}}_{3,0}$ with zero initial linear/angular velocity, and
flying toward the same goal frame $\left\\{G_{1}\right\\}$.

###  III-D Value Network Training

This section presents the learning of the value network. A value function
$V_{\phi_{k}}$ that is parameterized with $\phi_{k}$ is updated using Monte-
Carlo samplings obtained from a trajectory. This can be expressed by the
following equation:

$\phi_{k+1}=\underset{\phi}{\operatorname{argmin}}\frac{1}{K}\sum_{0}^{K}\left(V_{\phi}\left(s_{t}\right)-\hat{R}_{t}\right)^{2}$
(10)

where $K$ is the number of trajectories, ${\hat{R}}_{t}\ =\
\sum^{T}_{t^{\mathrm{{}^{\prime}}}=t}{\ }R(s_{t^{\mathrm{{}^{\prime}}}},$
$a_{t^{\mathrm{{}^{\prime}}}},s_{t^{\mathrm{{}^{\prime}}}+1})$ reward to go,
i.e., sum of rewards after the current position in a trajectory. Loss is
obtained using least squares error. Through this predicted current value
function $V_{\phi_{k}}$, the advantage estimate ${\hat{\mathcal{L}}}_{t}$ used
in the actual policy optimization can be obtained. If an advantage estimate is
made using well-tuned parameters, variance reduction is possible [20] as
follows:

$\begin{split}\hat{\mathcal{L}}_{t}&=\delta_{t}+(\gamma\lambda)\delta_{t+1}+\cdots+\cdots+(\gamma\lambda)^{K-t+1}\delta_{T-1}\\\
\delta_{t}&=r_{t}+\gamma V\left(s_{t+1}\right)-V\left(s_{t}\right)\end{split}$
(11)

where $r_{t}$ is the reward at step $t$ and $\lambda\ \mathrm{\in}\
\mathrm{[0,1]}$ a hyper parameter.

###  III-E Policy Network Training

TABLE I

Parameters Used For Training In The Simulation

$\small{}\begin{array}[]{lc}\\\\[-1.93748pt]
\hline\cr\hline\cr\\\\[-3.87498pt]
\lx<EMAIL_ADDRESS>\hline\cr\\\\[-3.87498pt] \text{ Number of steps per environment }&1,200\\\
\text{ Epoch size }&10\\\ \text{ Batch size }&10\\\ \text{ Value function
coefficient }\left(\mathrm{c}_{1}\right)&0.5\\\ \text{ Learning rate
}&0.00005\\\ \text{ Discount factor }(\gamma)&0.998\\\ \text{ GAE factor
}(\lambda)&0.95\\\ \text{ Clipping parameter }(\epsilon)&0.2\\\ \text{
Optimizer }&\text{ Adam }\\\ \\\\[-3.87498pt] \hline\cr\hline\cr\end{array}$

The policy optimization process is calculated using ${\mathcal{L}}_{t}$
obtained in equation (11). The loss function used at this time is PPO-clip
presented in [18]. A parameter $\theta_{k}$ for policy function
$\pi_{\theta_{k}}$ is updated as follows:

$\begin{array}[]{l}\theta_{k+1}=\underset{\theta}{\operatorname{argmax}}\frac{1}{K}\sum_{t=0}^{K}\bigg{\\{}\min\Big{(}\frac{\pi_{\theta}\left(a_{t}\mid
s_{t}\right)}{\pi_{\theta_{k}}\left(a_{t}\mid
s_{t}\right)}\mathcal{L}_{t}^{\pi_{\theta_{k}}},\\\ \quad\quad\quad\quad\quad
g\left(\epsilon,\mathcal{L}_{t}^{\pi_{\theta_{k}}}\right)\Big{)}-c_{1}\left(V_{\phi}\left(s_{t}\right)-\widehat{R}_{t}\right)^{2}\bigg{\\}}\end{array}$
(12)

where
$g(\epsilon,\mathcal{L})=\left\\{\begin{array}[]{ll}(1+\epsilon)\mathcal{L},&\mathcal{L}\geq
0\\\ (1-\epsilon)\mathcal{L},&\mathcal{L}<0\end{array}\right.$
and $\mathcal{L}_{t}^{\pi_{\theta_{k}}}$ is $\hat{\mathcal{L}_{t}}$ under
policy $\pi_{\theta_{k}}$; ${\mathrm{c}}_{\mathrm{1}}$ and $\epsilon$ are
hyper parameters that satisfy ${\mathrm{c}}_{\mathrm{1}},\epsilon\
\mathrm{\in}\ \mathrm{[0,1]}$.

##  IV Simulation

This section presents the learning process through simulations, including the
simulator used, simulation parameters, reward function, and the simulation
results.

###  IV-A Simulation Environment

For the simulator, we used Raisim [21], which guarantees faster speed and
accuracy than other simulators, and its performance was verified in various
previous studies [14, 17]. Parameters used in the simulation are listed in
Table I. To learn various samples, values within the ranges of $\mathrm{\pm}$1
m, $\mathrm{\pm}$1 m/s, and $\mathrm{\pm}$1 rad/s are randomly assigned to the
position, linear velocity, and angular velocity, respectively. The initial
orientation is also given randomly within the range where the body $z$-axis
has a positive value. The training was performed on a Linux machine with an
Intel Core i7-6700K CPU @ 4.00GHz, and GPU GTX 1660.

###  IV-B Reward Function

Figure 6:  Power consumption at each timestep while hovering with arm tilting
angle from 0° to 110°.

To control the system to achieve the desired performance through reinforcement
learning, an appropriate cost function must be set. The cost function used is
as follows:

$r_{t}=c_{p}\left\|\mathbf{p}_{t}\right\|+c_{\psi}\left\|{\psi}_{t}\right\|+c_{\boldsymbol{\upomega}}\left\|\boldsymbol{\upomega}_{t}\right\|+c_{E}\left\|{E}_{t}\right\|$
(13)

where ${\mathbf{p}}_{t}$, ${\psi}_{t},\ {\boldsymbol{\upomega}}_{t}$, and
${E}_{t}$ are the position, angle with respect to $z^{G}$-axis, angular
velocity, and power consumption at time t, respectively. $c_{p}$, $c_{\psi}$,
$c_{\boldsymbol{\upomega}}$, and $c_{E}$ are the weighting factors for
${\mathbf{p}}_{t}$, ${\psi}_{t},\ {\boldsymbol{\upomega}}_{t}$, and ${E}_{t}$,
respectively. In the case of attitude reward, our platform does not use
$\theta_{des}$, but uses $\alpha_{des}$, and learns the optimal attitude for
the current tilting angle $\alpha_{cur}$ in the learning process. Therefore,
the angle difference between the desired and the current $\psi$ was used as an
error. The quadrotor, which was mainly used for low-level multirotor control
through reinforcement learning, has a system whose four actuators output
$F_{z}^{B},M_{x}^{B},M_{y}^{B},$ and $M_{z}^{B}$. However, because our
platform is based on a coaxial hexacopter, seven actuators are redundant,
outputting only $F_{x}^{B},F_{z}^{B},M_{x}^{B},M_{y}^{B},$ and $M_{z}^{B}$.
Therefore, there are various solutions that make the actuator generate the
equivalent outputs. Because the policy network needs to converge to an optimal
policy, such a situation is undesirable. Thus, power consumption was
considered as a reward function, which was not considered in the previous
reinforcement learning studies using quadrotors. The relationship between
thrust and power consumption in the idle rotor system can be expressed as
follows [25]:

$P=T\cdot\sqrt{\frac{T}{2A\rho}}$

where $A$ is the rotor disk area, $\rho$ is the density of the air, $P$ the
required power for the thrust $T$. The comparison result between the proposed
and conventional methods is shown in Fig. 6. Because the reward function used
in the previous studies was focused on a quadrotor, it was not necessary to
consider the power consumption from thrust. However, in our platform, the
power consumption itself is more significant than a quadrotor, and undesirable
oscillation occurs in the thrust. Because the rotor output is also nonlinear,
such a thrust output should be avoided to prevent a more significant sim-to-
real gap. On the other hand, when the proposed method is used, the results are
much more stable than those with the conventional method. For efficient
learning, the platform converges to the origin of the inertial frame at the
time of learning. In the actual situation, rewards are expressed in the goal
frame, which is given by the manual input. Because the position and
orientation are the parts we care about most, it has the highest coefficient.

###  IV-C Curriculum Learning

Unlike the conventional quadrotor, the tilting multirotor has more complex
dynamics and systems. Therefore, it takes a long time to learn the optimal
policy, or it can converge to the local optima. Complex problems can be more
effectively solved using curriculum learning [22, 23]. These studies show that
learning through curriculum learning using a more accessible example promotes
the neural networks to converge faster. The curriculum was conducted by
learning to hover while reducing the randomness of the initial condition.
Then, the randomness is gradually increased, after which the tilting and
perching are learned while increasing the tilting angle. Thus, the agent can
converge faster and overcome the problem of falling into a local optimum
during learning.

Also, domain randomization has been used with curriculum learning. Domain
randomization is a concept suggested in [24] to reduce the real-to-sim gap in
reinforcement learning. It creates a simulation environment with random
characteristics such as wind, and random noise is applied to sensors and
hardware while learning. Wind disturbances, sensor noises, and hardware
parameters are randomized so that the initial optimal policy can run in
reality. However, it acts as a factor that makes learning to be complicated.
So curriculum learning was performed by applying 5% noise to sensor data and
hardware parameters.

###  IV-D Simulation Result

Figure 7: Learning curves when hovering is trained using the conventional and
proposed method. The number of data is equal to the total number of steps.
Figure 8: Simulation results using learned optimal policy while hovering. The
pitch angle $\theta$ changes according to the given tiling angle $\alpha$.
Figure 9: Position step responses of the learned optimal policy in the
simulation at various tilting angles.

The convergence speed when learning hovering in the simulation is checked to
determine the extent to which the contribution affects the result. As shown in
Fig. 7, the network was thoroughly trained with 3 million data using the
proposed method, while the conventional method did not converge. Consequently,
it can be confirmed that the proposed method reduces the data required for
learning, resulting in faster convergence. Two tests were conducted to confirm
the performance of the policy learned in the simulation. It is necessary to
decouple the $x$-position and the angle $\theta$ to perch on the wall stably.
For the first test, we checked if the learned optimal policy could maintain
the desired position with an adequate pitch angle $\theta$ in mid-air while
the tilting angle $\alpha$ changed from 0°to 110°. The results are shown in
Fig. 8. Even if $\alpha$ changes, the platform maintains its position with the
appropriate $\theta$. However, it is noteworthy that the $z$-position
gradually decreases as $\alpha$ increases. It is because the efficiency of the
platform decreases as the arm is tilted, and the power consumption by thrust
is considered in the reward function. Additionally, to check the control
performance according to $\alpha$, the test using a step position input was
carried out. The results are shown in Fig. 9. $\alpha$ of 0°, 60°, 110° are
the tilting angles that make the platform hover at 0°, 45°, 90°, respectively.
The behavior of the platform differs depending on ${\alpha}_{cur}$; however,
it was clear that it converged to the setpoint. For the $z$-position, it can
be seen that the steady-state error increases as $\alpha$ increases, similar
to the result in Fig. 8. From these results, we can conclude that the policy
was sufficiently learned to perform the actual flight.

##  V Experiments

This section describes the hardware parameters, overall operation diagram of
the platform used in the experiment, and experimental results. For the
experiment, the flight performance of the pose control between the cases with
and without learning the actual experience was compared.

###  V-A Hardware

Figure 10: Platform diagram for experimentation. The 1Gbit Ethernet uses
wireless communication, and the Mavlink and ROS use wired communication.

The main components of the system consist of 5-inch propellers, Xnova RM2207
2000 KV motors [26], and Robotis Dynamixel XM540-W270-R [27]. Pixhawk4 mini
[28] was used as a flight controller, and Jetson Nano with Quad-core ARM
Cortex-A57 MPCore processor is used for the onboard controller. The main
parameters are listed in Table II.

TABLE II

Hardware Parameters

$\small{}\begin{array}[]{lc}\\\\[-3.87498pt]
\hline\cr\hline\cr\\\\[-3.87498pt]
\lx<EMAIL_ADDRESS>\hline\cr\\\\[-3.87498pt] \text{ Total weight }&1.9\mathrm{~{}kg}\\\ \text{
Max. thrust of each BLDC motor \cite[cite]{[\@@bibref{}{tmot}{}{}]}
}&14.2\mathrm{~{}N}\\\ \text{ Stall torque of XM540-W270-R
\cite[cite]{[\@@bibref{}{rob}{}{}]} }&10.60\mathrm{Nm}\\\ \text{ Distance from
tilting axle to tilting rotor}&75\mathrm{~{}mm}\\\ \text{ Half of the distance
between tilting rotors}&130\mathrm{~{}mm}\\\ \text{ Distance from tilting axle
to fixed rotor }&200\mathrm{~{}mm}\\\ \\\\[-3.87498pt]
\hline\cr\hline\cr\end{array}$

A diagram of the entire system is detailed in Fig. 10, where
$\hat{\mathbf{x}}$ represents the estimation of the vector $\mathbf{x}$. After
${\mathbf{p}}^{{I}}_{B}$, ${\mathbf{q}}^{{I}}_{B}$,
${\mathbf{v}}^{{I}}_{{B}}$, and ${\boldsymbol{\upomega}}^{{I}}_{{B}}$ are
measured by the motion capture, they are sent to the VRPN node of the on-board
computer running the ROS (Robot Operating System). This process was performed
through wireless communication. The VRPN node sends the data to the flight
controller using a protocol referred to as Mavlink. Here, the user inputs
${\mathbf{p}}^{{I}}_{G}$, ${\alpha}_{des}$, and ${\psi}_{des}$ to the flight
controller through the radio controller. Then, estimated states are
transmitted to the policy network node through Mavlink. In the policy network
node, state vectors are inserted into the learned policy network to inference
T. After that, T and ${{\alpha}}_{{des}}$ are inputted to the flight
controller and servo motor through Mavlink and ROS protocols, respectively. In
the flight controller, the input T is converted into PWM and transmitted to
each rotor. In the servo motor, the PID control is performed through the input
${{\alpha}}_{{des}}$. Subsequently, the tasks described above are repeated as
the policy network node gets state feedback.

###  V-B Without Real-world Data

Figure 11: Actual flight results of hovering without learning real-world data.
The pitch angle $\theta$ according to the given tiling angle $\alpha$ and
corresponding position at that time.

To check the degree of sim-to-real gap, the same task as in Fig. 8 has been
tested. The results are shown in Fig. 11. The overall trend of the results is
similar to that of the simulation in Fig. 8. However, there is a significant
difference between the simulation and the actual flight owing to the sim-to-
real gap caused by nonlinear effects that have not been modeled in the
simulation. These nonlinearities have occurred from the interference between
propellers by the tilting rotor, the aerodynamics of coaxial propeller, and
the difference between modeled center of mass and the actual center of mass.

###  V-C With Real-world Data

Figure 12: Actual flight results of hovering after learning real-world data.
The pitch angle $\theta$ according to the given tiling angle $\alpha$ and
corresponding position at that time.

Figure 13: Perching process of the platform from hovering state. (a)
Beginning, (b) After 1.5 s, (c) After 3.5 s, (d) After perching.

The policy network was additionally trained by the actual flight data. There
is a difficulty in obtaining actual flight data for a multirotor sufficiently
due to flight time limitations. We checked whether we could learn enough to
achieve acceptable performance for perching by learning with limited real-
world data. To acquire the data for the training, flights with the platform
were repeated. Each flight was about 3 minutes long, and 30 times of flights
have been conducted. Because the state vector is updated at a 200Hz rate, a
total of about 1 million actual flight data has been obtained. Afterward, 2
million data were achieved with data augmentation using symmetry. The final
experimental results after learning these data are shown in Fig. 12. The
platform hovered and maintained its position more stably and accurately up to
90° compared to the one without learning real-world data. The result was
sufficient to tilt in the air and perch to the wall, as shown in Fig. 13. With
these results, we could conclude that the nonlinear effects that were not
modeled in the simulation were eventually learned through the real-world data.
In this research, we focused on demonstrating that the tilting multirotor can
be controlled through reinforcement learning.

##  VI Conclusion

This study proposed a novel control strategy for controlling a tilting
multirotor with reinforcement learning. Controlling an actual system with
reinforcement learning has the advantage of not needing to know the actual
model accurately; however, it may not be appropriately controlled due to a
sim-to-real gap. In this paper, the gap was overcome by learning real
experiences from the actual flight. Additionally, it is challenging and
requires more data to learn the tilting multirotor dynamics because it is more
complicated than the existing quadrotor. As described in Section III.B. and
III.C., novel methods to learn faster and augment the data have been proposed.
The results of the control using these methods are presented in Section V. In
this study, only the task involving perching on the wall by tilting in the air
was demonstrated; however, an additional controller suitable for the wall is
required for applications on an actual wall. Future work will enable perching,
detaching, and even wall interaction with a single controller without an
additional one.

## References

  * [1] J. Choi and H. Myung, “BRM Localization: UAV Localization in GNSS-Denied EnvironmentsBased on Matching of Numerical Map and UAV Images,” in Proc. IEEE/RSJ Int’l Conf. on Intelligent Robots and Systems (IROS), 2020, pp.1440-1443.
  * [2] S. Jung, J. Kim, J. Choi, D, Choi, and H. Myung, “GPS-aided Autonomous Aerial Vehicle for Safety Inspection of Industry Environment,” in Proc. Int’l Conf. on Ubiquitous Robots (UR), 2020, pp. 549-550.
  * [3] W. Myeong, S. Jung, B. Yu, C. Tirtawardhana, S. Song, J. Kim, J. Choi, and H. Myung, “Development of wall-climbing unmanned aerial vehicle system for micro-inspection of bridges,” Workshop on Aerial Robotics, Int’l Conf. on Robotics and Automation (ICRA), Montreal, Canada, May 2019.
  * [4] W. Myeong and H. Myung, “Development of a wall-climbing drone capable of vertical soft landing using a tilt-rotor mechanism,” IEEE Access, vol. 7, pp. 4868-4879, 2018.
  * [5] S. Rajappa, M. Ryll, H. H. Bülthoff, and A. Franchi, “Modeling, control and design optimization for a fully-actuated hexarotor aerial vehicle with tilted propellers,” in Proc. IEEE Int’l Conf. on Robotics and Automation (ICRA), 2015, pp. 4006–4013.
  * [6] D. Brescianini and R. D’Andea, “Design, modeling and control of an omni-directional aerial vehicle,” in Proc. IEEE Int’l Conf. on Robotics and Automation (ICRA), 2015, pp. 3261-3266.
  * [7] A. Oosedo, S. Abiko, S. Narasaki, A. Kuno, A. Konno, and M. Uchiyama, “Flight control systems of a quad tilt rotor unmanned aerial vehicle for a large attitude change,” in Proc. IEEE Int’l Conf. on Robotics and Automation (ICRA), 2015, pp. 2326-2331.
  * [8] M. Ryll, D. Bicego, and A. Franchi, “Modeling and control of FAST-Hex: a fully-actuated by synchronized-tilting hexarotor,” in Proc. IEEE/RSJ Int’l Conf. on Intelligent Robots and Systems (IROS), 2016, pp. 1689-1694.
  * [9] M. Tognon and A. Franchi, “Omnidirectional aerial vehicles with unidirectional thrusters: Theory, optimal design, and control,” IEEE Robotics and Automation Letters, vol. 3, no. 3, pp. 2277-2282, 2018.
  * [10] M. Kamel, S. Verling, O. Elkhatib, C. Sprecher, P. Wulkop, Z. Taylor, R. Siegwart, and I. Gilitschenski, “The voliro omniorientational hexacopter: An agile and maneuverable tiltable-rotor aerial vehicle,” IEEE Robotics $\&$ Automation Magazine, vol. 25, no. 4, pp. 34-44, 2018.
  * [11] R. Voyles and G. Jiang, “A nonparallel hexrotor UAV with faster response to disturbances for precision position keeping,” in Proc. IEEE Int’l Symp. on Safety, Security, and Rescue Robotics, 2014, pp. 1–5.
  * [12] P. Segui-Gasco, Y. Al-Rihani, H. S. Shin, and A. Savvaris, “A novel actuation concept for a multi rotor UAV,” in Proc. Int’l Conf. on Unmanned Aircraft Systems, 2013, pp. 373–382.
  * [13] M. Tognon, H. A. T. Chávez, E. Gasparin, Q. Sablé, D. Bicego, A. Mallet, M. Lany, G. Santi, B. Revaz, J. Cortés, and A. Franchi, “A truly-redundant aerial manipulator system with application to push-and-slide inspection in industrial plants,” IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1846-1851, 2019.
  * [14] J. Hwangbo, I. Sa, R. Siegwart, and M. Hutter, “Control of a quadrotor with reinforcement learning,” IEEE Robotics and Automation Letters, vol. 2, no. 4, pp. 2096-2103, 2017.
  * [15] Y. Wang, J. Sun, H. He, and C. Sun, “Deterministic policy gradient with integral compensator for robust quadrotor control,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 50, no. 10, pp. 3713-3725, 2019.
  * [16] N. O. Lambert, D. S. Drew, J. Yaconelli, S. Levine, R. Calandra, and K. S. Pister, “Low-level control of a quadrotor with deep model-based reinforcement learning,” IEEE Robotics and Automation Letters, vol. 4, no. 4, pp. 4224-4230, 2019.
  * [17] J. Hwangbo, J. Lee, A. Dosovitskiy, D. Bellicoso, V. Tsounis, V. Koltun, and M. Hutter, “Learning agile and dynamic motor skills for legged robots,” Science Robotics, vol. 4, no. 26, 2019.
  * [18] J. Schulman, F. Wolski, P.Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” arXiv:1707.06347, 2017.
  * [19] M. Boyle, “The integration of angular velocity,” Advances in Applied Clifford Algebras, vol. 27, no. 3, pp. 2345-2374, 2017.
  * [20] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, and K. Kavukcuoglu “Asynchronous methods for deep reinforcement learning.” in Proc. International Conference on Machine Learning (ICML), 2016, pp. 1928-1937.
  * [21] J. Hwangbo, J. Lee, and M. Hutter, “Per-contact iteration method for solving contact dynamics,” IEEE Robotics and Automation Letters, vol. 3, no. 2, pp. 895-902, 2018.
  * [22] Y. Bengio, J. Louradour, R. Collobert, and J. Weston, “Asynchronous methods for deep reinforcement learning,” in Proc. International Conference on Machine Learning (ICML), 2009, pp. 41-48.
  * [23] D. Weinshall, G. Cohen, and D. Amir, “Curriculum learning by transfer learning: Theory and experiments with deep networks,” in Proc. International Conference on Machine Learning (ICML), 2018, pp. 5238-5246.
  * [24] J. Tobin, R, Fong, A. Ray, J. Schneider, W. Zaremba, and P. Abbeel, ”Domain randomization for transferring deep neural networks from simulation to the real world,” in Proc. IEEE/RSJ Int’l Conf. on Intelligent Robots and Systems (IROS), 2018, pp. 23-30.
  * [25] G. J. Leishman, Principles of helicopter aerodynamics with CD extra, Cambridge University Press, 2006.
  * [26] “MN4010 KV475.” T-MOTOR Store. http://store-en.tmotor.com/goods.php?id=342 (accessed Feb. 26, 2020).
  * [27] “XM540-W270-T/R specifications.” ROBOTIS e- Manual, Korea. http://emanual.robotis.com/docs/en/dxl/x/xm540-w270/ (accessed Oct. 12, 2020).
  * [28] “Pixhawk4 mini.” Holybro Store. https://shop.holybro.com/pixhawk4-mini_p1120.html (accessed Oct. 11, 2020).


4.3 allows us to combine two dynamic coarsening algorithms, as in the
following dynamic composition lemma:

######  Lemma 6.10.

(Composing dynamic coarsenings). Let $\varepsilon_{1},\varepsilon_{2}\in[0,1]$
and $\delta_{1}\leq\delta_{2}$. For $i=1,2$, let $\mathcal{C}_{i}$ be a
dynamic $(\varepsilon_{i},\delta_{i})$-coarsening algorithms with
$\mathtt{update}$ times
$t^{\mathcal{C}_{i}}_{U}:=t^{\mathcal{C}_{i}}_{U}(\varepsilon_{i},\delta_{i},n)$
and $\mathtt{init}$ times $O(|\mathrm{supp}({\mathbf{x}})|\cdot
t^{\mathcal{C}_{i}}_{I})$, for
$t^{\mathcal{C}_{i}}_{I}:=t^{\mathcal{C}_{i}}_{I}(\varepsilon_{i},\delta_{i},n)$.
Then, there exists a dynamic
$(O(\varepsilon_{1}+\varepsilon_{2}),\delta_{2})$-coarsening algorithm with
$\mathtt{update}$ time
$O(t_{U}^{\mathcal{C}_{1}}+t^{\mathcal{C}_{2}}_{U}+\varepsilon^{-1}\cdot
t^{\mathcal{C}_{2}}_{I})$ and $\mathtt{init}$ time
$O(|\mathrm{supp}({\mathbf{x}})|\cdot(t^{\mathcal{C}_{1}}_{I}+t^{\mathcal{C}_{2}}_{I}))$,
which is deterministic/adaptive/output-adaptive if both $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ are. Moreover, it suffices for $\mathcal{C}_{2}$ to be a
coarsening algorithm only for inputs that are a subset of the support of an
output of $\mathcal{C}_{1}$.

As the proof is near identical to that of Lemma 4.3, we only outine one
salient difference.

###### Proof (Sketch).

The algorithm broadly follows the logic of Lemma 4.3, with
$\mathcal{C}_{1},\mathcal{C}_{2},\varepsilon_{1}$ and $\delta_{1}$ playing the
roles of $\mathcal{C}$,$\mathcal{R},\varepsilon$ and $\delta$ in that lemma.
The outline of the algorithm and the resulting running time and
determinism/adaptivity are as in Lemma 4.3. The only difference in correctness
analysis is that by Lemma 4.14, taking the non-deleted edges in
$\mathrm{supp}(x^{(1)})\cap\\{e\mid x_{e}<\delta_{1}\\}$ periodically (i.e.,
after every $\varepsilon_{1}\cdot\lVert{\mathbf{x}}\rVert/\delta_{1}$ updates
and using them as input to $\mathrm{supp}(x^{(1)})\cap\\{e\mid
x_{e}<\delta_{1}\\}$) allows us to maintain an
$(O(\varepsilon_{1}),\delta_{1})$-coarsening of ${\mathbf{x}}$ as the
(dynamic) input for $\mathcal{C}_{2}$ throughout. (Note that $\mathcal{C}_{2}$
is a dynamic coarsening algorithm for the resultant vector dominated by
${\mathbf{x}}^{(1)}$, by the lemma’s hypothesis.) That the dynamic output of
$\mathcal{C}_{2}$ is an
$(O(\varepsilon_{1}+\varepsilon_{2}),\delta_{2})$-coarsening of ${\mathbf{x}}$
then follows Lemma 6.9. ∎

Lemma 6.7 then follows from Lemma 6.10 in much the same way that Theorem 1.2
follows from Lemma 4.3 in Section 4.1, by taking the coarsening algorithms of
Section 4 as $\mathcal{C}_{1}$ and Algorithm 2 as the second coarsening
algorithm $\mathcal{C}_{2}$ (here, relying on Lemma 6.8). We omit the details
to avoid repetition.

###  6.3 Proof of Theorem 6.6: Maintaining AMMs

In this section we show how to maintain $O(\epsilon)$-AMMs, by dynamically
coarsening AMFMs (motivated by Lemma 6.5), and periodically using these
coarsened AMFMs to compute such AMMs.

Our first lemma provides a static algorithm substantiating the intuition that
a coarsening of an AMFM allows to efficiently compute an AMM (under mild
conditions, which we address below).

######  Lemma 6.11.

Let $0\leq\delta\leq\epsilon\leq 1$. If $\mu(G)\geq
2\delta^{-1}\epsilon^{-1}$, then there exists a deterministic algorithm that,
given an $(\varepsilon,\delta)$-AMFM ${\mathbf{x}}$ of $G$ and an
$(\epsilon,\delta)$-coarsening ${\mathbf{x}}^{\prime}$ of ${\mathbf{x}}$
satisfying $x^{\prime}_{e}\in\\{0,\delta\\}$ if $x_{e}<\delta$, outputs an
$O(\varepsilon+\delta)$-AMM of $G$ in time
$O(\mu(G)\cdot\epsilon^{-1}\cdot\delta^{-1}\cdot\log(\varepsilon^{-1}))$.

###### Proof.

We modify ${\mathbf{x}}^{\prime}$ within the desired time bounds to obtain an
$(\epsilon^{\prime\prime},\delta^{\prime\prime})$-AMFM
${\mathbf{x}}^{\prime\prime}$ with
${\mathbf{x}}^{\prime\prime}_{\min}\geq\delta^{\prime\prime}$ (for
$\varepsilon^{\prime\prime}=\Theta(\epsilon+\delta)$ and
$\delta^{\prime\prime}=\Theta(\delta)$ to be determined) in a graph
$G^{\prime\prime}=(V\cup V^{\prime\prime},E\cup E^{\prime\prime})$ obtained
from $G$ by adding some
$|V^{\prime\prime}|=O(\epsilon^{\prime\prime})\cdot\mu(G)$ many dummy vertices
$V^{\prime\prime}$ as well as some dummy edges $E^{\prime\prime}$ to $G$.
Therefore, by Lemma 6.5, the support of ${\mathbf{x}}^{\prime\prime}$ is an
$(\epsilon^{\prime\prime},(\delta^{\prime\prime})^{-1})$-kernel of
$G^{\prime\prime}$. Hence, by 6.3 we can compute deterministically an
$\varepsilon^{\prime\prime}$-AMM $M^{\prime\prime}$ of $G^{\prime\prime}$ in
the claimed running time. Now, by definition of an
$\epsilon^{\prime\prime}$-AMM, $M^{\prime\prime}$ is maximal in a subgraph
obtained from $G^{\prime\prime}$ after removing a set of vertices $U\subseteq
V\cup V^{\prime\prime}$ of cardinality at most
$|U|\leq\epsilon^{\prime\prime}\cdot\mu(G^{\prime\prime})\leq\epsilon^{\prime\prime}\cdot(1+O(\varepsilon^{\prime\prime}))\cdot\mu(G)\leq
O(\epsilon^{\prime\prime})\cdot\mu(G)$. Consequently, $M:=M^{\prime\prime}\cap
E$ is maximal in a subgraph obtained from $G$ after removing at most
$|U|+|V^{\prime\prime}|\leq
O(\epsilon^{\prime\prime})\cdot\mu(G)=O(\epsilon+\delta)\cdot\mu(G)$ many
vertices, including the at most $O(\varepsilon^{\prime\prime})\cdot\mu(G)$
many vertices of $V$ matched by $M^{\prime\prime}$ to dummy vertices in
$V^{\prime\prime}$. It remains to construct $G^{\prime\prime}$ and
${\mathbf{x}}^{\prime\prime}$.

First, invoking Lemma 4.12, we deterministically compute a bounded
$(\epsilon^{\prime},\delta)$-coarsening ${\mathbf{y}}$ of ${\mathbf{x}}$, for
$\epsilon^{\prime}:=3(\epsilon+\delta)$, in time
$O(|\mathrm{supp}({\mathbf{x}}^{\prime})|)\leq
O(\delta^{-1}\cdot\lVert{\mathbf{x}}\rVert)\leq O(\delta^{-1}\cdot\mu(G))$.
Here, the first inequality follows from
${\mathbf{x}}^{\prime}_{\min}\geq\delta$, while the second follows from the
integrality gap of the degree-bounded fractional matching polytope in general
graphs implying that $\lVert{\mathbf{x}}\rVert\leq\frac{3}{2}\cdot\mu(G)$. By
Property (C4) of bounded coarsenings, $y(v)\leq x(v)+\epsilon^{\prime}\leq
1+\epsilon^{\prime}$. We therefore consider
${\mathbf{z}}:={\mathbf{y}}/(1+\epsilon^{\prime})$, which by the above is a
fractional matching with
${\mathbf{z}}_{\min}\geq\delta^{\prime}:=\delta/(1+\epsilon^{\prime})$.
Moreover, since
$\lVert{\mathbf{z}}\rVert=\lVert{\mathbf{y}}\rVert/(1+\varepsilon^{\prime})\geq\lVert{\mathbf{y}}\rVert\cdot(1-\epsilon^{\prime})$
and hence $\sum_{v}|y(v)-z(v)|\leq
2\epsilon^{\prime}\lVert{\mathbf{y}}\rVert$, we have that

$\displaystyle d^{15\varepsilon^{\prime}}_{V}({\mathbf{x}},{\mathbf{z}})$
$\displaystyle\leq
d^{\varepsilon^{\prime}}_{V}({\mathbf{x}},{\mathbf{y}})+d^{14\varepsilon^{\prime}}_{V}({\mathbf{y}},{\mathbf{z}})$
$\displaystyle\leq
d^{\varepsilon^{\prime}}_{V}({\mathbf{x}},{\mathbf{y}})+d^{0}_{V}({\mathbf{y}},{\mathbf{z}})$
$\displaystyle\leq
d^{\varepsilon^{\prime}}_{V}({\mathbf{x}},{\mathbf{y}})+2\epsilon^{\prime}\lVert{\mathbf{y}}\rVert$
$\displaystyle\leq\varepsilon^{\prime}\cdot\lVert{\mathbf{{\mathbf{x}}}}\rVert+\epsilon^{\prime}+2\epsilon^{\prime}\cdot((1+\epsilon^{\prime})\cdot\lVert{\mathbf{x}}\rVert+\epsilon^{\prime})+2\epsilon^{\prime}$
Properties (C1) and (C2) $\displaystyle\leq
15\epsilon^{\prime}\cdot\lVert{\mathbf{x}}\rVert+15\epsilon^{\prime}.$
$\displaystyle\epsilon^{\prime}=3(\epsilon+\delta)\leq 6.$

That is, ${\mathbf{z}}$ is a fractional matching that satisfies Property (C2)
of a $(15\epsilon^{\prime},\delta^{\prime})$-coarsening of ${\mathbf{x}}$.

Now, we say a node $v$ is _useful_ if $x(v)\geq 1-\epsilon$ and $\max_{f\ni
v}x_{f}\leq\delta$ (noting their relevance in 6.1). By Property (C2), and
again using the integrality gap, we have that

$\displaystyle\sum_{v\textrm{
useful}}(|x(v)-z(v)|-15\epsilon^{\prime})^{+}\leq
d^{15\epsilon^{\prime}}_{V}(x,z)\leq(15\epsilon^{\prime}\cdot\lVert{\mathbf{x}}\rVert+15\epsilon^{\prime})\leq
30\epsilon^{\prime}\cdot\lVert{\mathbf{x}}\rVert\leq
45\epsilon^{\prime}\cdot\mu(G).$ (6)

We now create a set $V^{\prime\prime}$ of
$90\cdot\epsilon^{\prime}\cdot\mu(G)$ many dummy vertices, and create a
fractional matching ${\mathbf{x}}^{\prime\prime}$ from ${\mathbf{z}}$, letting
$x^{\prime\prime}_{e}=z_{e}$ for each edge $e\in E$ and adding dummy edges
$e\in E^{\prime\prime}$ with
${\mathbf{x}}^{\prime\prime}_{e}=\delta^{\prime\prime}:=\delta^{\prime}=\delta/(1+\varepsilon)\geq\delta/2$.
Specifically, for each useful vertex $v$, we add some
$\lceil(x(v)-z(v)-15\varepsilon^{\prime})^{+}\cdot(\delta^{\prime\prime})^{-1}\rceil\leq
2x(v)\cdot(\delta^{\prime\prime})^{-1}\leq 4\delta^{-1}$ dummy edges to
distinct dummy vertices (this is where we use that
$\varepsilon\cdot\mu(G^{\prime})\geq\delta^{-1}$), chosen in round-robin
fashion. This guarantees that each useful vertex $v$ has
$x^{\prime\prime}(v)\geq x(v)-15\varepsilon^{\prime}$. That
${\mathbf{x}}^{\prime\prime}$ is a fractional matching, and in particular
dummy nodes $u$ have $x(u)\leq 1$, follows from Equation 6, as the amount of
total ${\mathbf{x}}^{\prime\prime}$-value on dummy edges is at most
$90\varepsilon^{\prime}\cdot\mu(G)\leq|V^{\prime\prime}|$, distributed in
round-robin fashion.

Finally, we note that any edge $e$ with $x^{\prime\prime}_{e}<\delta^{\prime}$
has $z_{e}<\delta^{\prime}$ and so $z_{e}=0$, by Property (C3), and so
$y_{e}=0$, implying in turn that $x_{e}<\delta$, again by Property (C3), and
so there exists a useful $v\in e$, by 6.1. Therefore, $x(v)\geq 1-\epsilon$,
and so $x^{\prime\prime}(v)\geq x(v)-15\epsilon^{\prime}\geq
1-\epsilon-15\epsilon^{\prime}$. Moreover, all edges $f\ni v$ have
$x_{f}\leq\delta$, and so $x^{\prime}_{f}\in\\{0,\delta\\}$ by Property (C3)
and the lemma’s hypothesis. Consequently, $y_{f}\in\\{0,\delta\\}$, and so
$x^{\prime\prime}_{f}\in\\{0,\delta^{\prime}\\}$. That is, letting
$\varepsilon^{\prime\prime}:=\epsilon-15\epsilon^{\prime}$ and
$\delta^{\prime\prime}:=\delta^{\prime}$, we conclude that
${\mathbf{x}}^{\prime\prime}$ is an
$(\epsilon^{\prime\prime},\delta^{\prime\prime})$-AMFM with
${\mathbf{x}}^{\prime\prime}_{\min}\geq\delta^{\prime\prime}$ in the graph
$G^{\prime\prime}$ obtained by adding at most
$90\epsilon^{\prime}\cdot\mu(G)=O(\epsilon+\delta)\cdot\mu(G)$ many dummy
vertices to $G$. The lemma follows. ∎

The above lemma allows us to compute an AMM quickly when $\mu(G)$ is large.
The following simple complementary lemma allows us to compute a maximal
matching quickly when $\mu(G)$ is small.

######  Lemma 6.12.

There exists a static deterministic algorithm that given an $O(1)$-approximate
vertex cover $U$ of graph $G=(V,E)$, compute a maximal matching in $G$ in time
$O(\mu(G)^{2})$.

###### Proof.

First, the algorithm computes a maximal matching $M$ in $G[U]$, taking
$O(|U|^{2})=O(\mu(G)^{2})$ time, since an $O(1)$-approximate vertex cover has
size $O(\mu(G))$.101010The endpoints of any maximum matching form a vertex
cover of size $2\mu(G)$. Then, we extend $M$ to be a maximal matching in all
of $G$ as follows: for each unmatched vertex $u\in U$, we scan the neighbors
of $u$ until we find an unmatched neighbor $v$ (in which case we add $(u,v)$
to $M$) or until we run out of neighbors of $u$. As $|M|\leq\mu(G)$ at all
times by definition of $\mu(G)$, we scan at most $2\mu(G)+1$ neighbors per
node $u\in U$ until we match $u$ (or determine that all of its neighbors are
unmatched), for a total running time of $O(U\cdot\mu(G))=O(\mu(G)^{2})$. Since
each edge in $G$ has an endpoint in the vertex cover $U$, this results in a
maximal matching. ∎

We are finally ready to prove Theorem 6.6, restated for ease of reference. See
6.6

###### Proof.

Our algorithm dynamically maintains data structures, using which it
periodically computes an $\epsilon$-AMM, the non-deleted edges of which serve
as its matching during the subsequent period. A period at whose start the
algorithm computes an $\epsilon$-AMM $M$ consists of
$\lfloor\epsilon\cdot|M|\rfloor\leq\epsilon\cdot\mu(G)$ updates, and so by
6.4, the undeleted edges of $M$ are a $6\epsilon$-AMM throughout the period.
We turn to describing the necessary data structures and analyzing their update
time and the (amortized) update time of the periodic AMM computations.
Throughout, we assume without loss of generality that $\varepsilon=2^{-k}$ for
$k\geq 0$ some integer.

The data structures. First, we maintain an $(\epsilon,\epsilon/16)$-AMFM
${\mathbf{x}}$ using update time $t_{f}$, and update recourse $u_{f}$. For
each edge $x_{e}\geq\varepsilon/16$, we set $x_{e}=\varepsilon/16$, noting
that this does not affect the salient properties of an
$(\varepsilon,\varepsilon/16)$-AMFM. This second assumption implies that
$\mathcal{C}$ is a coarsening algorithm for the dynamic AMFM we will wish to
coarsen. This implies that coarsening algorithm $\mathcal{C}$ can be run on
${\mathbf{x}}$ to maintain an $(\epsilon,\delta)$-coarsening
${\mathbf{x}}^{\prime}$ of ${\mathbf{x}}$, where each change to ${\mathbf{x}}$
incurs update time $t_{c}$, for a total update time of $O(t_{f}+u_{f}\cdot
t_{c})$. In addition, using [BK19], we deterministically maintain an
$O(1)$-approximate vertex cover $U\subseteq V$ using $O(1)$ update
time,111111Generally, [BK19] maintain a $(2+\epsilon)$-approximate vertex
cover in $O(\epsilon^{-2})$ for any $\epsilon\in(0,1)$. which is dominated by
the above update time.

The end of a period. When a period ends (and a new one begins), both the
current matching $M$ and the new matching $M^{\prime}$ that we compute for the
next matching are $O(\epsilon)$-AMMs, and so $|M|=\Theta(\mu(G))$ and
$|M^{\prime}|=\Theta(\mu(G))$. We compute $M^{\prime}$ as follows. If
$|M|\leq\varepsilon^{-2}$, we run the algorithm of Lemma 6.12, using the
$O(1)$-vertex cover $U$, in time $O(\mu(G)^{2})=O(|M^{\prime}|^{2})$,
amortized over $\epsilon\cdot|M^{\prime}|$ updates, for an amortized update
time of
$O(|M^{\prime}|^{2}/(\epsilon\cdot|M^{\prime}|))=O(\epsilon^{-1}\cdot|M^{\prime}|)=O(\epsilon^{-3})$.
Otherwise, we have that $(\mu(G)\geq)|M|>2\epsilon^{-2}$, and we use
${\mathbf{x}}$ and ${\mathbf{x}}^{\prime}$ and Lemma 6.11 to compute
$M^{\prime}$ in time
$O(\mu(G)\cdot\epsilon^{-2}\cdot\log(\epsilon^{-1}))=O(|M^{\prime}|\cdot\epsilon^{-2}\cdot\log(\epsilon^{-1}))$,
for an amortized update time of
$O(|M|\cdot\epsilon^{-2}\cdot\log(\epsilon^{-1}))/(\epsilon\cdot|M^{\prime}|)=O(\epsilon^{-3}\cdot\log(\epsilon^{-1}))$.

To summarize, the above algorithm maintains an $O(\epsilon)$-AMM within the
claimed running time. As this algorithm consists of deterministic steps
(including those of the vertex-cover algorithm of [BK19]) and runs algorithms
$\mathcal{F}$ and $\mathcal{C}$, the combined algorithm is
deterministic/adaptive/output-adaptive if the latter two algorithms are. ∎

###  6.4 Restricted Fractional Matchings

To conclude this section, we briefly note that the same approach underlying
Theorem 6.6 also allows us to round other known structured fractional
matchings in general graphs. In particular, we can also round the following
fractional matchings, introduced by [BS16].

######  Definition 6.13.

Fractional matching ${\mathbf{x}}\in\mathbb{R}^{E}_{\geq 0}$ is _$\varepsilon$
-restricted_ if $x_{e}\in[0,\varepsilon]\cup\\{1\\}$ for each edge $e\in E.$

The interest in restricted fractional matchings (in general graphs) is that
their integrality gap is low, in the following sense (see, e.g., [BS16,
ABD22]).

######  Proposition 6.14.

Let ${\mathbf{x}}$ be an $\alpha$-approximate fractional matching in $G$
(i.e., $\lVert{\mathbf{x}}\rVert\geq\alpha\cdot\mu(G)$) that is also
$\varepsilon$-restricted. Then, $\mathrm{supp}({\mathbf{x}})$ contains an
$\alpha\cdot(1-\varepsilon)$-approximate integral matching.

######  Theorem 6.15.

Let $\varepsilon=2^{-k}$ for $k\geq 11$ an integer. Let $\mathcal{F}$ be a
dynamic $\alpha$-approximate $\varepsilon$-restricted fractional matching
algorithm with update time $t_{f}$ and output recourse $u_{f}$. Let
$\mathcal{C}$ be a dynamic $(16\varepsilon,\varepsilon)$-coarsening algorithm
with $\mathtt{update}$ time $t_{c}$ for vectors ${\mathbf{x}}$ satisfying
$x_{e}\geq\varepsilon/16$ implies that $(x_{e})_{i}=0$ for $i>k+4$. Then there
exists a dynamic $\alpha(1-O(\varepsilon))$-approximate matching algorithm
$\mathcal{A}$ with update time $O(\varepsilon^{-3}+t_{f}+u_{f}\cdot t_{r})$.
Moreover, $\mathcal{A}$ is deterministic/adaptive/output-adaptive if both
$\mathcal{F}$ and $\mathcal{C}$ are.

The proof outline again mirrors that of Theorem 6.6 (and Lemma 4.3 before it),
maintaining essentially the same data structures, and so we only discuss the
key difference.

###### Proof (Sketch).

The maintained $(O(\varepsilon),\varepsilon)$-coarsening
${\mathbf{x}}^{\prime}$ of the dynamic $\varepsilon$-restricted fractional
matching ${\mathbf{x}}$ is $2\varepsilon$-restricted fractional matching, by
Property (C3). Moreover, by Property (C1) and $\lVert{\mathbf{x}}\rVert\geq
1$, we have that
$\lVert{{\mathbf{x}}^{\prime}}\rVert\geq(1-32\varepsilon)\lVert{\mathbf{x}}\rVert$.
Therefore, by 6.14, $\mathrm{supp}(x^{\prime})$ contains an integral matching
$M^{*}$ of cardinality
$|M^{*}|\geq\lVert{{\mathbf{x}}^{\prime}}\rVert\cdot(1-32\varepsilon)\geq\lVert{\mathbf{x}}\rVert\cdot(1-32\varepsilon)^{2}\geq\alpha(1-1024\varepsilon)\cdot\mu(G).$
Now, if instead of computing an AMM periodically, as in Theorem 6.6, we
compute an $\varepsilon$-approximate matching $M$ in time
$O(\varepsilon^{-1}|\mathrm{supp}({\mathbf{x}})|)=O(\varepsilon^{-1}\lVert{\mathbf{x}}\rVert/\varepsilon)=O(\varepsilon^{-2}\cdot\mu(G))$.121212For
example, we can use the $\varepsilon$-approximate maximum-weight matching
algorithm of [DP14], which runs in time $O(\varepsilon^{-1}\cdot m)$ in
$m$-edge unweighted graphs. We do so every $\varepsilon\cdot\mu(G)$ updates,
thus maintaining a $(1-3\varepsilon)$-approximation of $|M^{*}|$ throughout by
“stability” of the matching problem (see [GP13]. This then results in an
$\alpha(1-1024\varepsilon)\cdot(1-3\varepsilon)\geq\alpha(1-O(\varepsilon))$-approximation,
with essentially the same update time of Theorem 6.6, other than the
$O(\varepsilon^{-3}\cdot\log(\varepsilon^{-1}))$ term in the update time,
which is improved to $O(\varepsilon^{-3})$. ∎

By combining Theorem 6.15 with Lemma 6.7, we obtain efficient dynamic rounding
algorithms for $\varepsilon$-restricted fractional matchings, with update
times and determinism/adaptivity as the stated in Theorem 1.5

##  7 Decremental Matching

In this section we discuss applications of our rounding algorithms to speeding
up decremental matching algorithms. Prior results are obtained by a number of
fractional algorithms [BGS20, JJST22, BKS23b, ABD22], combined with known
rounding algorithms (or variants thereof [ABD22]). We show how our (partial)
rounding algorithms yield speeds ups on known decremental bipartite matching
algorithms, and bring us within touching distance of similar deterministic
results in general graphs.

##### Robust fractional matchings.

The approach underlying [BGS20, JJST22, ABD22] is to phaseically compute a
_robust_ fractional matching ${\mathbf{x}}$, in the sense that the value of
${\mathbf{x}}$ restricted to non-deleted edges remains
$(1-\varepsilon)$-approximate with respect to the current maximum (integral)
matching in the subgraph induced by non-deleted edges, unless the latter
decreases by a $(1-O(\varepsilon))$ factor. For example, in a complete graph,
a uniform fractional matching is robust, while an integral matching is not, as
deleting its edges would yield a $0$-approximation to the maximum matching,
which would be unaffected by such deletions. Formally, the above works
implement the following.

######  Definition 7.1.

An _$\varepsilon$ -robust_ decremental fractional matching algorithm
partitions the sequence of deletions into $P$ _phases_ of consecutive
deletions (determined during the algorithm’s run), and computes a fractional
matching ${\mathbf{x}}^{i}$ at the start of phase $i$, where
${\mathbf{x}}^{i}$ restricted to non-deleted edges is a
$(1-\varepsilon)$-approximate throughout phase $i$ (i.e., until
${\mathbf{x}}^{i+1}$ is computed).

As for dynamic algorithms, we may consider $\varepsilon$-robust decremental
fractional matching algorithms that are either deterministic or adaptive. All
currently known such algorithms are adaptive, and even deterministic.

In what follows, we show how our rounding algorigthms can be used to round
known $\varepsilon$-robust decremental fractional matching algorithms to
obtain new state-of-the-art decremental (integral) matching algorithms,
starting with bipartite graphs.

###  7.1 Bipartite Graphs

Applying the rounding algorithms of Theorem 1.2, one immediately obtains a
framework to rounding such decremental fractional bipartite matching
algorithms.

######  Theorem 7.2.

Let $\mathcal{F}$ be an $\varepsilon$-robust decremental fractional bipartite
matching algorithm, using total time $t^{\mathcal{F}}$ and at most
$p^{\mathcal{F}}$ phases. Let $\mathcal{R}$ be an $\varepsilon$-approximate
bipartite rounding algorithm with $\mathtt{update}$ time $t^{\mathcal{R}}_{U}$
and $\mathtt{init}$ time $t^{\mathcal{R}}_{I}({\mathbf{x}})$. Then, there
exists a $(1-2\varepsilon)$-approximate decremental bipartite matching
algorithm $\mathcal{A}$ which on graph starting with $m$ edges takes total
time
$O(t^{\mathcal{F}}+\sum_{i=1}^{p^{\mathcal{F}}}t^{\mathcal{R}}_{I}({\mathbf{x}}^{i})+m\cdot
t^{\mathcal{R}}_{U})$. Algorithm $\mathcal{A}$ is
deterministic/adaptive/output-adaptive if both $\mathcal{F}$ and $\mathcal{R}$
are.

###### Proof.

The combined algorithm $\mathcal{A}$ is direct. Whenever $\mathcal{F}$
computes a new fractional matching ${\mathbf{x}}^{i}$, we run
$\mathtt{init}(G,{\mathbf{x}}^{i},\varepsilon)$ in algorithm $\mathcal{R}$.
Between computations of fractional matchings ${\mathbf{x}}^{i}$ and
${\mathbf{x}}^{i+1}$, we call $\mathtt{update}(e,0)$ for each edge $e$
deleted. The running time is trivially
$O(t^{\mathcal{F}}+\sum_{i=1}^{p^{\mathcal{F}}}t^{\mathcal{R}}_{I}({\mathbf{x}}^{i})+m\cdot
t^{\mathcal{R}}_{U})$. As for the approximation ratio, the fractional matching
${\mathbf{x}}$ throughout a phase (i.e., the ${\mathbf{x}}^{i}$ value of
undeleted edges between computation of ${\mathbf{x}}^{i}$ and
${\mathbf{x}}^{i+1}$) is $(1-\varepsilon)$-approximate with respect to the
current maximum matching $\mu(G)$, and the rounding algorithm $\mathcal{R}$
maintains a matching $M\subseteq\mathrm{supp}({\mathbf{x}})$ with the desired
approximation ratio,

$\displaystyle|M|$
$\displaystyle\geq(1-\varepsilon)\cdot\lVert{\mathbf{x}}\rVert\geq(1-\varepsilon)^{2}\cdot\mu(G)\geq(1-2\varepsilon)\cdot\mu(G).$

Finally, as Algorithm $\mathcal{A}$ only uses algorithms $\mathcal{F}$ and
$\mathcal{R}$, the former is deterministic/adaptive/output-adaptive if the
latter two are. ∎

Theorem 7.2 in conjunction with Theorem 1.2 yield a number of improvements for
the decremental bipartite matching problem (see Table 1).131313The rounding
algorithm of [BK21] only states its $n$-dependence, which is $\log^{4}n$, but
a careful study shows that their $\varepsilon$-dependence is
$\varepsilon^{-6}$. In particular, these theorems yield decremental (integral)
bipartite matching algorithms with the same update time as the current best
_fractional_ algorithms for the same problems [BCH20, JJST22]. Our
improvements compared to prior work follows both from our faster update times
(previously of the order $\Omega(\varepsilon^{-4})$, and some with high
polylog dependencies), as well as our rounding algorithms’ initialization
times, which avoid us paying the update time per each of the potentially
$p^{\mathcal{F}}\cdot m$ many edges in the supports of
${\mathbf{x}}^{1},{\mathbf{x}}^{2},\dots,x^{p^{\mathcal{F}}}$. We discuss the
fractional algorithms of [BGS20, JJST22], substantiating the results in the
subsequent table, in Appendix C.

New Time Per Edge | Fractional Algorithm | Closest Prior Best |  Reference
---|---|---|---
$\varepsilon^{-2}\cdot n^{o(1)}$ (A) |  [JJST22] (see Lemma C.2) |  $\varepsilon^{-4}\cdot n^{o(1)}$ (A) |  [JJST22] \+ [Waj20]
$\varepsilon^{-3}\cdot\log^{5}n$ (D) | [JJST22] (see Lemma C.2) |  $\varepsilon^{-4}\cdot\log^{5}n$ (A) |  [JJST22] \+ [Waj20]
$\varepsilon^{-9}\cdot\log^{9}n$ (D) |  [JJST22] \+ [BK21]
$\varepsilon^{-4}\cdot\log^{3}n$ (D) | [BGS20] (see Lemma C.1) |  $\varepsilon^{-4}\cdot\log^{3}n$ (A) |  [BGS20] \+ [Waj20]
$\varepsilon^{-10}\cdot\log^{7}n$ (D) |  [BGS20] \+ [BK21]
Table 1: New results for $(1-\varepsilon)$-approximate Decremental Bipartite
Matching
(D) and (A) stand for deterministic, and (randomized) adaptive, respectively

###  7.2 Potential Future Applications: General Graphs

In [ABD22], Assadi, Bernstein and Dudeja follow the same robust fractional
matching approach of [BGS20], and show how to implement it in _general_
graphs. By assuming that $\mu(G)\geq\varepsilon\cdot n$ throughout, which only
incurs a (randomized) $\mathrm{poly}(\log n)$ slowdown, by known vertex
sparsification results [AKLY16], they show how to maintain an
$\varepsilon$-robust fractional matching that is $\varepsilon$-restricted
(6.13) in total time $m\cdot 2^{O(\varepsilon^{-1})}$. By adapting the
rounding scheme of [Waj20], they then round this fractional matching randomly
(but adaptively).

By appealing to Theorem 6.15 and Lemma 6.7, we can similarly round
$\varepsilon$-restricted fractional matchings deterministically, with a $\log
n\cdot\mathrm{poly}(\varepsilon^{-1})$ update time. Combining with
_deterministic_ vertex sparsification with a $n^{o(1)}$ slowdown [Kis22], we
obtain _almost_ all ingredients necessary for the first sub-polynomial-time
deterministic $(1-\varepsilon)$-approximate decremental matching algorithm in
general graphs. Unfortunately, the fractional algorithm of [ABD22] relies on
randomization in one additional crucial step to compute an
$\varepsilon$-robust fractional matching, namely in the subroutine
$M$-or-$E^{*}()$, that outputs either a large fractional matching respecting
some edge capacity constraints, or a minimum cut (whose capacities one then
increased). For bipartite graphs, [BGS20] gave a deterministic implementation
of this subroutine, though for general graphs this seems more challenging, and
so [ABD22] resorted to randomization to implement this subroutine. Our work
therefore leaves the de-randomization of this subroutine as a concrete last
step to resolving in the affirmative the following conjecture.

######  Conjecture 7.3.

There exists a determinsitic decremental $(1-\varepsilon)$-approximate
matching algorithm with total update time $m\cdot n^{o(1)}$, for any constant
$\varepsilon>0$.

## APPENDIX

##  Appendix A A $\mathtt{degree}\text{-}\mathtt{split}$ Algorithm

In this section we provide an implementation and analysis of the
$\mathtt{degree}\text{-}\mathtt{split}$ algorithm guaranteed by 2.4, restated
below. See 2.4

###### Proof of 2.4.

First, suppose $G$ is a simple graph (i.e., it contains no parallel edges). We
later show how to easily extend this to a multigraph with maximum multiplicity
two.

Recall that a _walk_ $\mathcal{W}$ in a graph is a sequence of edges
$(e_{1},\dots,e_{k})$, with $e_{i}=\\{v_{i},v_{i+1}\\}$. We call $v_{1}$ and
$v_{k+1}$ the _extreme_ vertices of $\mathcal{W}$. We call odd-indexed and
even-indexed edges $e_{i}$ _odd_ or _even_ for short. The walk $\mathcal{W}$
is a _cycle_ if $v_{1}=v_{k+1}$, and the walk is _maximal_ if it cannot be
extended, i.e., if there exists no edge $e=\\{v_{1},v\\}$ or
$e=\\{v_{k+1},v\\}$ outside of $\mathcal{W}$.

While $E\neq\emptyset$, Algorithm $\mathtt{degree}\text{-}\mathtt{split}$
repeatedly computes maximal walks $\mathcal{W}$, removes these walks’ edges
from $E$ and adds all odd edges (resp., even edges) of $\mathcal{W}$ to the
smaller (resp., larger) of $E_{1}$ and $E_{2}$, breaking ties in favor of
$E_{1}$. This algorithm clearly runs in linear time, as the $O(|\mathcal{W}|)$
time to compute a walk $\mathcal{W}$ decreases $|E|$ by $|\mathcal{W}|$.

Next, since each edge is added to one of $E_{1}$ or $E_{2}$, we have that
$|E|=|E_{1}|+|E_{2}|$. Moreover, since the number of odd and even edges differ
by at most one for each walk (the former being no less plentiful), we have
that $|E_{1}|\geq|E_{2}|$ and $\big{|}|E_{1}|-|E_{2}|\big{|}\leq 1$
throughout. Property (P1) follows.

Finally, fix a vertex $v$ and $i\in\\{1,2\\}$. By maximality of the walks
computed, once $v$ is an extreme vertex of at most one walk. Thus, all but at
most two edges of $v$ are paired into successive odd/even edges in some walks
computed. Consequently, the number of odd and even edges of $v$ can differ by
$0$, in which case $d_{i}(v)=\frac{d_{G}(v)}{2}$, they may differ by $1$, in
which case $d_{i}(v)\in\left\\{\lfloor\frac{d_{G}(v)}{2}\rfloor,\
\lceil\frac{d_{G}(v)}{2}\rceil\right\\}$, or they may differ by $2$, in which
case $v$ has two more odd edges than even edges, the last walk $v$ belongs to
is an odd-length cycle (and hence $G$ is not bipartite) and we have that
$d_{i}(v)\in\left\\{\frac{d_{G}(v)}{2}-1,\,\frac{d_{G}(v)}{2}+1\right\\}$.
Properties (P2) and (P3) follow.

Now, to address the (slightly) more general case where some edges have two
parallel copies, we let $G^{\prime}$ be the simple graph obtained after
removing all parallel edges from $G$, and let $E^{\prime}_{1}$ and
$E^{\prime}_{2}$ be the edge sets computed by running
$\mathtt{degree}\text{-}\mathtt{split}$ on $G^{\prime}$. Then, for each pair
of parallel edges $(e,e^{\prime})$ in $G$, we arbitrarily add one of the pair
to $E_{1}$ and add the other to $E_{2}$. Finally, we let $E_{1}\leftarrow
E_{1}\cup E^{\prime}_{1}$ and $E_{2}\leftarrow E_{2}\cup E^{\prime}_{2}$. It
is easy to see that the sets $E_{1}$ and $E_{2}$ are simple (by construction),
and that these sets then satisfy all three desired properties with respect to
$G$, since the edge sets $E^{\prime}_{1}$ and $E^{\prime}_{2}$ satisfy these
properties with respect to $G^{\prime}$, and every vertex $v$ has all of its
(parallel) edges in $E\setminus E^{\prime}$ evenly divided between $E_{1}$ and
$E_{2}$. The linear running time is trivial given the linear time to compute
$E^{\prime}_{1},E^{\prime}_{2}$. ∎

##  Appendix B Dynamic Set Sampling

In this section we provide an output-adaptive data structure for the dynamic
set sampling problem (restated below). Recall that this is the basic problem
of maintaining a dynamic subset of $[n]$ where every element is included in
the subset independently with probability $p_{i}$ under dynamic changes to
$p_{i}$ and re-sampling. This basic problem was studied by [TWLH10, BP17,
YWW23].

See 5.1

Our main result of this section is that we can implement in each operation in
total time linear in the number of operations, $n$, and the size of the $T$
output.

See 5.2

##### Comparison with the concurrent work of [YWW23].

Our solution is somewhat simpler than that of the concurrent set sampler of
[YWW23]. For our purposes, the only important difference is that our algorithm
is provably output-adaptive.

Our Algorithm 3 and associated proof of Theorem 5.2 stem from a simple insight
about computing when an element $i\in[n]$ will be in the output of
$\mathtt{sample}()$. Note that if there are no operations of the form
$\mathtt{set}(i,\alpha)$, then the probability $i$ is in any individual output
of $\mathtt{sample}()$ is $p_{i}.$ Consequently, the probability that $p_{i}$
is not in the output of $\mathtt{sample}()$ for the next $t$ calls to
$\mathtt{sample}()$ is $(1-p_{i})^{t}$. Therefore, the number of calls to
$\mathtt{sample}()$ it takes for $i$ to be in the output sample follows the
geometric distribution with parameter $p_{i}$, i.e. $\textrm{Geo}(p_{i})$!

Leveraging this simple insight above leads to an efficient set sampler data
structures. Naively, implementing set sampling takes $O(n)$ time per call to
$\mathtt{sample}()$, used to determine for each element $i$ whether or not it
should be in the output. However, we could instead simply sample from
$\mathrm{geom}(p_{i})$ (in expected $O(1)$, using [BF13]) whenever
$\mathtt{set}(i,\alpha)$ is called or $i$ is in the output of
$\mathtt{sample}()$, in order to determine _the next call_ to
$\mathtt{sample}()$ which will result in $i$ being in the output. Provided we
can efficiently keep track of this information for each $i$, this would yield
the desired bounds in Theorem 5.2.

Unfortunately, when sampling from $\mathrm{geom}(p_{i})$, the output could be
arbitrarily large (albeit with small probability). Further, maintaining the
data structure for knowing when $i$ is scheduled to be in the output of
$\mathtt{sample}()$ would naively involve maintaining a heap on arbitrary
large numbers, incurring logarithmic factors. There are many potential data-
structures and techniques to solve this problem. In our Algorithm 3 we provide
one simple, straightforward solution. Every $n$ calls to $\mathtt{sample}()$,
we “rebuild” our data structure and rather than sampling from
$\mathrm{geom}(p_{i})$ to determine the next call to $\mathtt{sample}()$ that
will output $i$, we instead simply sample to determine the next call to
$\mathtt{sample}()$ before the rebuild that will output $i$ (if there is one).
Algorithm 3 simply does this, resampling this time for $i$ whenever
$\mathtt{set}(i,\alpha)$ is called.

global : Size $n$ and $p\in[0,1]^{n}$

1

global : Current (relative) time $\tau$, subsets
$T_{1},...,T_{n}\subseteq[n]$, and next sample times
$\tau_{1},...,\tau_{n}\in[n+1]$

2

3function  _$\mathtt{init}(n,p\in[0,1]^{n})$_

4

5 Save $n$ and $p$ as global variables;

6 Initialize $\tau\leftarrow 1$, $T_{i}=\emptyset$, and $\tau_{i}=n+1$ for all
$i\in[n]$;

7

8 Call $\mathtt{set}(i,p_{i})$ for all $i\in S$;

9

10

11

12function  _$\mathtt{set}(i\in[n],\alpha\in[0,1])$_

13

14 if  _$\tau_{i}\neq n+1$_ then $T_{\tau_{i}}\leftarrow
T_{\tau_{i}}\setminus\\{i\\}$;

15

// The loop below can be implemented in expected $O(1)$ time (see Lemma B.1)

16

17 for  _$j=\tau$ to $n$_ do

18

19 Independently with probability $p_{i}$, set $T_{j}\leftarrow
T_{j}\cup\\{i\\}$, $\tau_{i}=j$, and return

20 end for

21

22 $\tau_{i}=n+1$;

23

24

25

26function  _$\mathtt{sample}()$_

27

28 Set $T\leftarrow T_{\tau}$ and then set $\tau\leftarrow\tau+1$;

29

30 if  _$\tau <n+1$_ then call $\mathtt{set}(i,p_{i})$ for all $i\in T$;

31

32 else set $\tau=1$, and then call $\mathtt{set}(i,p_{i})$ for all $i\in[n]$;

33

return : $T$

34

35

missingfnum@algorithm3Algorithm 3 Set Sampler Data Structure

Algorithm 3 is written without an efficient determination of the next output
time for each element, so that it is clear that this algorithm is a set
sampler. In the following Lemma B.1 we show how to perform this efficient
determination or, more precisely, implementing the for-loop in Lines 3-3 We
then use this lemma to prove Theorem 5.2.

######  Lemma B.1.

The for-loop in Lines 3-3 of Algorithm 3 can be implemented in expected $O(1)$
time in the word RAM model.

###### Proof.

The loop executes the return statement with a value of $j\in[t,n]$ with
probability $p^{j-t}(1-p)$. Consequently, if we let $\ell\geq 0$ be sampled by
the geometric distribution with probability $p$, i.e.,
$\Pr[\ell=v]=p^{v}(1-p)$ for all $v\in\mathbb{Z}_{>0}$, and if
$\ell\in\\{0,...,n-t\\}$ simply execute the return statement with $j=t+\ell$
and otherwise set $\tau_{i}=n+1$, then this is equivalent to the lines of the
for loop. Since sampling from a geometric distribution $\textrm{Geo}(p)$ in
this manner can be implemented in expected $O(\log(1/p)/w)=O(1)$ time in the
word RAM model [BF13], the result follows. ∎

###### Proof of Theorem 5.2.

Algorithm 3 maintains that after each operation ($\mathtt{init}$,
$\mathtt{set}$ or $\mathtt{sample}$), each $i\in[n]$ is a member of at most
one $T_{j}$. Further, if $i\in T_{j}$, then $\tau\leq j$ and $\tau_{i}=j$ and
moreover $\tau_{i}=n+1$ if and only if $i\notin T_{j}$ for any $j\in[n]$.
Further, the algorithm is designed (as discussed) so that $T_{\tau}$ is a
valid output of $\mathtt{sample}$ at time $\tau$ (for any updates of an
output-adaptive adversary, that is unaware of $T_{j}$ for $j\geq\tau$). Since
the algorithm also ensures that $\tau\leq n$, the algorithm has the desired
output. Further, from these properties it is clear that the algorithm can be
implemented in $O(n)$ space. It only remains to bound the running time for
implementing the algorithm.

To analyze the running time of the algorithm, first note that by Lemma B.1,
each $\mathtt{set}$ operation can be implemented in expected $O(1)$ time.
Consequently, $\mathtt{init}$ can be implemented in expected $O(n)$ time.
Further, since $T=\mathtt{sample}()$ simply calls $\mathtt{set}$ for elements
in its output or for all $n$ elements after every $n$ times it is called, it
has the desired expected runtime $O(1+|T|)$ as well. ∎

##  Appendix C Known Decremental Fractional Bipartite Matching Algorithms

For completeness, we briefly discuss the parameters of the decremental
bipartite algortihms of [BGS20, JJST22], which together with Theorem 7.2 and
Theorem 1.2 yield the results of Table 1.

######  Lemma C.1 (Congestion Balancing [BGS20]).

There exists an $\varepsilon$-robust decremental fractional bipartite matching
algorithm with total time $O(m\cdot\varepsilon^{-4}\cdot\log^{3}n)$ and
$O(\varepsilon^{-1}\cdot\log n)$ phases.

###### Proof.

The algorithm of [BGS20] consists of $O(\varepsilon^{-1}\cdot\log n)$ phases,
where a phase starts when the maximum matching size of $G$ decreases by a
factor of $(1-\varepsilon)$. The bottleneck of each phase is the
$O(m\cdot\varepsilon^{-2}\cdot\log^{3}n)$-time subroutine Robust-Matching,
which computes a fractional matching that does not change during the phase
(aside from nullification of value on deleted edges), and is guaranteed to
remain $(1-\varepsilon)$-approximate during the phrase [BCH20, Lemma 5.1].
This subroutine’s running time is $O(m\cdot\varepsilon^{-3}\cdot\log^{2}n)$.
Thus, the algorithm’s total running time is
$O(m\cdot\varepsilon^{-4}\cdot\log^{3}n)$. ∎

######  Lemma C.2 (Regularized Box-Simplex Games [JJST22]).

There exist $\varepsilon$-robust decremental fractional bipartite matching
algorithms that are:

  1. 1.

Deterministic, with total time $O(m\cdot\varepsilon^{-3}\cdot\log^{5}n)$ and
$O(\epsilon^{-2}\cdot\log^{2}n)$ phases [JJST22, Theorem 7].

  2. 2.

Adaptive, with total time $O(m\cdot\varepsilon^{-2}\cdot n^{o(1)})$ and
$O(\epsilon^{-2}\cdot\log^{2}n)$ phases [JJST22, Theorem 9].

## Acknowledgements

Thank you to Arun Jambulapati for helpful conversations which were
foundational for the static bipartite rounding algorithm in this paper and
subsequent developments.

## References

  * [ABD22] Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja.  Decremental matching in general graphs.  In Proceedings of the 49th International Colloquium on Automata, Languages and Programming (ICALP), pages 11:1–11:19, 2022.
  * [ABKL23] Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, and Huan Li.  On regularity lemma and barriers in streaming and dynamic matching.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), 2023.  To appear.
  * [ACC+18] Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc.  Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms.  In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), pages 79:1–79:16, 2018.
  * [AD16] Amir Abboud and Søren Dahlgaard.  Popular conjectures as a barrier for dynamic planar graph algorithms.  In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 477–486, 2016.
  * [AKLY16] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev.  Maximum matchings in dynamic graph streams and the simultaneous communication model.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1345–1364, 2016.
  * [AVW14] Amir Abboud and Virginia Vassilevska Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In Proceedings of the 55th Symposium on Foundations of Computer Science (FOCS), pages 434–443, 2014.
  * [BCH20] Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger.  Deterministic dynamic matching in ${O}(1)$ update time.  Algorithmica, 82(4):1057–1080, 2020.
  * [BDH+19] Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan.  Fully dynamic maximal independent set with polylogarithmic update time.  In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS), pages 382–405, 2019.
  * [Beh23] Soheil Behnezhad.  Dynamic algorithms for maximum matching size.  In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 129–162, 2023.
  * [BF13] Karl Bringmann and Tobias Friedrich.  Exact and efficient generation of geometric random variates and random graphs.  In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), pages 267–278, 2013.
  * [BFH19] Aaron Bernstein, Sebastian Forster, and Monika Henzinger.  A deamortization approach for dynamic spanner and dynamic maximal matching.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1899–1918, 2019.
  * [BGS15] Surender Baswana, Manoj Gupta, and Sandeep Sen.  Fully dynamic maximal matching in ${O}(\log n)$ update time.  SIAM Journal on Computing (SICOMP), 44(1):88–113, 2015.
  * [BGS20] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak.  Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing.  In Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS), pages 1123–1134, 2020.
  * [BHI15] Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano.  Deterministic fully dynamic data structures for vertex cover and matching.  In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 785–804, 2015.
  * [BHN16] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai.  New deterministic approximation algorithms for fully dynamic matching.  In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 398–411, 2016.
  * [BHN17] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai.  Fully dynamic approximate maximum matching and minimum vertex cover in ${O}(\log^{3}n)$ worst case update time.  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 470–489, 2017.
  * [BK19] Sayan Bhattacharya and Janardhan Kulkarni.  Deterministically maintaining a $(2+\epsilon)$-approximate minimum vertex cover in ${O}(1/\varepsilon^{2})$ amortized update time.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1872–1885, 2019.
  * [BK21] Sayan Bhattacharya and Peter Kiss.  Deterministic rounding of dynamic fractional matchings.  In Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP), 2021.
  * [BK22] Soheil Behnezhad and Sanjeev Khanna.  New trade-offs for fully dynamic matching via hierarchical edcs.  In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3529–3566, 2022.
  * [BK23] Joakim Blikstad and Peter Kiss.  Incremental $(1-\epsilon)$-approximate dynamic matching in ${O}(\mathrm{poly}(1/\epsilon))$ update time.  arXiv preprint arXiv:2302.08432, 2023.
  * [BKM+22] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer.  Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds.  In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 1671–1684, 2022.
  * [BKS23a] Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak.  Dynamic $(1+\epsilon)$-approximate matching size in truly sublinear update time.  arXiv preprint arXiv:2302.05030, 2023.
  * [BKS23b] Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak.  Dynamic algorithms for packing-covering lps via multiplicative weight updates.  page To appear, 2023.
  * [BKSW23] Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, and David Wajc.  Dynamic matching with better-than-2 approximation in polylogarithmic update time.  In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 100–128, 2023.
  * [BLM20] Soheil Behnezhad, Jakub Łącki, and Vahab Mirrokni.  Fully dynamic matching: Beating 2-approximation in ${\Delta}^{\epsilon}$ update time.  In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2492–2508, 2020.
  * [BNS19] Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak.  Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds.  In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS), pages 456–480, 2019.
  * [BP17] Karl Bringmann and Konstantinos Panagiotou.  Efficient sampling methods for discrete distributions.  Algorithmica, 79:484–508, 2017.
  * [BS15] Aaron Bernstein and Cliff Stein.  Fully dynamic matching in bipartite graphs.  In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), pages 167–179, 2015.
  * [BS16] Aaron Bernstein and Cliff Stein.  Faster fully dynamic matchings with small approximation ratios.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 692–711, 2016.
  * [CK19] Julia Chuzhoy and Sanjeev Khanna.  A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems.  In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pages 389–400, 2019.
  * [CKL+22] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In Proceedings of the 63rd Symposium on Foundations of Computer Science (FOCS), 2022.  To appear.
  * [CS18] Moses Charikar and Shay Solomon.  Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds.  In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), pages 33:1–33:14, 2018.
  * [CZ19] Shiri Chechik and Tianyi Zhang.  Fully dynamic maximal independent set in expected poly-log update time.  In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS), pages 370–381, 2019.
  * [Dah16] Søren Dahlgaard.  On the hardness of partially dynamic graph problems and connections to diameter.  In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), pages 48:1–48:14, 2016.
  * [DP14] Ran Duan and Seth Pettie.  Linear-time approximation for maximum weight matching.  Journal of the ACM (JACM), 61(1):1, 2014.
  * [Edm65] Jack Edmonds.  Maximum matching and a polyhedron with 0, 1-vertices.  Journal of research of the National Bureau of Standards B, 69(125-130):55–56, 1965.
  * [GLS+19] Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, and Shay Solomon.  $(1+\epsilon)$-approximate incremental matching in constant deterministic amortized time.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1886–1898, 2019.
  * [GP13] Manoj Gupta and Richard Peng.  Fully dynamic $(1+\varepsilon)$-approximate matchings.  In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS), pages 548–557, 2013.
  * [GRS14] Manoj Gupta, Venkatesh Raman, and SP Suresh.  Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time.  In Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), volume 29, pages 227–239, 2014.
  * [GSSU22] Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, and Amitai Uzrad.  Maintaining an edcs in general graphs: Simpler, density-sensitive and with worst-case time bounds.  Proceedings of the 5th Symposium on Simplicity in Algorithms (SOSA), pages 12–23, 2022.
  * [HKNS15] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 21–30, 2015.
  * [IL93] Zoran Ivkovic and Errol L Lloyd.  Fully dynamic maintenance of vertex cover.  In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 99–111, 1993.
  * [JJST22] Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian.  Regularized box-simplex games and dynamic decremental bipartite matching.  In Proceedings of the 49th International Colloquium on Automata, Languages and Programming (ICALP), 2022.
  * [Kis22] Peter Kiss.  Improving update times of dynamic matching algorithms from amortized to worst case.  Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 94:1–94:21, 2022.
  * [KPP16] Tsvi Kopelowitz, Seth Pettie, and Ely Porat.  Higher lower bounds from the 3sum conjecture.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1272–1287, 2016.
  * [NS17] Danupon Nanongkai and Thatchaphol Saranurak.  Dynamic spanning forest with worst-case update time: adaptive, las vegas, and ${O}(n^{1/2}-\varepsilon)$-time.  In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 1122–1129, 2017.
  * [OR10] Krzysztof Onak and Ronitt Rubinfeld.  Maintaining a large matching and a small vertex cover.  In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pages 457–464, 2010.
  * [PS16] David Peleg and Shay Solomon.  Dynamic $(1+\epsilon)$-approximate matchings: a density-sensitive approach.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 712–729, 2016.
  * [RSW22] Mohammad Roghani, Amin Saberi, and David Wajc.  Beating the folklore algorithm for dynamic matching.  In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 111:1–111:23, 2022.
  * [San09] Piotr Sankowski.  Maximum weight bipartite matching in matrix multiplication time.  Theoretical Computer Science (TCS), 410(44):4480–4488, 2009.
  * [Sol16] Shay Solomon.  Fully dynamic maximal matching in constant update time.  In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 325–334, 2016.
  * [TWLH10] Meng-Tsung Tsai, Da-Wei Wang, Churn-Jung Liau, and Tsan-sheng Hsu.  Heterogeneous subset sampling.  In Proceedings of the 16th, pages 500–509, 2010.
  * [Waj20] David Wajc.  Rounding dynamic matchings against an adaptive adversary.  In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 194–207, 2020.
  * [YWW23] Lu Yi, Hanzhi Wang, and Zhewei Wei.  Optimal dynamic subset sampling: Theory and applications.  In Proceedings of the 29th International Conference on Knowledge Discovery and Data Mining (KDD), 2023.
  * [ZH23] Da Wei Zheng and Monika Henzinger.  Multiplicative auction algorithm for approximate maximum weight bipartite matching.  In Proceedings of the 24th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2023.