# Adversarial Distortion for Learned Video Compression

Vijay Veerabadran$\dagger$3, Reza Pourreza1, Amirhossein Habibian2, Taco
Cohen2
1 Qualcomm AI Research, Qualcomm Technologies, Inc.
2 Qualcomm AI Research, Qualcomm Technologies Netherlands B.V.
3 Department of Cognitive Science, University of California San Diego

###### Abstract

In this paper, we present a novel adversarial lossy video compression model.
At extremely low bit-rates, standard video coding schemes suffer from
unpleasant reconstruction artifacts such as blocking, ringing etc. Existing
learned neural approaches to video compression have achieved reasonable
success on reducing the bit-rate for efficient transmission and reduce the
impact of artifacts to an extent. However, they still tend to produce blurred
results under extreme compression. In this paper, we present a deep
adversarial learned video compression model that minimizes an auxiliary
adversarial distortion objective. We find this adversarial objective to
correlate better with human perceptual quality judgement relative to
traditional quality metrics such as MS-SSIM and PSNR. Our experiments using a
state-of-the-art learned video compression system demonstrate a reduction of
perceptual artifacts and reconstruction of detail lost especially under
extremely high compression.

††† Work completed during internship at Qualcomm Technologies, Inc.
Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc.

##  1 Introduction

As the resolution of digitally recorded and streamed videos keeps growing,
there is an increasing demand for video compression algorithms that enable
fast transmission of videos without loss in Quality-of-Experience. While
current video codecs can encode video at low bitrates, this usually results in
unpleasant compression artifacts [34, 24]. The application of deep neural
networks to develop learned video compression algorithms as explored in recent
art [28, 25, 22, 13, 9, 8, 11] produces promising results at solving this
issue of perceptual artifacts. However, due to the use of distortion metrics
such as MS-SSIM [31] and MSE, the reconstructions tend to be blurry [6].

(a) |  (b) |  (c)
---|---|---

Figure 1: Demonstration of the effectiveness of training with adversarial
loss. (a) uncompressed frame, learned compression [13] via (b) MS-SSIM
distortion, (c) adversarial distortion, at similar bitrates. [See Fig. 5
cation for license information]

Generative Adversarial Networks (GANs) have been shown to be capable of
producing highly realistic images and videos from random noise inputs [18, 17,
35, 7, 10]. This suggests that the GAN objective more accurately reflects
image/video quality as perceived by humans. Indeed the work of [4] has shown
that GANs can be used for low-rate high-quality image compression, by
augmenting the rate/distortion loss with an adversarial loss. However, so far
there is little work on the application of adversarial losses to video
compression due to scaling issues.

We tackle the scaling issue via factorization of our adversarial discriminator
into smaller neural network components and show results that demonstrate our
compression system’s relatively improved perceptual quality even under extreme
compression (see Fig. 1). Our model is based on the one proposed by [13],
which is a 3D autoencoder with discrete latents and a PixelCNN++[29] prior,
trained end-to-end to optimize a rate/distortion loss. Our contributions shall
be applicable to other learned video compression systems in general. We also
present an ablation study resulting from our search across various
formulations of GANs in terms of their architecture and loss functions within
the context of lossy video compression. The contributions of this paper are:
_i)_ we propose adversarial loss to improve the perceptual quality of learned
video compression, _ii)_ we study techniques to improve the training stability
using adversarial loss, _iii)_ we study a spatial-temporal factorization of
discriminator to enable end-to-end training of deep video compression
networks.

##  2 Learned Video Compression

Figure 2: Lossy video compression with adversarial distortion, (a) learned
video compression component, (b) adversarial distortion components, where
Discs and Disct represent the spatial and the spatio-temporal discriminators.

[Frames by Ambrose Productions CC BY-SA 3.0
https://creativecommons.org/licenses/by/3.0/legalcode, via YouTube]

A learned video compression typically consists of an encoder, decoder, entropy
estimator and distortion estimator. All the components are trained end-to-end
on a collection of videos $\mathbf{x}$.

Encoder maps an input sequence $\mathbf{x}$ into a latent representation
$\mathbf{z}=\mathbf{E}_{\phi}(\mathbf{x})$. Encoder is a stack of
convolutional layers with several down-samplings that reduce the input
dimension. In the last layer, encoder employs a quantisation function on the
activations to reduce the bit-width of latents
$\mathbf{z}=\mathbf{Q}(\tilde{\mathbf{z}})$. Quantizer maps each element, or
group of elements, in activations $\tilde{\mathbf{z}}_{i}$ to a discrete
symbol $\mathbf{z}_{i}\in\\{0,\dots,L\\}$. Learning discrete representation,
as a non-differentiable function, requires adding uniform noise or soft
assignment as an approximation. The decoder, which is a stack of convolutional
layers with several up-samplings, reconstructs the video given discrete
latents $\hat{\mathbf{x}}=\mathbf{D}_{\psi}(\mathbf{z})$.

Entropy estimator predicts the average number of bits needed to encode latents
using a lossless entropy coding schema such as Huffman or arithmetic coding.
The bit rate is measured as the cross-entropy between the true distribution of
latents $p(\mathbf{z})$ and a density estimated by $P_{\theta}(\mathbf{z})$ as
in Eq. 1. The density estimator $P_{\theta}(\mathbf{z})$ is parameterized as a
neural network usually with an auto-regressive architecture  _i.e._ PixelCNN++
[29].

$\mathbf{H}(\mathbf{z})=\mathbb{E}_{\mathbf{z}\sim
p(\mathbf{z})}[-\log(P_{\theta}(\mathbf{z}))]$ (1)

Distortion loss measures the difference between the input and reconstructed
videos $\mathbf{d}(\mathbf{x},\hat{\mathbf{x}})$ usually by pixel-wise
distances, such as $\ell_{1}$ and $\ell_{2}$, or by more sophisticated metrics
such as MS-SSIM. All the aforementioned components are trained end-to-end by
minimizing a rate-distortion trade-off as the loss function:

$\mathbf{d}(\mathbf{x},\mathbf{D}_{\psi}(\mathbf{E}_{\phi}(\mathbf{x}))+\beta\mathbf{H}(\mathbf{z})$
(2)

##  3 Adversarial Distortion Loss

The distortion, measured by pixel-wise metrics  _i.e._ $\ell_{1}$, $\ell_{2}$,
and MS-SSIM, are often not perfectly aligned with perceptual quality. Recent
work [6] mathematically proves that the distortion and perceptual quality are
at odds with each other and minimizing the mean distortion leads to a decrease
in perceptual quality. Instead of solely relying on pixel-wise distances, we
define the distortion as an adversarial loss between the decoder and a
discriminator $\mathbf{C}_{\omega}$. This setting can be interpreted as
training a conditional GAN, where the decoder $\mathbf{D}_{\psi}$ learns to
generate a video given the encoded latents $\mathbf{z}$. The discriminator
encourages the decoder to generate videos which reside on the data manifold
that improves perceptual quality.

| $f$ | $g$ | $h$
---|---|---|---
Minimax [12] | $-\log(1+e^{-y})$ | $-y-\log(1+e^{-y})$ | $-y-\log(1+e^{-y})$
Wasserstein [5] | $y$ | $-y$ | $-y$
Least Squares [23] | $-(y-1)^{2}$ | $-y^{2}$ | $(y-1)^{2}$

Table 1: Component functions for a few adversarial losses.

###  3.1 Stable adversarial training

Adversarial loss Adversarial loss can be defined in various formulations
depending on how to specify the component functions $f$, $g$ and $h$:

$\displaystyle\max_{\mathbf{C}_{\omega}}\;$
$\displaystyle\mathbb{E}_{\mathbf{x}}[f(\mathbf{C}_{\omega}(\mathbf{x}))]+\mathbb{E}_{\hat{\mathbf{x}}}[g(\mathbf{C}_{\omega}(\hat{\mathbf{x}}))]$
(3) $\displaystyle\min_{\mathbf{D}_{\psi}}\;$
$\displaystyle\mathbb{E}_{\hat{\mathbf{x}}}[h(\mathbf{C}_{\omega}(\hat{\mathbf{x}}))]$
(4)

Table 1 specifies the component functions for several widely used GAN
formulations. We investigate the impact of each formulation on training
stability as they have different loss landscapes and gradient behavior;
finding the best formulation is hence non-trivial. Minimax loss [12] and
Wasserstein loss [5] resulted in fairly decent improvements in terms of
reconstruction quality, but we noticed the training to be unstable and time
consuming. We also experimented with the Least Squares [23] and Relativistic
[16] formulations. Both of these formulations resulted in stable adversarial
training. Among these two choices, our best formulation was the Least Squares
loss that generated higher quality videos (see section 4.2).

Perceptual loss As a way of further stabilizing our model’s adversarial
training, we incorporated a semantic loss [21, 30] that minimizes the
$\ell_{1}$ of the difference between framewise VGG-19 representations of
$\mathbf{x}$ and $\hat{\mathbf{x}}$. This semantic loss resulted in faster and
more stable training of our adversarial video compression model.

###  3.2 Factorized spatial-temporal discriminators

Recent work in training GANs to generate videos points out the advantage of
scaling up the training, _i.e._ , using larger batch sizes, deeper models etc.
[10]. However, due to scalability issues relating to working with video data
and the models size, we faced difficulty in jointly training all components.
In this case, our two choices to scale up our training were: _(i)_ finetune
the decoder using an adversarial distortion and fixing the prior and encoder,
hence loading only the adversarial distortion components in memory, and _(ii)_
factorizing our model into smaller components that enable large-scale
training. While analyzing the compression performance of the above two
choices, we observed that the latter produced higher quality reconstruction at
the same bit-rates. In order to scale up joint adversarial training for our
complete model, we resorted to factorizing the discriminator into two smaller
spatial and spatio-temporal discriminators. Both these discriminators were
formulated as LSGAN discriminators. The average loss from these discriminators
was used to train the decoder.

Putting all together, we train our model end-to-end by optimizing the rate-
distortion trade-off Eq. 2 using the following distortion loss:

$\mathbf{d}(\mathbf{x},\hat{\mathbf{x}})=\alpha\left\|\mathbf{x}-\hat{\mathbf{x}}\right\|_{2}+\gamma\left\|\mathbf{\sigma}(\mathbf{x})-\mathbf{\sigma}(\hat{\mathbf{x}})\right\|_{1}+\rho[(\mathbf{C}_{\omega}(\hat{\mathbf{x}})-1)^{2}]$
(5)

where $\mathbf{\sigma}$ represents the VGG-19 features111We used features from
the $4^{th}$ convolution before the 5th max-pooling layer of an ImageNet-
trained VGG-19 network.. These design choices are summarized in our
architecture in Fig. 2.

##  4 Experiments

Figure 3: Comparison of RDAE and our method on Kinetics validation set.

###  4.1 Experimental setup

Network architecture We demonstrate the impact of our adversarial training on
the Rate-Distortion Autoencoder [13] (RDAE) model which achieves state-of-the-
art video compression performance compared to other learned [22, 33]
compression methods in terms of MS-SSIM at various bit-rates. Further details
on the architecture of RDAE’s encoder, decoder, entropy estimator and
quantizer can be found in [13]. We employed a 2D ResNet-34 [15] (trained on
ImageNet) and a 3D ResNet [14] (trained from scratch) as our spatial and
spatio-temporal discriminators respectively. We spatially downsize our spatio-
temporal discriminator’s input by half in order to save memory, however, we
did not temporally subsample our spatial discriminator’s input.

Dataset We created a dataset sourced from Kinetics400 [19] by selecting the
first 16 frames from each high-quality video and downsampling them to
alleviate the existing compression artifacts resulting in a total of 93750
videos for training and 5687 videos for validation. We used random $160\times
160$ crops for training and used full-size frames for validation. We used UVG
[2] as the test dataset for comparisons with other methods.

Figure 4: LPIPS comparisons of H.264, H.265, RDAE, and our method on UVG.

Implementation details We pretrained our video compression model using rate-
loss and MSE distortion loss to speed up adversarial training; this step
provided a good initialization for adversarially training decoder weights. Our
hyperparameter choices for optimizing Eq. 5 are: $\alpha=0.005$, $\gamma=0.1$,
and $\rho=0.0001$. We used a batch size of 37, for a total of 12 epochs. We
trained our network with 4 values of $\beta=\\{0.1,0.3,0.5,0.7\\}$ to obtain a
rate-distortion curve. All models were trained using Adam optimizer [20] with
learning rate of $10^{-4}$, $\beta_{1}=0.9$ and $\beta_{2}=0.999$.

|
---|---
(a) Uncompressed frame |

---

(b) H.265, 0.0294 bpp |  (c) RDAE, 0.0339 bpp |  (d) Ours, 0.0309 bpp
---|---|---

Figure 5: Visual comparison of H.265, RDAE, and our method at a comparable
bitrate. (a) shows an uncompressed frame (frame 49 of Netflix Tango in Netflix
El Fuente [3]), (b), (c), and (d) show the close-ups of the reconstructed
frame from H.265, RDAE, and our method, respectively. Our method is void of
the compression artifacts present in H.265 and oversmoothing present in RDAE
under low bit-rates.

[Frame 49 of Tango video from Netflix Tango in Netflix El Fuente, produced by
Netflix, with CC BY-NC-ND 4.0 license:
https://media.xiph.org/video/derf/ElFuente/Netflix_Tango_Copyright.txt]

###  4.2 Results

Comparison to state of the art In this section, we compare the performance of
our method with a learned video compression method RDAE [13] as well as two
non-learned codecs H.265 [27] and H.264 [32]. Fig. 3 shows the comparison of
our method with RDAE in terms of Inception Score [26] (IS, $\uparrow$) on
Kinetics validation set. Incorporation of adversarial training improves IS,
and hence the perceptual salience of decoded videos by a great extent.

Due to the small number of videos present in UVG, we are unable to accurately
compute IS on this dataset; we report a framewise Learned Perceptual Image
Patch Similarity [36] (LPIPS, $\downarrow$) score on UVG for this reason. Fig.
4 shows the comparison of our method with RDAE, H.264 and H.265 in terms of
LPIPS on UVG dataset. We used ffmpeg [1] implementation of H.265 and H.264.
From this analysis, we observe that adversarial training improves the
perceptual quality of RDAE, resulting in a lower LPIPS score. Our model,
albeit underperforms H.265, closes the gap between the learned methods and
H.265 in terms of LPIPS to a high extent. In Fig. 5 we compare the visual
quality of our lowest rate model with H.265 and RDAE at a similar rate. We can
see that our result is relatively free from the compression artifacts usually
present in H.265 and RDAE at low bitrate.

Ablation study We trained video compression models separately on each of the 4
GAN loss formulations mentioned in section 3 along with a stabilizing pixel-
wise $\ell_{1}$\- or $\ell_{2}$-norm of the distance between $\mathbf{x}$ and
$\hat{\mathbf{x}}$ (8 GAN models in total, WGAN not reported due to unstable
training). We report a summary of these experiments in Table 2 and we decided
to use the best performing LSGAN with $\ell_{2}$ pixel-wise loss for our video
compression model.

GAN Type | Pixel Loss | MS-SSIM | PSNR (dB)
---|---|---|---
DCGAN [12] | L1 | 0.957 | 26.655
DCGAN | L2 | 0.958 | 26.862
RaGAN [16] | L1 | 0.957 | 26.554
RaGAN | L2 | 0.957 | 26.625
LSGAN [23] | L1 | 0.96 | 26.905
LSGAN | L2 | 0.961 | 27.032
Table 2: Ablation study on different GAN losses, PSNR and MS-SSIM Comparisons
on Kinetics validation set.

##  5 Conclusion

In this paper, we have presented a new deep adversarial lossy video
compression algorithm that outperforms state-of-the-art learned video
compression systems in terms of visual quality. By employing adversarial
training for the decoder, we demonstrate reduction in the perceptual artifacts
(especially under very low bit-rates) typically present in the reconstructed
output. We have also presented an ablation study of our design choices that
resulted in our final adversarial compression model.

## References

  * [1] ffmpeg.  http://ffmpeg.org/.  Accessed: 2020-03-03.
  * [2] Ultra Video Group test sequences.  http://ultravideo.cs.tut.fi/.  Accessed: 2020-03-03.
  * [3] Xiph.org video test media [derf’s collection].  https://media.xiph.org/video/derf/.  Accessed: 2020-03-03.
  * [4] Eirikur Agustsson, Michael Tschannen, Fabian Mentzer, Radu Timofte, and Luc Van Gool.  Generative adversarial networks for extreme learned image compression.  In ICCV, 2019.
  * [5] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein gan.  arXiv, 2017.
  * [6] Yochai Blau and Tomer Michaeli.  The perception-distortion tradeoff.  In CVPR, 2018.
  * [7] Andrew Brock, Jeff Donahue, and Karen Simonyan.  Large scale gan training for high fidelity natural image synthesis.  arXiv, 2018.
  * [8] Tong Chen, Haojie Liu, Qiu Shen, Tao Yue, Xun Cao, and Zhan Ma.  Deepcoder: A deep neural network based video compression.  In VCIP, 2017.
  * [9] Zhibo Chen, Tianyu He, Xin Jin, and Feng Wu.  Learning for video compression.  IEEE Trans. on Circuits and Systems for Video Technology, 2019.
  * [10] Aidan Clark, Jeff Donahue, and Karen Simonyan.  Efficient video generation on complex datasets.  arXiv, 2019.
  * [11] Abdelaziz Djelouah, Joaquim Campos, Simone Schaub-Meyer, and Christopher Schroers.  Neural inter-frame compression for video coding.  In ICCV, 2019.
  * [12] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In NeurIPS, 2014.
  * [13] Amirhossein Habibian, Ties van Rozendaal, Jakub M Tomczak, and Taco S Cohen.  Video compression with rate-distortion autoencoders.  In ICCV, 2019.
  * [14] Kensho Hara, Hirokatsu Kataoka, and Yutaka Satoh.  Can spatiotemporal 3d cnns retrace the history of 2d cnns and imagenet?  In CVPR, 2018.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  arXiv preprint arXiv:1512.03385, 2015.
  * [16] Alexia Jolicoeur-Martineau.  The relativistic discriminator: a key element missing from standard gan.  arXiv, 2018.
  * [17] Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen.  Progressive growing of gans for improved quality, stability, and variation.  arXiv, 2017.
  * [18] Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In CVPR, 2019.
  * [19] Will Kay, João Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, Mustafa Suleyman, and Andrew Zisserman.  The Kinetics Human Action Video Dataset.  arxiv, 2017.
  * [20] D Kingma and J Ba.  Adam: A Method for Stochastic Optimization.  2015\.
  * [21] Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al.  Photo-realistic single image super-resolution using a generative adversarial network.  In CVPR, 2017.
  * [22] Guo Lu, Wanli Ouyang, Dong Xu, Xiaoyun Zhang, Chunlei Cai, and Zhiyong Gao.  Dvc: An end-to-end deep video compression framework.  In CVPR, 2019.
  * [23] Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley.  Least squares generative adversarial networks.  In ICCV, 2017.
  * [24] Reza Pourreza, Amir Ghodrati, and Amirhossein Habibian.  Recognizing compressed videos: Challenges and promises.  In ICCV Workshops, 2019.
  * [25] Oren Rippel, Sanjay Nair, Carissa Lew, Steve Branson, Alexander G Anderson, and Lubomir Bourdev.  Learned video compression.  In ICCV, 2019.
  * [26] Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen.  Improved techniques for training gans.  In NeurIPS. 2016.
  * [27] G J Sullivan, J R Ohm, W J Han, and T Wiegand.  Overview of the High Efficiency Video Coding (HEVC) Standard.  IEEE Trans. on Circuits and Systems for Video Technology, 2012.
  * [28] Michael Tschannen, Eirikur Agustsson, and Mario Lucic.  Deep generative models for distribution-preserving lossy compression.  In NeurIPS, 2018.
  * [29] Aaron Van den Oord, Nal Kalchbrenner, Lasse Espeholt, Oriol Vinyals, Alex Graves, et al.  Conditional image generation with pixelcnn decoders.  In NeurIPS, 2016.
  * [30] Xintao Wang, Ke Yu, Shixiang Wu, Jinjin Gu, Yihao Liu, Chao Dong, Yu Qiao, and Chen Change Loy.  Esrgan: Enhanced super-resolution generative adversarial networks.  In ECCV, 2018.
  * [31] Zhou Wang, Alan C Bovik, Hamid R Sheikh, Eero P Simoncelli, et al.  Image quality assessment: from error visibility to structural similarity.  IEEE Trans. on Image Processing, 2004.
  * [32] T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra.  Overview of the h.264/avc video coding standard.  IEEE Trans. on Circuits and Systems for Video Technology, 2003.
  * [33] Chao-Yuan Wu, Nayan Singhal, and Philipp Krahenbuhl.  Video compression through image interpolation.  In ECCV, 2018.
  * [34] Kai Zeng, Tiesong Zhao, Abdul Rehman, and Zhou Wang.  Characterizing perceptual artifacts in compressed video streams.  In Human Vision and Electronic Imaging XIX, 2014.
  * [35] Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena.  Self-attention generative adversarial networks.  arXiv, 2018.
  * [36] Richard Zhang, Phillip Isola, Alexei A. Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric.  arXiv, 2018.


11institutetext: Indian Institute of Technology Madras, India
11email<EMAIL_ADDRESS>
# Stable Matchings with Flexible Quotas

Girija Limaye  Meghana Nasre

###### Abstract

We consider the problem of assigning agents to programs in the presence of
two-sided preferences, commonly known as the Hospital Residents problem. In
the standard setting each program has a rigid upper quota which cannot be
violated. Motivated by applications where quotas may be flexible, we propose
and study the problem of computing stable matchings under flexible quotas –
denoted as the ${\sf SMFQ}$ setting.

In the $\sf SMFQ$ setting we have a cost associated with every program and
these costs control the quotas. Our goal is to compute a stable matching that
matches all agents and is optimal with respect to the cost criteria. We study
two optimization problems with respect to the costs and show that there is a
sharp contrast in the complexity status of the two optimization criteria. We
also establish the connection of our model with the stable extension problem
in an apparently different two-round setting of the stable matching problem.
We show that our results in the $\sf SMFQ$ setting generalize the stable
extension problem.

###### Keywords:

Matchings under preferences, Stable matchings, Stable extensions, Flexible
quotas, Hardness of approximation, Approximation algorithms, Fast exponential
algorithms

##  1 Introduction

The stable matching problem in the many-to-one setting, also known as the
Hospital Residents problem has been extensively investigated since it is
applicable in several real world settings like assigning students to schools
[1] or elective courses [18], under-graduate students to university programs
[3] and many more. A stable matching problem is modeled as a bipartite graph
$G=(\mathcal{A}\cup\mathcal{P},E)$ where $\mathcal{A}$ and $\mathcal{P}$
denote the set of agents and programs respectively and $(a,p)\in E$ if and
only if $a\in\mathcal{A}$ and $p\in\mathcal{P}$ are mutually acceptable to
each other. Each agent and program ranks a subset from the other side in a
strict order and this ranking is called as the preference list of the agent or
program. If $x$ prefers $y$ over $z$, we denote it by $y>_{x}z$. In the
standard setting a program $p$ has an upper-quota denoted by $q(p)$. We denote
this as the SM setting throughout the paper.

A matching $M\subseteq E$ in $G$ is an assignment of agents to programs such
that each agent is matched to at most one program and a program is matched to
at most $q(p)$ many agents. Let $M(a)$ denote the program that agent $a$ is
matched to in $M$ and $M(p)$ denote the set of agents matched to program $p$
in matching $M$. Every agent prefers being matched to one of its acceptable
partners over remaining unmatched. A program $p$ is called under-subscribed in
$M$ if $|M(p)|<q(p)$ and fully-subscribed in $M$ if $|M(p)|=q(p)$. Stability
is a well-accepted notion of optimality in this setting and is defined as
follows.

######  Definition 1 (Stable matchings in SM setting)

A pair $(a,p)\in E\setminus M$ is a blocking pair w.r.t. the matching $M$ if
$p>_{a}M(a)$ and $p$ is either under-subscribed in $M$ or there exists at
least one agent $a^{\prime}\in M(p)$ such that $a>_{p}a^{\prime}$. A matching
$M$ is stable if there is no blocking pair w.r.t. $M$.

It is well known that every instance of the stable matching problem admits a
stable matching and it can be computed in linear time [11]. However, a stable
matching can be half the size of a maximum cardinality matching (see instance
$G$ in Fig. 1 where $a_{3}$ and $a_{5}$ are left unassigned in any stable
matching).

$\displaystyle a_{1}$ $\displaystyle:p_{1},p_{2}$ $\displaystyle
a_{2},a_{3},a_{4}$ $\displaystyle:p_{2},p_{1}$ $\displaystyle a_{5}$
$\displaystyle:p_{2}$

$\displaystyle\ p_{1}$ $\displaystyle:a_{2},a_{4},a_{1},a_{3}$ $\displaystyle\
p_{2}$ $\displaystyle:a_{1},a_{2},a_{5},a_{3},a_{4}$

Figure 1: Instance with five agents, two programs and the preferences of
agents and programs. For the ${\sf SM}$ setting let $q(p_{1})=2$ and
$q(p_{2})=1$ and denote the instance as $G$. The matching
$N=\\{(a_{1},p_{1}),(a_{2},p_{2}),(a_{4},p_{1})\\}$ is a stable in $G$. For
the $\sf SMFQ$ setting let $c(p_{1})=1$ and $c(p_{2})=2$ and denote the
instance as $H$.

Size of a matching plays a very important role in real-world applications
where leaving agents unmatched is undesirable and sometimes even unacceptable.
Relaxing stability in order to enable larger size matchings has been
investigated extensively in literature [14, 5]. However, in all such works the
quotas are considered rigid which may not be the case in certain applications.

In real-world applications of the SM  problem, the assignment of agents to
programs operates as follows: agents and programs submit their preferences and
quotas to the central administrative authority who then outputs a stable
assignment. This task is typically complicated by the presence of high-demand
programs with limited quotas. In practice, quotas are determined by logistic
considerations like class size in case of course allocation and resource
availability in case of school choice and may be flexible. For instance, every
semester elective allocation for under-graduate students at IIT Madras happens
via an automated procedure and once the preferences of students are available
to the academic office, course instructors are consulted to adjust class
capacities if appropriate. A recent work by Gajulapalli et al. [10] studies
the school-choice problem in a two round-setting. Here, in the first round the
quotas given as input are considered rigid. In the second round though, the
quotas of some schools are violated in order to match additional students in a
stability preserving manner.

Motivated by such applications, we introduce and study the problem of
computing stable matchings with flexible quotas – denoted as $\sf SMFQ$
setting. Having unrestricted quotas is unreasonable hence we let costs control
quotas in our setting. An instance $H$ in the $\sf SMFQ$ setting is similar to
the ${\sf SM}$ setting except that programs do not have quotas associated,
instead a program $p$ has a non-negative integer $c(p)$ denoting the cost of
matching an agent to $p$. Since there are no quotas in the ${\sf SMFQ}$
setting, in an output matching some programs may have no agents assigned to
them – we denote such programs as closed. We modify the definition of
stability in the ${\sf SMFQ}$ setting and use this throughout the paper.

######  Definition 2 (Stable matchings in $\sf SMFQ$ setting)

A pair $(a,p)\in E\setminus M$ is a blocking pair w.r.t. the matching $M$ if
$p>_{a}M(a)$ and there exists at least one agent $a^{\prime}\in M(p)$ such
that $a>_{p}a^{\prime}$. A matching $M$ is stable if there is no blocking pair
w.r.t. $M$.

In literature, such a blocking pair is also considered as an envy pair
$(a,a^{\prime})$ and the matching $M$ is called envy-free [24]. In the SM
setting, an envy-free matching need not be stable but in the $\sf SMFQ$
setting, envy-free matchings are stable. In the $\sf SMFQ$ setting, our goal
is to compute an $\mathcal{A}$-perfect matching (one that matches all agents)
that is stable with respect to the preferences subject to the following two
optimization criteria with respect to costs.

  1. 1.

Minimize the total cost: The total cost of a matching $M$ is defined as
$\sum_{p\in\mathcal{P}}(|M(p)|\cdot c(p))$. Our goal is to compute an
$\mathcal{A}$-perfect stable matching that minimizes the total costs – we
denote this as the $\sf MINSUM$ problem.

  2. 2.

Minimize the max cost: The maximum cost (spent at a program) for a matching
$M$ is defined as $\max_{p\in\mathcal{P}}\\{|M(p)|\cdot c(p)\\}$. Our goal is
to compute an $\mathcal{A}$-perfect stable matching that minimizes the maximum
cost – we denote this as the $\sf{MINMAX}$ problem.

In the $\sf SMFQ$ instance $H$ in Fig. 1, the matching
$N^{\prime}=\\{(a_{1},p_{1}),(a_{2},p_{2}),(a_{3},p_{1}),\allowbreak(a_{4},p_{1}),(a_{5},p_{2})\\}$
is $\mathcal{A}$-perfect as well as stable with respect to the preferences.
The total cost of $N^{\prime}$ is $7$ and the max-cost of $N^{\prime}$ is $4$.
It is easy to verify that in the instance $H$, the matching $N^{\prime}$ is an
optimal solution for both the $\sf MINSUM$ as well as the $\sf{MINMAX}$
problem. This need not be true in general; in fact we prove a sharp contrast
in the complexity status of the two problems.

###  1.1  Our Results

We show the following new results for the $\sf SMFQ$ setting in this paper.

###### Theorem 1.1

The $\sf{MINMAX}$ problem is solvable in polynomial time.

###### Theorem 1.2

The $\sf MINSUM$ problem is $\sf NP$-hard even when every agent has a
preference list of length exactly $f\geq 2$, there is a master list ordering
on agents and programs and the instance has $2$ distinct costs.

In the $\sf SMFQ$ setting since $\mathcal{A}$-perfectness is guaranteed, it is
natural for agents to submit short preference lists. However, since there is a
guarantee that every agent is matched, the central authority is likely to
impose a minimum requirement on the length of the preference list [15]. We
further note that under the two extreme scenarios – that is all preference
lists are unit length or all preference lists are complete, the $\sf MINSUM$
problem admits a simple polynomial time algorithm. Theorem 1.2 shows that the
general case is $\sf NP$-hard. We also show that $\sf MINSUM$ is hard to
approximate within a constant factor, unless $\sf P=\sf NP$.

###### Theorem 1.3

The $\sf MINSUM$ problem cannot be approximated within a factor
$\frac{7}{6}-\epsilon,\epsilon>0$ even when the instance has $3$ distinct
costs, unless $\sf P=\sf NP$.

On the positive side, we present the following approximation algorithms.

###### Theorem 1.4

The $\sf MINSUM$ problem admits the following approximation algorithms. Let
$\ell_{p}$ denote the maximum length of preference list of any program.

  1. (I)

a linear time $\ell_{p}$-approximation algorithm.

  2. (II)

a $|\mathcal{P}|$-approximation algorithm.

We present a fast exponential algorithm for the instances where number of
distinct costs is small. The number of distinct costs appearing in an agent’s
preference list (denoted as $k$) is upper-bounded by the number of distinct
costs in the instance as well as by the maximum length of an agent’s
preference list.

###### Theorem 1.5

The MINSUM problem admits an $O(k^{|\mathcal{A}|})$ time algorithm.

Size and $\mathcal{A}$-perfectness of the output: As stated earlier, size of a
matching plays a crucial role in real-world scenarios. In [6] the authors
mention that the administrators of the Scottish Foundation Allocation Scheme
were interested in larger size matchings at the expense of allowing blocking
pairs. In applications like school-choice [1] every child must find a school.
In case of matching sailors to billets in the US Navy [23, 20], every sailor
must be assigned to some billet, apart from some additional constraints. The
$\mathcal{A}$-perfectness requirement is imposed in the two-round school
choice problem studied in [10]. Round-1 is the standard stable matching
problem; whereas in round-2, their goal is to match all agents in a particular
set derived from the matching of round-1. We formalize this connection in
Section 2 where we generalize the stable extensions from [10]. In [10] they
consider a variant of $\sf MINSUM$ problem (Problem 33, Section 7) and state
that their problem is $\sf NP$-hard. However, they do not investigate the
problem in detail.

###  1.2 Related Work

Apart from [10], flexible quotas in the college admission setting are studied
in [19]. In their setting, no costs are involved but colleges may have ties in
the preference lists and flexible quotas are used for tie-breaking at the last
matched rank. In the student-project allocation setting, the problem of
minimizing the maximum and total deviation from the initial target is studied
in [8]. Flexibility in quotas also comes up when colleges have upper and
lower-quotas [4, 24, 12]. In the work by Biro et al. [4], colleges either
satisfy the lower-quotas or are closed.

A setting where courses make monetary transfers to students and have budget
constraints is studied in [16]. Funding constraints are studied in [2] in the
context of allocating student interns to the projects funded by supervisors. A
setting involving high-demand courses and scheduling constraints is studied in
[18] which assumes a fixed quota at courses. Course allocation involving
efficient assignment of students to highly-popular courses is treated with the
AI approach in [13]. Course bidding mechanisms for allocating seats
efficiently at high-demand courses are investigated in [22].

Organization of the paper:  In Section 2, we establish connection between $\sf
SMFQ$ setting and the generalized stable extension setting. We present our
algorithmic results for the $\sf{MINMAX}$ and $\sf MINSUM$ problems in Section
3. In Section 4, we present $\sf NP$-hardness and inapproximability results
for the $\sf MINSUM$ problem.

##  2 Stable extensions and SMFQ setting

In this section, we formally define the notion of stable extensions as defined
by Gajulapalli et al. [10] in a two round setting. Given an SM instance $G$
and a stable matching $M$ in $G$, a stable extension $M^{\prime}$ of $M$ is
defined as follows.

###### Definition 3

$M^{\prime}$ is a stable extension of $M$ if $M\subseteq M^{\prime}$ and
$M^{\prime}$ is stable w.r.t. preferences in $G$ and $M^{\prime}$ may violate
quotas of programs in $G$.

In the Type A1 setting [10] they consider the following problem: let $M$ be a
stable matching in $G$ computed in round-1. In round-2, the goal is to compute
a stable extension $M^{\prime}$ of $M$ which matches the maximum number of
unmatched agents in $M$ – they denote this as the largest stable extension
problem. Let $\mathcal{A}_{u}$ denote the set of agents unmatched in $M$. It
is well known by the Rural Hospital Theorem [21] that the set
$\mathcal{A}_{u}$ is independent of the stable matching. We note the following
about the stable extensions considered in [10].

  * •

If agent $a\in\mathcal{A}_{u}$ is matched to program $p$ in round-2, then $p$
must be fully-subscribed in $M$, otherwise $M$ is not stable. Thus, the total
number of agents matched to $p$ at the end of round-2 exceeds $q(p)$. In [10]
no restriction is imposed on the number of agents matched to programs in
round-2.

  * •

The stable matching $M$ in round-1 determines a unique subset of agents
$\mathcal{A}_{u}(M)\subseteq\mathcal{A}_{u}$ all of which can be matched in a
stable extension of $M$. Since increase in quotas is unrestricted in [10],
they match all the agents in $\mathcal{A}_{u}(M)$ to their top preferred
programs in a suitably modified graph. We generalize this by introducing costs
for programs in round-2. This allows quotas to be controlled in the second
round.

  * •

Since $\mathcal{A}_{u}(M)$ depends on the stable matching selected in round-1,
it is natural to ask: can we select a stable matching $M$ in round-1 which
allows maximum number of agents to be matched in an extension of $M$ in
round-2? We answer this question by proving in Lemma 1 that the
$\mathcal{A}$-optimal stable matching in $G$ achieves this guarantee. The
$\mathcal{A}$-optimal stable matching matches every agent to its most-
preferred stable partner [11].

For the sake of completeness, we present below the algorithm from [10] to
compute the set $\mathcal{A}_{u}(M)$. Their overall idea is to delete certain
edges from $E$ that cannot be matched in any stable extension of $M$. We use
the notion of barrier111 The notion of a barrier is similar to the notion of
threshold resident defined in the context of envy-free matchings [17]. as
defined in [10]. For program $p$, Barrier($p$) is the most-preferred matched
agent $a$ such that $a$ prefers $p$ over $M(a)$. For every program $p$, we
prune the preference list of $p$ by deleting the edges of the form
$(a^{\prime},p)$ such that $a^{\prime}$ is lower-preferred than Barrier($p$)
in $p$’s list. We denote this pruned graph after the for loop in line 5 as
$G_{M}$. The set $\mathcal{A}_{u}(M)$ is precisely the set of agents which are
not isolated in $G_{M}$.

1:Input: An SM instance $G$ and a stable matching $M$ in $G$.

2:Output: A set of agents $\mathcal{A}_{u}(M)$.

3:Let $\mathcal{A}_{u}$ be the set of agents unmatched in $M$

4:Let $E_{M}$ be the set of edges incident on an agent in $\mathcal{A}_{u}$

5:for every $p\in\mathcal{P}$ do

6: for every $a\in\mathcal{A}_{u}$ do

7: if $a<_{p}$ Barrier($p$) then

8: Delete edge $(a,p)$ from $E_{M}$

9:Let $\mathcal{A}_{u}(M)\subseteq\mathcal{A}_{u}$ such that every agent in
$\mathcal{A}_{u}(M)$ has at least one edge in $E_{M}$ incident on it.

10:Let $G_{M}=(\mathcal{A}_{u}(M)\cup\mathcal{P},E_{M})$

11:Return $\mathcal{A}_{u}(M)$

Algorithm 1 Algorithm to compute $\mathcal{A}_{u}(M)$ (adapted from [10])

###### Lemma 1

Let $G$ be the SM instance in round-1. Let ${M}$ be the $\mathcal{A}$-optimal
stable matching and let $M^{\prime}$ be any other stable matching in $G$.
Then, any agent that can be matched in a stable extension of $M^{\prime}$ can
also be matched in a stable extension of $M$. Thus,
$\mathcal{A}_{u}(M^{\prime})\subseteq\mathcal{A}_{u}(M)$.

###### Proof

Let $G_{M}$ and $G_{M^{\prime}}$ denote the pruned graphs after for loop in
line 5 in Algorithm 1 w.r.t. $M$ and $M^{\prime}$ respectively. Suppose for
the contradiction that, $|\mathcal{A}_{u}(M^{\prime})|>|\mathcal{A}_{u}(M)|$.
Then, there exists an agent
$a\in\mathcal{A}_{u}^{*}(M^{\prime})\setminus\mathcal{A}_{u}^{*}(M)$; that is,
agent $a$ has degree at least one in $G_{M^{\prime}}$ but degree $0$ in
$G_{M}$. Let $(a,p)\in G_{M^{\prime}}\setminus G_{M}$. Thus, there exists
agent $a^{\prime}>_{p}a$ such that $M(a^{\prime})<_{a^{\prime}}p$. But since
$(a,p)\in G^{\prime}$, we have $M^{\prime}(a^{\prime})\geq_{a^{\prime}}p$.
Since $M$ is $\mathcal{A}$-optimal, it implies that
$M(a)\geq_{a}M^{\prime}(a)$ for every agent $a$. This contradicts that
$M(a^{\prime})<_{a^{\prime}}M^{\prime}(a^{\prime})$. Hence,
$|\mathcal{A}_{u}(M)|\geq|\mathcal{A}_{u}({M^{\prime}})|$. ∎

In order to match maximum number of agents in round-2, by Lemma 1 we need to
select the $\mathcal{A}$-optimal matching in round-1. A stable matching $M$
selected in round-1 may admit multiple stable extensions. In Fig. 1, the
$\mathcal{A}$-optimal stable matching $N$ in $G$ admits two stable extensions,
namely $N_{E_{1}}=N\cup\\{(a_{3},p_{2}),(a_{5},p_{2})\\}$ and
$N_{E_{2}}=N\cup\\{(a_{3},p_{1}),(a_{5},p_{2})\\}$ and the algorithm in [10]
outputs $N_{E_{1}}$. It is natural to control the number of agents matched to
a program in round-2. We achieve this by defining the following two problems.

  1. 1.

For program $p$, let $d(p)$ denote the deviation of $p$, that is the
additional number of agents matched to $p$ beyond $q(p)$ in round-2. Let
$d^{*}=\max_{p\in\mathcal{P}}{d(p)}$. The goal is to compute a stable
extension of $M$ that minimizes $d^{*}$. This can be modeled as the
$\sf{MINMAX}$ problem on $G_{M}$ (defined above) where every program has unit
cost.

  2. 2.

Let $c(p)$ denote the cost of matching an agent to a program in round-2. The
goal is to compute a stable extension of $M$ where the total cost of matching
agents in round-2 is minimized. This is exactly the $\sf MINSUM$ problem on
$G_{M}$ with the costs $c(p)$.

Thus, our results in the ${\sf SMFQ}$ setting generalize the stable extensions
problem.

##  3 Algorithmic Results in the $\sf SMFQ$ setting

In this section, we present our algorithmic results for the $\sf SMFQ$
setting. In Section 3.1, we present an exact exponential algorithm for $\sf
MINSUM$ when the number of distinct costs in the instance is small. In Section
3.2, we define a natural lower-bound on the optimal cost and present two
$\ell_{p}$-approximation algorithms for $\sf MINSUM$, where $\ell_{p}$ denotes
the length of the longest preference list of any program. In Section 3.3, we
present a polynomial time algorithm for the $\sf{MINMAX}$ problem. We use this
result to derive a lower-bound for the $\sf MINSUM$ problem that leads to a
practically better approximation guarantee of $|\mathcal{P}|$.

###  3.1 Exact exponential algorithm for $\sf MINSUM$

In this section we present an exact exponential algorithm for $\sf MINSUM$.
Let $H$ be an $\sf SMFQ$ instance. Let $t$ be the number of distinct costs in
$H$ and $k$ be the number of distinct costs appearing in an agent’s preference
list in $H$. Then $k\leq t$. Also $k\leq\ell_{a}$ where $\ell_{a}$ is the
maximum length of an agent’s preference list. Our algorithm (Algorithm 2)
considers every possible $|\mathcal{A}|$-tuple of costs $\langle
c^{1},\ldots,c^{|\mathcal{A}|}\rangle$ such that each $c^{i}$ is one of the
distinct costs appearing for agent $a_{i}$ Thus, there are at most
$k^{|\mathcal{A}|}$ tuples. For each tuple, the algorithm constructs a sub-
graph $H^{\prime}$ such that every agent $a_{i}$ has edges incident to
programs with cost exactly $c^{i}$. If $p$ is the highest preferred program
neighbouring agent $a$ in $H^{\prime}$ then any program $p^{\prime}>_{a}p$ in
the graph $H$ cannot be matched with any agent $a^{\prime}<_{p^{\prime}}a$,
otherwise it creates blocking pair $(a,p)$. The algorithm prunes the graph
$H^{\prime}$ to remove such edges $(a^{\prime},p^{\prime})$ repeatedly. If no
agent is isolated after the pruning then the algorithm computes $M^{\prime}$
by matching every agent to the top-choice program in this pruned graph. The
algorithm picks a least-cost matching $M$ among the matchings $M^{\prime}$ and
returns $M$.

Correctness.  The algorithm computes at least one $\mathcal{A}$-perfect
matching. This is true because the tuple that consists of the cost of the top-
choice program of every agent leads to an $\mathcal{A}$-perfect matching.

1:$M=\emptyset,cost=\infty$

2:for every tuple $\langle c^{1},\ldots,c^{|\mathcal{A}|}\rangle$ do

3: $H^{\prime}=\\{(a_{i},p)\mid a_{i}\in\mathcal{A},p$ has cost $c^{i}\\}$

4: let change = 1

5: while every agent has degree $\geq 1$ and change = 1 do

6: let change = 0

7: for every $a_{i}\in\mathcal{A}$ do

8: let $p$ be the top-preferred program such that $(a_{i},p)\in H^{\prime}$

9: for every $p^{\prime}>_{a_{i}}p$ do

10: for every $a<_{p^{\prime}}a_{i}$ do

11: Delete $(a,p^{\prime})$ and let change = 1

12: if no agent is isolated in $H^{\prime}$ then

13: $M^{\prime}=\\{(a,p)\mid a\in\mathcal{A},p$ is the top-choice program of
$a$ in $H^{\prime}$}

14: if cost of $M^{\prime}\leq cost$ then

15: $M=M^{\prime},cost=$ cost of $M^{\prime}$

16:return $M$

Algorithm 2 $O(k^{|\mathcal{A}|})$ algorithm for $\sf MINSUM$

###### Lemma 2

The matching $M$ computed by Algorithm 2 is stable.

###### Proof

The matching $M$ is actually matching $M^{\prime}$ computed for some tuple.
Thus, it is enough to show that $M^{\prime}$ computed for an arbitrary tuple
is stable.

Suppose $M^{\prime}$ is not stable, then there exists agents $a,a^{\prime}$
such that $M^{\prime}(a)<_{a}p^{\prime}$ and $(a^{\prime},p^{\prime})\in
M^{\prime}$ and $a^{\prime}<_{p^{\prime}}a$. If $(a,p^{\prime})\in H^{\prime}$
at line 13 then $M^{\prime}(a)\geq_{a}p^{\prime}$, a contradiction. Hence,
$(a,p^{\prime})\notin H^{\prime}$. If $(a,p^{\prime})\notin H^{\prime}$ after
line 3 then note that edge $(a^{\prime},p^{\prime})$ is deleted at line 11.
Otherwise, $(a,p^{\prime})$ was deleted in some iteration of the edge deletion
loop. This implies that there exists $a^{\prime\prime}>_{p^{\prime}}a$ that
triggered this deletion. But, then we have that
$a^{\prime\prime}>_{p^{\prime}}a^{\prime}$, implying that
$(a^{\prime},p^{\prime})$ is also deleted. Thus, in both the cases,
$(a^{\prime},p^{\prime})\notin H^{\prime}$ and hence
$(a^{\prime},p^{\prime})\notin M^{\prime}$. This contradicts the assumption
that $(a^{\prime},p^{\prime})\in M^{\prime}$ and hence completes the proof. ∎

Thus the algorithm computes at least one $\mathcal{A}$-perfect, stable
matching. We now show that the algorithm computes an optimal matching.

###### Lemma 3

Let $M$ be an $\mathcal{A}$-perfect stable matching and $\mathcal{T}$ be the
tuple corresponding to $M$. Then no edge in $M$ is deleted when Algorithm 2
processes $\mathcal{T}$.

###### Proof

Suppose for the sake of contradiction that an edge in $M$ is deleted when
Algorithm 2 processes the tuple $\mathcal{T}$. Let $(a_{1},p_{1})$ be the
first edge in $M$ that gets deleted during the course of the algorithm. The
edge $(a_{1},p_{1})$ is in $H^{\prime}$ after line 3 since $p_{1}$ has the
same cost as given by the tuple $\mathcal{T}$. This implies that the edge
$(a_{1},p_{1})$ is deleted while pruning the instance. Suppose agent $a_{2}$
caused the deletion of edge $(a_{1},p_{1})$ at time $t$. Let $M(a_{2})=p_{2}$.
Then it is clear that either $p_{2}=p_{1}$ or $p_{2}>_{a_{2}}p_{1}$, otherwise
$M$ is not stable. But since $a_{2}$ triggered the deletion of
$(a_{1},p_{1})$, the top choice program adjacent to $a_{2}$ in $H^{\prime}$ at
time $t$ is less preferred than $p_{1}$. Again note that $(a_{2},p_{2})\in
H^{\prime}$ after line 3 hence $(a_{2},p_{2})$ must have been deleted at time
earlier than $t$. This contradicts the assumption that $(a_{1},p_{1})$ is the
first edge in $M$ that gets deleted. This completes the proof. ∎

Let ${\sf OPT}$ is an optimal matching and let $\mathcal{T}_{{\sf OPT}}$ be
the tuple corresponding to ${\sf OPT}$. When algorithm processes
$\mathcal{T}_{{\sf OPT}}$, by Lemma 3, no edge in ${\sf OPT}$ is deleted.
Thus, no agent gets isolated and the algorithm computes $M^{\prime}$. Since
Algorithm 2 returns the matching with cost at most the cost of $M^{\prime}$,
it implies that it returns an $\mathcal{A}$-perfect stable matching with
minimum total cost.

Running Time.  For each of the $O(k^{|\mathcal{A}|})$ tuples, the algorithm
computes the graph $H^{\prime}$, deletes $O(m)$ edges where $m$ is the number
of edges in $H$ and may compute matching $M^{\prime}$. Thus the Algorithm 2
runs in time $O(k^{|\mathcal{A}|}\cdot poly(m))$.

This establishes Theorem 1.5.

###  3.2 $\ell_{p}$-approximation for $\sf MINSUM$

In this section we present two linear time algorithms for the $\sf MINSUM$
problem with approximation guarantee of $\ell_{p}$. Let $p^{*}_{a}$ denote the
minimum cost program in the preference list of agent $a$. If there is more
than one program with the same minimum cost, we let $p^{*}_{a}$ be the most-
preferred amongst these programs.

Description of the first algorithm:  Given an $\sf SMFQ$ instance $H$, our
algorithm (Algorithm 3) starts by matching every agent $a$ to $p^{*}_{a}$.
Note that such a matching is $\mathcal{A}$-perfect and min-cost but not
necessarily stable. Now the algorithm considers programs in an arbitrary
order. For program $p$, we consider agents in the reverse preference list
ordering of $p$. If there exists agent $a\notin M(p)$ such that $p>_{a}M(a)$
and there exists $a^{\prime}\in M(p)$ such that $a^{\prime}<_{p}a$, then
$(a,p)$ forms a blocking pair. We resolve this by promoting $a$ from $M(a)$ to
$p$. The algorithm stops when we have considered every program.

1:let $M=\\{(a,p)|\ \ a\in\mathcal{A}$ and $p=p^{*}_{a}\\}$

2:for every program ${p}$ do

3: for $a$ in reverse preference list ordering of $p$ do

4: if there exists $a^{\prime}\in M(p)$ such that $a>_{p}a^{\prime}$ and
$p>_{a}M(a)$ then

5: $M=M\setminus\\{(a,M(a))\\}\cup\\{(a,p)\\}$

6:return $M$

Algorithm 3 First $\ell_{p}$-approximation algorithm for $\sf MINSUM$

Note that in Algorithm 3 an agent can only get promoted in the loop (line 5)
of the algorithm. Further, program $p$ is assigned agents only when it is
being considered in the for loop (line 2). Finally, if program $p$ is assigned
at least one agent in the final output matching, then $p=p^{*}_{a}$ for some
agent $a\in\mathcal{A}$.

Analysis: It is clear that the matching computed by Algorithm 3 is
$\mathcal{A}$-perfect. We show the correctness and the approximation guarantee
below.

###### Lemma 4

The matching $M$ output by Algorithm 3 is stable.

###### Proof

We show that no agent participates in a blocking pair w.r.t. $M$. Assume for
contradiction, that $(a,p)$ blocks $M$. Then $p>_{a}M(a)$ and there exists an
agent $a^{\prime}\in M(p)$ such that $a^{\prime}<_{p}a$. Consider the
iteration of the for loop in line 2 when $p$ was considered. Either
$a^{\prime}$ was already matched to $p$ (before this iteration) or
$a^{\prime}$ is assigned to $p$ in this iteration. Note that $p$ prefers $a$
over $a^{\prime}$ and the agents are considered in reverse order of $p$’s
preferences. Thus if $a$ was matched in that iteration to a lower-preferred
program $p^{\prime\prime}$ than $p$, then $a$ must be promoted to $p$.
Otherwise, $a$ was already matched in that iteration to a better-preferred
program. Since agents can only get promoted in subsequent iterations, it
contradicts that at the end of the algorithm, agent $a$ prefers $p$ to $M(a)$.
This completes the proof of stability. ∎

###### Lemma 5

The matching $M$ output by Algorithm 3 is an $\ell_{p}$-approximation.

###### Proof

Let $c({\sf OPT})$ and $c(M)$ be the cost of matching ${\sf OPT}$ and $M$
respectively. It is easy to see that

$c({\sf OPT})\geq\sum\limits_{a\in\mathcal{A}}{c(p_{a}^{*})}$ (1)

In the matching $M$, some agents are matched to their least cost program (call
them $\mathcal{A}_{1}$), whereas some agents get promoted (call them
$\mathcal{A}_{2}$). However, as noted earlier, if a program $p$ is assigned
agents in $M$ then $p=p^{*}_{a}$ for some agent $a$. Thus for agent
$a\in\mathcal{A}_{2}$, we charge the cost of some other least cost program
$p^{*}_{a^{\prime}}$. Since a program can be charged at most $\ell_{p}-1$
times by agents in $\mathcal{A}_{2}$, we have

$\displaystyle c(M)$ $\displaystyle=$
$\displaystyle\sum\limits_{a\in\mathcal{A}_{1}}{c(p^{*}_{a})}+\sum\limits_{a\in\mathcal{A}_{2}}{c(M(a))}\leq\sum\limits_{a\in\mathcal{A}}{c(p^{*}_{a})}+\sum\limits_{a\in\mathcal{A}}{(\ell_{p}-1)\cdot
c(p^{*}_{a})}\leq\ell_{p}\cdot c({\sf OPT})$

∎

This establishes Theorem 1.4 (I).

Next, we present another algorithm using the lower-bound in Eq. 1 with
approximation guarantee of $\ell_{p}$.

Description of the second algorithm (ALG):  Given an $\sf SMFQ$ instance $H$,
we construct a subset $\mathcal{P}^{\prime}$ of $\mathcal{P}$ such that
$p\in\mathcal{P}^{\prime}$ iff $p=p^{*}_{a}$ for some agent $a$. Our algorithm
now matches every agent $a$ to the most-preferred program in
$\mathcal{P}^{\prime}$.

Analysis of ALG: It is clear that the matching computed by ALG is
$\mathcal{A}$-perfect. Let $M$ be the output of ALG and ${\sf OPT}$ be an
optimal matching. Let $c({\sf OPT})$ and $c(M)$ be the cost of matching ${\sf
OPT}$ and $M$ respectively. The lower-bound on $c({\sf OPT})$ in Eq. 1 is
exactly the same. We show the correctness and the approximation guarantee of
ALG via Lemma 6 and Lemma 7.

###### Lemma 6

The output $M$ of ALG is stable.

###### Proof

We show that no agent participates in a blocking pair w.r.t. $M$. Suppose
$(a,p)$ blocks $M$. Then it implies that $p>_{a}M(a)$ and there exists an
agent $a^{\prime}\in M(p)$ such that $a^{\prime}<_{p}a$. Since ALG assigns
agents to programs in $\mathcal{P}^{\prime}$ only, it implies that
$p\in\mathcal{P}^{\prime}$. However, $M(a)$ is the most-preferred program in
$\mathcal{P}^{\prime}$ and hence $M(a)\geq_{a}p$. Thus, the claimed blocking
pair does not exist. ∎

###### Lemma 7

The output $M$ of ALG is an $\ell_{p}$-approximation.

###### Proof

In the matching $M$, agent $a$ is either matched to $p^{*}_{a}$ or
$p^{*}_{a^{\prime}}$ for some other agent $a^{\prime}$. This is determined by
the relative ordering of $p^{*}_{a}$ and $p^{*}_{a^{\prime}}$ in the
preference list of $a$. We partition the agents as
$\mathcal{A}=\mathcal{A}_{1}\cup\mathcal{A}_{2}$, where $\mathcal{A}_{1}$ is
the set of agents matched to their own least cost program, that is,
$a\in\mathcal{A}_{1}$ iff $M(a)=p^{*}_{a}$. We define
$\mathcal{A}_{2}=\mathcal{A}\setminus\mathcal{A}_{1}$. We can write the cost
of $M$ as follows:

$c(M)=\sum\limits_{a\in\mathcal{A}_{1}}{c(p^{*}_{a})}+\sum\limits_{a\in\mathcal{A}_{2}}{c(M(a))}$

By similar arguments as in Lemma 5, we get the $\ell_{p}$ approximation
guarantee. ∎

####  3.2.1 Comparing the two $\ell_{p}$ approximation algroithms for $\sf
MINSUM$

We present following instances which illustrate that neither of the two
algorithms is strictly better than the other.

###### Example 1

Let $\mathcal{A}=\\{a_{1},a_{2},\ldots,a_{n}\\}$,
$\mathcal{P}=\\{p_{1},p_{2}\\}$, $c(p_{1})=1,c(p_{2})=\alpha$ where $\alpha$
is some large positive constant. The agents $a_{1},\ldots,a_{n-1}$ have the
same preference list $p_{2}$ followed by $p_{1}$. Whereas agent $a_{n}$ has
only $p_{2}$ in its preference list. The preferences of the programs are as
given below.

$\displaystyle p_{1}$ $\displaystyle:a_{1},\ a_{2},\ \ldots,\ a_{n-1}$
$\displaystyle p_{2}$ $\displaystyle:a_{n},\ a_{n-1},\ a_{n-2},\ \ldots,\
a_{1}$

Here, ALG outputs $M_{1}$ of cost $n\cdot\alpha$ where
$M_{1}=\\{(a_{1},p_{2}),\ldots,(a_{n},p_{2})\\}$. In contrast, Algorithm 3
outputs $M_{2}=\\{(a_{1},p_{1}),\ldots,(a_{n-1},p_{1}),(a_{n},p_{2})\\}$ whose
cost is $n-1+\alpha$. Clearly, Algorithm 3 outperforms ALG in this case and in
fact $M_{2}$ is optimal for the instance.

###### Example 2

Let $\mathcal{A}=\\{a_{1},a_{2},\ldots,a_{n}\\}$,
$\mathcal{P}=\\{p_{1},p_{2},p_{3}\\}$, $c(p_{1})=1,c(p_{2})=2,c(p_{3})=\alpha$
where $\alpha$ is some large positive constant. The preferences of agents
$a_{1},\ldots,a_{n-2}$ are $p_{2}$ followed by $p_{3}$ followed by $p_{1}$.
The preference list of $a_{n-1}$ contains only $p_{2}$ and the preference list
of $a_{n}$ contains only $p_{3}$. The preferences of programs are as shown
below.

$\displaystyle p_{1}$ $\displaystyle:a_{1},\ a_{2},\ \ldots,a_{n-2}$
$\displaystyle p_{2}$ $\displaystyle:a_{n-1},\ a_{1},\ a_{2},\ \ldots,a_{n-2}$
$\displaystyle p_{3}$ $\displaystyle:a_{1},\ \ldots,\ a_{n-2},\ a_{n}$

Here, ALG outputs
$M_{1}=\\{(a_{1},p_{2}),\ldots,(a_{n-1},p_{2}),(a_{n},p_{3})\\}$ whose cost is
$2\cdot(n-1)+\alpha$. In contrast, Algorithm 3 outputs $M_{2}$ of cost
$2+(n-1)\cdot\alpha$ where
$M_{2}=\\{(a_{1},p_{3}),\ldots,(a_{n-2},p_{3}),(a_{n-1},p_{2}),(a_{n},p_{3})\\}$.
In this instance ALG outperforms Algorithm 3 and it can be verified that
$M_{1}$ is the optimal matching.

Remark on the lower-bound.  We note that although $\ell_{p}$ seems a weak
approximation guarantee, this is the best bound one can obtain via the lower-
bound in Eq. 1. We show a family of instances where lower-bound is $1$ and
optimal cost is $\ell_{p}$. In Fig. 2 we have $n$ agents and $3$ programs with
master list ordering on agents and programs. We have $\ell_{p}=n$ and
$c(p_{0})=0,c(p_{1})=1$ and $c(p_{2})=n$ (denoted in brackets). Then the
lower-bound on optimal solution of $\sf MINSUM$ is $1$ and the optimal cost is
$n$.

$\displaystyle 1\leq i\leq n-1,\ \ \ a_{i}$ $\displaystyle:p_{1},p_{0}$
$\displaystyle a_{n}$ $\displaystyle:p_{1},p_{2}$

$\displaystyle(0)\ p_{0}$ $\displaystyle:a_{1},a_{2},\ldots,a_{n-1}$
$\displaystyle(1)\ p_{1}$ $\displaystyle:a_{1},a_{2},\ldots,a_{n-1},a_{n}$
$\displaystyle(n)\ p_{2}$ $\displaystyle:a_{n}$

Figure 2: A family of instances with optimal cost exactly $\ell_{p}$ times the
lower-bound. There are two optimal matchings of cost $\ell_{p}=n$: ${\sf
OPT}_{1}=\\{(a_{1},p_{0}),\ldots,(a_{n-1},p_{0}),(a_{n},p_{2})\\}$ and ${\sf
OPT}_{2}=\\{(a_{1},p_{1}),\ldots,(a_{n},p_{1})\\}$.

###  3.3 $\sf{MINMAX}$ problem and a $|\mathcal{P}|$-approximation for $\sf
MINSUM$

In this section we present a simple polynomial time algorithm for the
$\sf{MINMAX}$ problem. We then prove that the optimal solution to the
$\sf{MINMAX}$ problem serves as a lower-bound on the optimal solution for the
$\sf MINSUM$ problem. Using this lower-bound we design a
$|\mathcal{P}|$-approximation for the $\sf MINSUM$ problem.

####  3.3.1 Polynomial time algorithm for the $\sf{MINMAX}$ problem.

Our algorithm for the $\sf{MINMAX}$ problem is based on the following
observations:

  * •

Let $H$ be an $\sf SMFQ$ instance and $M^{*}$ be the optimal solution for the
$\sf{MINMAX}$ problem on $H$. Let
$t^{*}=max_{p\in\mathcal{P}}\\{c(p)\cdot|M^{*}(p)|\\}$. Then there exists an
instance $G_{t^{*}}$ of the SM problem with quotas of programs as follows: for
each $p\in\mathcal{P}$,
$q(p)=\left\lfloor\frac{t^{*}}{c(p)}\right\rfloor\geq|M^{*}(p)|$. The instance
$G_{t^{*}}$ admits an $\mathcal{A}$-perfect stable matching. This follows from
the fact that $M^{*}$ is an $\mathcal{A}$-perfect matching in which every
program is assigned at most $q(p)$ many agents.

  * •

For any $t<t^{*}$, consider the instance $G_{t}$ of SM problem with
$q(p)=\left\lfloor\frac{t}{c(p)}\right\rfloor$. The instance $G_{t}$ does not
admit an $\mathcal{A}$-perfect stable matching. Otherwise this contradicts the
optimality of $M^{*}$.

  * •

The optimal value $t^{*}$ lies in the range $0$ to $|\mathcal{A}|\cdot c^{*}$,
where $c^{*}$ denotes the maximum cost of any program in the input instance
$H$.

  * •

For some $t$, if $G_{t}$ admits an $\mathcal{A}$-perfect stable matching then
for any $t^{\prime}>t$, $G_{t^{\prime}}$ admits an $\mathcal{A}$-perfect
stable matching.

Using the above observations the algorithm for the $\sf{MINMAX}$ problem is
immediate. We binary search for the optimal value of $t$ in the range
$[0,|\mathcal{A}|\cdot c^{*}]$. For a particular value of $t$ we construct the
SM instance $G_{t}$ by setting appropriate quotas. If the stable matching in
$G_{t}$ is not $\mathcal{A}$-perfect, then we search in the upper-range.
Otherwise, we check if $G_{t-1}$ admits an $\mathcal{A}$-perfect stable
matching. If not, we return $t$ otherwise, we search for the optimal in the
lower-range. The algorithm requires $O(\log{(|\mathcal{A}|\cdot c^{*}))}$ many
iterations where each iteration computes at most two stable matchings using
the linear time Gale and Shapley algorithm [11]. Thus the overall running time
is polynomial in the input size. This establishes Theorem 1.1.

####  3.3.2 $|\mathcal{P}|$-approximation algorithm for $\sf MINSUM$.

We now prove that the optimal matching $M^{*}$ for the $\sf{MINMAX}$ problem
is a $|\mathcal{P}|$-approximation for the $\sf MINSUM$ problem.

###### Lemma 8

The optimal solution for the $\sf{MINMAX}$ problem is a
$|\mathcal{P}|$-approximation for the $\sf MINSUM$ problem.

###### Proof

Let $H$ be an $\sf SMFQ$ instance and let $M^{*}$ be the optimal matching for
the $\sf{MINMAX}$ problem on $H$. For the same instance $H$, let $N^{*}$ be
the optimal matching for the $\sf MINSUM$ problem. Let us define $t^{*}$ and
$y^{*}$ as follows:

$\displaystyle t^{*}=\max_{p\in\mathcal{P}}\\{c(p)\cdot|M^{*}(p)|\\}\hskip
57.81621pty^{*}=\sum_{p\in\mathcal{P}}\left(c(p)\cdot|N^{*}(p)|\ \right)$

We first observe that $y^{*}\geq t^{*}$. This is true because $N^{*}$ is an
$\mathcal{A}$-perfect stable matching in $H$. Furthermore, since costs of all
programs are non-negative,
$\max_{p\in\mathcal{P}}\\{c(p)\cdot|N^{*}(p)|\\}\leq y^{*}$. Therefore if
$y^{*}<t^{*}$, it contradicts the optimality of $M^{*}$ for the $\sf{MINMAX}$
problem. To prove the approximation guarantee, we note that since $t^{*}$
denotes the maximum cost incurred at any program in $M^{*}$, the total cost of
$M^{*}$ is upper bounded by $|\mathcal{P}|\cdot t^{*}\leq|\mathcal{P}|\cdot
y^{*}$. ∎

This establishes Theorem 1.4 (II).

##  4 Hardness results

In this section, we present the $\sf NP$-hardness hardness result (Theorem
1.2) and the inapproximability result (Theorem 1.3) for the $\sf MINSUM$
problem.

###  4.1 $\sf NP$-hardness of $\sf MINSUM$

We show that the $\sf MINSUM$ problem is $\sf NP$-hard even under severe
restrictions on the instance. In particular we show that the hardness holds
even when all agents have a preference list of a constant length $f$ and there
is a master list ordering on agents and programs. To show the $\sf
NP$-hardness of $\sf MINSUM$ we use the Set Cover ($\sf{SC}$) instance where
every element occurs in exactly $f$ sets. Minimum vertex cover on $f$-uniform
hypergraphs is known to be $\sf NP$-complete and $\sf{SC}$ problem where every
element occurs in exactly $f$ sets is equivalent to it [7].

Reduction: Let $\langle S,E,k\rangle$ be an instance of $\sf{SC}$ such that
every element in $E$ occurs in exactly $f$ sets. Let $m=|S|,n=|E|$. We
construct an instance $H$ of $\sf SMFQ$ as follows. For every set $s_{i}\in
S$, we have a set-agent $a_{i}$ and a set-program $p_{i}$. For every element
$e_{h}\in E$, we have an element-agent $a_{h}^{\prime}$. We also have a
program $p$ and $f-2$ programs $p^{1},\ldots,p^{f-2}$. Thus in the instance
$H$ we have $m+n$ agents and $m+f-1$ programs. Let $E_{i}$ denote the set of
elements in the $s_{i}$. The element-agents corresponding to $E_{i}$ in $H$
are denoted by $\mathcal{A}_{i}^{\prime}$.

Preferences: The preference lists of agents and programs are shown in Fig. 3.
Every set-agent $a_{i}$ has $f$ programs in its preference list - the set-
program $p_{i}$ followed by the program $p$ followed by the programs
$p^{1},\ldots,p^{f-2}$ in that order. Every element-agent $a^{\prime}_{j}$ has
the $f$ set-programs corresponding to the sets that contain it in an arbitrary
fixed order. Every set-program $p_{i}$ has its set-agent $a_{i}$ as its top-
preferred agent followed by the agents in $\mathcal{A}_{i}$ in an arbitrary
fixed order. The program $p$ and each program $p^{1},\ldots,p^{f-2}$ has the
set-agents as $a_{1},\ldots,a_{n}$ in an arbitrary fixed order. It is clear
that every agent has a preference list of length $f$.

Costs: The costs for program $p_{i}$ for $1\leq i\leq n$ and $p^{j}$ for
$1\leq j\leq f-2$ is $1$ and that for the program $p$ is $0$. Thus, the
instance has two distinct costs.

$\mathcal{A}$ |  $\mathcal{P}$
---|---
$1\leq i\leq m,\ a_{i}:p_{i},p,p^{1},\ldots,p^{f-2}$ |  $1\leq i\leq m,\ p_{i}:a_{i},\mathcal{A}_{i}^{\prime}$
$1\leq j\leq n,\ a_{j}^{\prime}:p_{j1},\ldots,p_{jf}$ |  $p:a_{1},\ldots,a_{m}$
|  $1\leq t\leq f\text{-}2,p^{t}:a_{1},\ldots,a_{m}$
Figure 3: Reduced instance $H$ of $\sf SMFQ$ from instance $\langle
S,E,k\rangle$ of $\sf{SC}$

###### Claim

If $\langle S,E,k\rangle$ is a yes instance, then $H$ admits an
$\mathcal{A}$-perfect stable matching of cost at most $n+k$.

###### Proof

Let $X\subseteq S$ be the set cover size at most $k$. Using $X$, we construct
an $\mathcal{A}$-perfect matching $M$ in $H$ and show that $M$ is stable. We
then show that the cost of $M$ is bounded. For every set $s_{i}\notin X$, we
match the corresponding set-agent $a_{i}$ to the program $p$, that is,
$M(a_{i})=p$. For every set $s_{i}\in X$, we match the corresponding set-agent
$a_{i}$ to the program $p_{i}$, that is, $M(a_{i})=p_{i}$. Since $X$ is a set
cover, for every element $e_{j}\in E$, at least one of the sets it occurs in
is in $X$. Thus, for every element-agent $a^{\prime}_{j}$, we match it to the
program $p_{jt}$ corresponding to the set in $X$ (in case more than one set
containing $e_{j}$ are in $X$, then we match it to the program which is
highest preferred amongst them). It is clear that $M$ is
$\mathcal{A}$-perfect.

To prove that $M$ is stable, we show that no agent participates in a blocking
pair. First observe that, an agent $a_{i}$ corresponding to $s_{i}\in X$ is
matched to its top-choice program. Hence such agents do not participate in
blocking pairs. Now, for all agents $a_{i}$ such that $s_{i}\notin X$, these
agents are matched to $p$. However, the corresponding program $p_{i}$ remains
closed. Finally, every element-agent that is not matched to its top-choice
programs has all such top-choice programs closed. Thus the matching is stable.

We compute the cost of matching $M$ from the agent side. Each element-agent is
matched to some program $p_{i}$ and costs $1$ each. At most $k$ set-agents
matched to their corresponding set-program $p_{i}$ each costs $1$ and the
$m-k$ set-agents are matched to program $p$ that incur the cost $0$ each.
Hence the cost of the matching is at most $n+k$. ∎

###### Claim

If $H$ admits an $\mathcal{A}$-perfect stable matching with cost at most
$n+k$, then $\langle S,E,k\rangle$ is a yes instance.

###### Proof

First we prove that program $p$ must take at least $m-k$ set-agents - Since
the matching is $\mathcal{A}$-perfect, every matched element-agent contributes
a cost of at least $1$ each, every set-agent not matched to $p$ contributes a
cost of $1$ each thus if program $p$ takes less than $m-k$ set-agents then the
cost of any such $\mathcal{A}$-perfect stable matching is at least $n+k+1$,
which is a contradiction. Thus, at least $m-k$ set-agents must be matched to
program $p$.

Let $X$ be the set of sets $s_{i}$ such that $a_{i}$ is matched to $p_{i}$.
Then, $|X|\leq k$. Since, the matching is stable, every program $p_{i}$ such
that $s_{i}\notin X$ must be closed (since $a_{i}$ is either matched to $p$ or
$p^{j}$). We now prove that $X$ is a set cover. Suppose not, then there exists
at least one element, say $e_{j}$ such that no set containing $e_{j}$ is in
$X$, implying that all the programs $p_{jt}$ are closed. It means that
element-agent $a_{t}^{\prime}$ is unmatched. This implies that the matching is
not $\mathcal{A}$-perfect, which is a contradiction. Hence $X$ must be a set
cover. Since $|X|\leq k$, thus $\langle S,E,k\rangle$ is a yes instance. ∎

We remark that the $\sf NP$-hardness result holds even when there is a master
list ordering on agents and programs as follows:

$(a_{1},\ldots,a_{m},a_{1}^{\prime},\ldots,a_{n}^{\prime})$,
$(p_{1},\ldots,p_{m},p,p^{1},\ldots,p^{f-2})$.

This establishes Theorem 1.2.

###  4.2 Inapproximability of $\sf MINSUM$

Let $G=(V,E)$ be an instance of minimum vertex cover ($\sf{MVC}$) problem. Let
$n=|V|$ and $m=|E|$. We construct an instance of $\sf SMFQ$ as follows.

Reduction:  For every vertex $u_{i}$, we have $m$ vertex-agents
$a_{i}^{1},\ldots a_{i}^{m}$ and $2$ vertex-programs $p_{i}$ and
$p_{i}^{\prime}$. For every edge $e_{j}$, we have one edge-agent
$a^{\prime}_{j}$. We have an additional program $p$. Thus, we have $m+mn$
agents and $2n+1$ programs.

Preferences:  Preference lists of programs and agents are shown in Fig. 4. The
set of vertex-programs $p_{j1}^{\prime}$ and $p_{j2}^{\prime}$ corresponding
to the end-points $u_{j1}$ and $u_{j2}$ of edge $e_{j}$ is denoted by
$\mathcal{P}_{j}^{\prime}$. The set of edge-agents $a_{j}^{\prime}$
corresponding to the edges incident on vertex $u_{i}$ is denoted by
$\mathcal{A}^{\prime}_{i}$. Each vertex-agent $a_{i}^{t},1\leq t\leq m$ has
the program $p_{i}$ followed by $p_{i}^{\prime}$ followed by $p$. Each edge-
agent $a_{j}^{\prime}$ has the two programs in $\mathcal{P}_{j}^{\prime}$ in
an arbitrary order. Each vertex-program $p_{i}$ prefers the $m$ vertex-agents
$a_{i}^{1},\ldots,a_{i}^{m}$ in that order. Each vertex-program
$p_{i}^{\prime}$ prefers the $m$ vertex-agents $a_{i}^{1},\ldots,a_{i}^{m}$ in
that order, followed by the edge-agents $\mathcal{A}^{\prime}_{i}$. Program
$p$ prefers the $mn$ vertex-agents in an arbitrary but fixed order.

Costs:  The cost of each vertex-program $p_{i}$ is $3$, that of each vertex-
program $p_{i}^{\prime}$ is $2n$ and that of the program $p$ is $0$.

$\mathcal{A}$ |  $\mathcal{P}$
---|---
$\forall 1\leq i\leq n,\ 1\leq j\leq m,\ \ \ a_{i}^{j}:p_{i},p_{i}^{\prime},p$ |  $\forall 1\leq i\leq n,\ \ \ p_{i}:a_{i}^{1},\ldots,a_{i}^{m}$
|  $\forall 1\leq i\leq n,\ \ \
p_{i}^{\prime}:a_{i}^{1},\ldots,a_{i}^{m},\mathcal{A}_{i}^{\prime}$
$1\leq j\leq m,\ \ \ a_{j}^{\prime}:\mathcal{P}_{j}^{\prime}$ |  $1\leq i\leq n,1\leq t\leq m,\ \ \ p:a_{i}^{t}$
Figure 4: Reduced instance $H$ of $\sf SMFQ$ from instance $G$ of $\sf{MVC}$

###### Lemma 9

If an optimal vertex cover in $G$ is of size at most
$(\frac{2}{3}+\epsilon)\cdot n$ then in $H$, there exists an
$\mathcal{A}$-perfect stable matching $M$ with cost at most $(4+3\epsilon)mn$.

###### Proof

Let $V^{\prime}$ be the vertex cover of $G$ of size at most
$(\frac{2}{3}+\epsilon)\cdot n$. If $u_{i}\notin V^{\prime}$, we match all the
$m$ $s_{i}^{t}$ agents to the program $p$ at cost $0$. If $u_{i}\in
V^{\prime}$, we match all the $m$ $s_{i}^{t}$-type agents to the program
$p_{i}$. This contributes the cost of at most
$m\cdot(\frac{2}{3}+\epsilon)\cdot n\cdot 3=mn(2+3\epsilon)$. We then prune
the preference list of every edge-agent $a_{j}^{\prime}$ by deleting the
programs $p_{i}^{\prime}$ corresponding to the end-point $u_{i}$ such that
$u_{i}\notin V^{\prime}$. Since $V^{\prime}$ is a vertex cover, it is
guaranteed that every edge is covered and hence every edge-agent
$a_{j}^{\prime}$ has a non-empty list $\mathcal{P}_{j}^{\prime}$ after
pruning. Every edge-agent $a_{j}^{\prime}$ is then matched to the top-
preferred program $p_{i}^{\prime}$ in the pruned list $\mathcal{P}_{j}$. This
contributes a cost of $2mn$ incurred by the edge-agents.

Thus, the total cost of this matching is at most
$(2+2+3\epsilon)mn=(4+3\epsilon)mn$. It is easy to see that $M$ is
$\mathcal{A}$-perfect and is stable since no agent participates in a blocking
pair. ∎

###### Lemma 10

If the optimal vertex cover in $G$ has size greater than
$(\frac{8}{9}-\epsilon)\cdot n$ then in $H$, any $\mathcal{A}$-perfect stable
matching $M$ has cost greater than $(\frac{14}{3}-3\epsilon)mn$.

###### Proof

We prove the contra-positive i.e. if there exists an $\mathcal{A}$-perfect
stable matching within cost $mn(\frac{14}{3}-3\epsilon)$ then optimal vertex
cover in $G$ has size at most $(\frac{8}{9}-\epsilon)\cdot n$. Given that the
matching is $\mathcal{A}$-perfect, all the $a_{j}^{\prime}$ type agents ($m$
in total) must be matched to some program in $\mathcal{P}_{j}^{\prime}$. Note
that each such agent must contribute a cost of $2n$ and hence they together
contribute a cost of $2mn$.

Suppose the edge-agent $a_{j}^{\prime}$ is matched to a program
$p_{i}^{\prime}$ such that $u_{i}$ is one of the end-points of edge $e_{j}$.
Then, $m$ $s_{i}^{t}$ vertex-agents for the vertex $u_{i}$ must be matched to
either $p_{i}$ or $p_{i}^{\prime}$, otherwise they form a blocking pair with
the program $p_{i}^{\prime}$. Let $V^{\prime}$ be the set of vertices $u_{i}$
such that at least one $s_{i}^{t}$ is matched to $p_{i}$ or $p_{i}^{\prime}$.
If $u_{i}\in V^{\prime}$ is such that less than m $s_{i}^{t}$ type agents are
matched to $p_{i}$ or $p_{i}^{\prime}$, then it implies that no edge-agent
corresponding to the edge incident on $u_{i}$ could have been matched to
$p_{i}^{\prime}$ but is matched to $p_{k}^{\prime}$ where $u_{k}$ is its other
end-point. Thus, we can remove such $u_{i}$ from $V^{\prime}$. It is clear
that $V^{\prime}$ is a vertex cover of $G$ since the matching is
$\mathcal{A}$-perfect. For every $u_{i}\in V^{\prime}$, all $m$ $s_{i}^{t}$
vertex-agents are matched to $p_{i}$ or $p_{i}^{\prime}$. Since they together
contribute the cost at most $mn(\frac{8}{3}-3\epsilon)$ and each $u_{i}\in
V^{\prime}$ has $m$ copies matched, each contributing a cost of at least $3$,
it implies that $|V^{\prime}|\leq(\frac{8}{9}-\epsilon)\cdot n$, implying that
an optimal vertex cover in $G$ has size at most $(\frac{8}{9}-\epsilon)\cdot
n$. ∎

###### Lemma 11

The $\sf MINSUM$ problem is $\sf NP$-hard to approximate within a factor of
$\frac{7}{6}-\delta$ for any constant $\delta>0$.

###### Proof

We use the following proposition and the results proved in Lemma 9 and Lemma
10.

Proposition [9]. For any $\epsilon>0$ and $p<\frac{3-\sqrt{5}}{2}$, the
following holds: If there is a polynomial-time algorithm that, given a graph
$G=(V,E)$, distinguishes between the following two cases, then $\sf P=\sf NP$.

$(1)|VC(G)|\leq(1-p+\epsilon)|V|$

$(2)|VC(G)|>(1-max\\{p^{2},4p^{3}-3p^{4}\\}-\epsilon)|V|$ ∎

By letting $p=\frac{1}{3}$ in Proposition above, we know that the existence of
a polynomial-time algorithm that distinguishes between the following two cases
implies $\sf P=\sf NP$ for an arbitrary small positive constant $\epsilon$:

$(1)|VC(G)|\leq(\frac{2}{3}+\epsilon)|V|$ i.e. $cost(M)\leq(4+3\epsilon)mn$

$(2)|VC(G)|>(\frac{8}{9}-\epsilon)|V|$ i.e.
$cost(M)>(\frac{14}{3}-3\epsilon)mn$

Now, suppose that there is a polynomial-time approximation algorithm $A$ for
$\sf MINSUM$ whose approximation ratio is at most $\frac{7}{6}-\delta$ for
some $\delta$. Then, consider a fixed constant $\epsilon$ such that
$\epsilon<\frac{8\delta}{13-6\delta}$. If an instance of case $(1)$ is given
to $A$, it outputs a solution with cost at most
$(4+3\epsilon)mn(\frac{7}{6}-\delta)<mn\frac{26(7-6\delta)}{3(13-6\delta)}$.
If an instance of case $(2)$ is given to $A$, it outputs a solution with cost
greater than
$mn(\frac{14}{3}-3\epsilon)>mn\frac{26(7-6\delta)}{3(13-6\delta)}$. Hence,
using $A$, we can distinguish between cases $(1)$ and $(2)$, which implies
that $\sf P=\sf NP$. ∎

This establishes Theorem 1.3.

## References

  * [1] Abdulkadiroğlu, A., Sönmez, T.: School choice: A mechanism design approach. American Economic Review 93(3), 729–747 (June 2003). https://doi.org/10.1257/000282803322157061
  * [2] Aziz, H., Baychkov, A., Biró, P.: Summer internship matching with funding constraints. In: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20. pp. 97–104 (2020), https://dl.acm.org/doi/abs/10.5555/3398761.3398778
  * [3] Baswana, S., Chakrabarti, P.P., Chandran, S., Kanoria, Y., Patange, U.: Centralized admissions for engineering colleges in india. Interfaces 49(5), 338–354 (2019). https://doi.org/10.1287/inte.2019.1007
  * [4] Biró, P., Fleiner, T., Irving, R.W., Manlove, D.: The college admissions problem with lower and common quotas. Theor. Comput. Sci. 411(34-36), 3136–3153 (2010). https://doi.org/10.1016/j.tcs.2010.05.005
  * [5] Biró, P., Manlove, D., Mittal, S.: Size versus stability in the marriage problem. Theor. Comput. Sci. 411(16-18), 1828–1841 (2010). https://doi.org/10.1016/j.tcs.2010.02.003
  * [6] Biró, P., Manlove, D.F., Mittal, S.: Size versus stability in the marriage problem. Theor. Comput. Sci. 411(16-18), 1828–1841 (2010). https://doi.org/10.1016/j.tcs.2010.02.003
  * [7] Cardinal, J., Karpinski, M., Schmied, R., Viehmann, C.: Approximating vertex cover in dense hypergraphs. Journal of Discrete Algorithms 13, 67 – 77 (2012). https://doi.org/https://doi.org/10.1016/j.jda.2012.01.003
  * [8] Cooper, F.: Fair and large stable matchings in the stable marriage and student-project allocation problems. Ph.D. thesis, University of Glasgow, UK (2020), http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.815027
  * [9] Dinur, I., Safra, S.: The importance of being biased. In: Proceedings on 34th Annual ACM Symposium on Theory of Computing. pp. 33–42 (2002), https://doi.org/10.1145/509907.509915
  * [10] Gajulapalli, K., Liu, J.A., Mai, T., Vazirani, V.V.: Stability-preserving, time-efficient mechanisms for school choice in two rounds. In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020). LIPIcs, vol. 182, pp. 21:1–21:15 (2020). https://doi.org/10.4230/LIPIcs.FSTTCS.2020.21
  * [11] Gale, D., Shapley, L.S.: College admissions and the stability of marriage. The American Mathematical Monthly 69(1), 9–15 (1962), http://www.jstor.org/stable/2312726
  * [12] Hamada, K., Iwama, K., Miyazaki, S.: The hospitals/residents problem with lower quotas. Algorithmica 74(1), 440–465 (2016). https://doi.org/10.1007/s00453-014-9951-z, https://doi.org/10.1007/s00453-014-9951-z
  * [13] Hoshino, R., Raible-Clark, C.: The quest draft: An automated course allocation algorithm. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. pp. 2906–2913 (2014), http://www.aaai.org/ocs/index.php/IAAI/IAAI14/paper/view/8341
  * [14] Huang, C.C., Kavitha, T.: Popular matchings in the stable marriage problem. In: International Colloquium on Automata, Languages, and Programming. pp. 666–677. Springer (2011). https://doi.org/10.1007/978-3-642-22006-7_56
  * [15] Irving, R.: Matching practices for entry-labor markets – scotland, mip country profile 3. (2011), https://www.matching-in-practice.eu/the-scottish-foundation-allocation-scheme-sfas/
  * [16] Kawase, Y., Iwasaki, A.: Approximately stable matchings with budget constraints. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18) (2018), https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17032
  * [17] Krishnapriya, A.M., Nasre, M., Nimbhorkar, P., Rawat, A.: How good are popular matchings? In: 17th International Symposium on Experimental Algorithms, SEA 2018\. pp. 9:1–9:14 (2018). https://doi.org/10.4230/LIPIcs.SEA.2018.9
  * [18] Othman, A., Sandholm, T., Budish, E.: Finding approximate competitive equilibria: efficient and fair course allocation. In: 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010). pp. 873–880 (2010), https://dl.acm.org/citation.cfm?id=1838323
  * [19] Rios, I., Larroucau, T., Parra, G., Cominetti, R.: College admissions problem with ties and flexible quotas (01 2014). https://doi.org/10.2139/ssrn.2478998
  * [20] Robards, P.A.: Applying two-sided matching processes to the united states navy enlisted assignment process. Tech. rep., NAVAL POSTGRADUATE SCHOOL MONTEREY CA (2001)
  * [21] Roth, A.E.: On the allocation of residents to rural hospitals: A general property of two-sided matching markets. Econometrica 54(2), 425–427 (1986), http://www.jstor.org/stable/1913160
  * [22] Sönmez, T., Ünver, M.U.: Course bidding at business schools. International Economic Review 51(1), 99–123 (2010). https://doi.org/10.1111/j.1468-2354.2009.00572.x
  * [23] Yang, W., Giampapa, J., Sycara, K.: Two-sided matching for the us navy detailing process with market complication. Tech. rep., Technical Report CMU-RI-TR-03-49, Robotics Institute, Carnegie-Mellon University (2003)
  * [24] Yokoi, Y.: Envy-free matchings with lower quotas. Algorithmica 82(2), 188–211 (2020). https://doi.org/10.1007/s00453-018-0493-7, https://doi.org/10.1007/s00453-018-0493-7


# Symplectic Particle Tracking in a Thick Nonlinear McMillan Lens for the
Fermilab Integrable Optics Test Accelerator (IOTA)

B. Cathey<EMAIL_ADDRESS>G. Stancari  T. Zolkin  Fermi National Accelerator
Laboratory  Batavia  IL  USA

###### Abstract

The McMillan system is a novel method to increase the tune spread of a beam
without decreasing its dynamic aperture due to the system’s integrability.
While the ideal system is based on an infinitely thin kick, the physical
design requires a thick electron lens, including a solenoid. Particle
transport through the lens is difficult to simulate due to the nature of the
force on the circulating beam. This paper demonstrates accurate simulation of
a thick McMillan lens in a solenoid using symplectic integrators derived from
Yoshida’s method.

##  1 INTRODUCTION

As circular accelerators achieve higher beam intensities, beam instabilities
increasingly limit design capabilities. Beam instabilities can come from
interactions of the beam with the surrounding environment through wakefields
and impedance, or from space charge due to the beam itself. Landau damping is
one way to mitigate instabilities. Landau damping is the use of a spread of
betatron tunes to lower a beam’s sensitivity to instabilities. To generate a
tune spread nonlinear forces are required, such as octupole magnets creating
tune spread dependent on the particle’s amplitude. However, octupoles and
other nonlinear elements can have a significant drawback in that they reduce
the beam’s dynamic aperture. There are nonlinear dynamical systems that are
integrable, and that can be implemented in accelerators, without loss of
dynamic aperture [1, 2, 3, 4, 5, 6].

The Integrable Optics Test Accelerator (IOTA) at Fermilab is partly dedicated
to the experimental study of novel, integrable, nonlinear focusing lattices
[7]. In particular, one straight section is designed to include an electron
lens, which will be used for research on nonlinear dynamics, electron cooling,
and space-charge compensation [8, 7, 9, 10]. Because of their flexibility,
electron lenses can be designed to have different effects on the circulating
beam [11, 12, 13, 14, 15]. In this paper, we focus on the simulation of a
realistic McMillan electron lens, the nonlinear element necessary for creating
the McMillan integrable system in IOTA [16, 17, 18].

##  2 BACKGROUND

The McMillan system has two sections: a linear transport and a nonlinear kick
[2, 3]. The linear transport requires a $\pi/2$ phase advance in both vertical
and horizontal phase spaces, and a round beam at the kick. The two dimensional
McMillan kick is defined as

$f(r)=\frac{kr}{\frac{r^{2}}{a^{2}}+1},$ (1)

with $k$ as the kick strength and $a$ as an effective width. This system has
two integrals of motion guaranteeing integrability. These are best defined in
polar coordinates where:

$\displaystyle r$ $\displaystyle=\sqrt{x^{2}+y^{2}},$ $\displaystyle
r^{\prime}$
$\displaystyle=\frac{xx^{\prime}+yy^{\prime}}{\sqrt{x^{2}+y^{2}}},$ (2)
$\displaystyle\theta$ $\displaystyle=\arctan 2{(y,x)},$
$\displaystyle\theta^{\prime}$
$\displaystyle=\frac{xy^{\prime}-yx^{\prime}}{\sqrt{x^{2}+y^{2}}}.$

One is the angular momentum $L_{z}=r\theta^{\prime}$. The other is given by

$I=\frac{r^{2}r^{\prime 2}}{a^{2}}+\frac{r^{2}}{\beta^{2}}+r^{\prime
2}+\theta^{\prime 2}-krr^{\prime}.$ (3)

This system generates a wide tune spread while maintaining integrability [17,
19]. There are two regimes of strength for the McMillan lens based on the
lattice beta function. The weak regime occurs when $\beta k<2$ and has a
maximum tune spread of

$(\Delta\nu_{\theta})_{\mathrm{max}}=\frac{1}{4}-\frac{1}{2\pi}\arccos{\left(\frac{\beta
k}{2}\right)}.$ (4)

The strong regime is when $\beta k>2$ and can create a tune spread that
reaches the integer resonance.

However, this system cannot be physically achieved with a thin kick. The
electron lens must have some length and be contained within a solenoid to
magnetically confine the electron beam and keep the lens current consistent
throughout beam traversal. These complications are shown in Fig. 1. To predict
how they affect particle motion compared to the ideal system, the motion
through the lens needs to be simulated.

Figure 1: Drawing of the electron lens in IOTA.

##  3 SYMPLECTIC INTEGRATION OF THE MCMILLAN LENS

The most straightforward way to simulate the lens is to solve the equations of
motion for a particle in the lens. To do so, the lens is analyzed in isolation
from the rest of the lattice, treating the lens beam as a current density with
infinite length. The kick in Eq. (1) is created with a current density of the
form

$J(r)=\frac{j_{0}}{\left(\frac{r^{2}}{a^{2}}+1\right)^{2}},$ (5)

where $j_{0}$ is the peak current density on axis. The current density gives a
total force from the electric and magnetic fields of

$\vec{F}(r)=\frac{e\left(1\pm\beta_{z}\beta_{e}\right)j_{0}}{2\epsilon_{0}\beta_{e}c}\frac{r}{\frac{r^{2}}{a^{2}}+1}\hat{r}=\kappa\frac{r}{\frac{r^{2}}{a^{2}}+1}\hat{r},$
(6)

with $\beta_{e}$ and $\beta_{z}$ being the ratios to $c$ of the lens beam’s
velocity and the circulating beam’s velocity respectively. This force has a
potential energy of the form

$V=\frac{-\kappa a^{2}}{2}\ln\left(\frac{r^{2}}{a^{2}}+1\right).$ (7)

The solenoid is treated as a uniform magnetic field, $B$, along the beam axis.
The fringe effects of the solenoid can then be added before and after the main
lens transport. This isolated lens system has two constants of motion as well:
the angular momentum and the total energy given by

$\displaystyle L_{M}$ $\displaystyle=p_{z}r\theta^{\prime}-\frac{eBr^{2}}{2},$
(8) $\displaystyle E_{M}$ $\displaystyle=\frac{p_{z}^{2}}{2m}\left(r^{\prime
2}+\theta^{\prime 2}\right)-\frac{\kappa
a^{2}}{2}\ln\left(\frac{r^{2}}{a^{2}}+1\right).$

Here, $p_{z}$ is the momentum of the circulating beam particle along the beam
axis, and $m$ is its mass.

Unfortunately, logarithmic central potentials such as Eq. (7) have no known
solutions. As such, the thick lens must be approximated. While the final phase
space position cannot be directly calculated, we can see how close to the
correct value the approximation is based on the error to the constants in Eq.
(8) after transport through the lens. The simplest approach is to use
alternating solenoid transports and kicks of the form of Eq. (1). However,
increasing numbers of transport-kick slices approached convergence very
slowly. A super convergent method is needed to accurately and efficiently
simulate the McMillan lens.

As the lens system has two separable Hamiltonians, the lens beam and the
solenoid, Yoshida’s method for constructing symplectic integrators is viable
[20]. Yoshida’s method creates coefficients for increasing orders of
integrator. These coefficients are applied to the length, $L$, of the
transport or kick. The kick coefficient, $k$, is given by

$k=\frac{L}{p_{z}\beta_{z}c}\kappa=\frac{L\left(1\pm\beta_{z}\beta_{e}\right)j_{0}}{2(B\rho)\epsilon_{0}\beta_{z}\beta_{e}c^{2}},$
(9)

so that the kick strength is simply multiplied by the appropriate coefficient.
The solenoid transport matrix has its effective length multiplied by the
coefficient [21]. The second order integrator used as a base for the Yoshida
method was: transporting half-way through the solenoid, a full strength kick,
and transporting another solenoid half
$\left(\frac{1}{2},1,\frac{1}{2}\right)$.

To further increase accuracy, the lens was first sliced into small equal units
of length, and each individual unit was symplectically integrated over its
smaller length. Figure 2 shows an example with the fourth order integrator.
This was done for multiple orders of integrator.

Figure 2: Diagram showing how the lens is approximated using a symplectic
integrator over equal slices of the lens.

##  4 SIMULATIONS OF THE MCMILLAN LENS

Simulations were conducted using an isolated lens with a length of $L=0.7\
\mathrm{m}$, kick strength $k=1.076\ \mathrm{m^{-1}}$, and solenoid field
$B=0.333\ \mathrm{T}$. Figure 3 shows an example of how different orders
converge on the energy for a test particle. Only the energy convergence is
shown because $L_{M}$ quickly converged. The results show how the symplectic
integrators converge much faster than the transport-kick approximation,
eventually reaching machine accuracy.

Figure 3: Graph showing how different orders of integrator converge with
increasing numbers of slices. The particle started with
$x,x^{\prime},y,y^{\prime}=(2\ \mathrm{mm},-0.1\ \mathrm{mrad},-3\
\mathrm{mm},0.4\ \mathrm{mrad})$.

The rate of convergence for each integrator depends on the initial phase-space
coordinates of a particle. For simplicity’s sake, a single approximation that
adequately covers all relevant particle starting coordinates needs to picked.
After looking at a few sample starting positions, the sixth order integrator
looked like a good choice for accurate results. Figure 4 shows the error in
total energy after transporting through the lens for 50 slices of the sixth
order with a phase space where the initial $\theta^{\prime}=0$. A very wide
range of starting radii and radial velocities was chosen to explore the
behavior of this integration scheme. The plot shows that accuracy decreases in
regions with specific radial velocities. These regions are at the edge of
typical beam parameters and will only affect larger beam sizes. Particles
outside of these regions were transported with high accuracy.

Figure 4: Color plot showing the error in energy for 50 slices with the 6th
order integrator for the $\theta^{\prime}=0$ phase space.

Using the above approximation, initial studies of an orbiting beam in the full
ring were done using a simple transport matrix with a $\pi/2$ phase advance,
as required by the ideal McMillan system, with $\beta=3\ \mathrm{m}$ at the
lens entrance. The beam had an uncorrelated Gaussian distribution with initial
horizontal and vertical emittances of 2.95 mm mrad. Figures 5 and 6 show the
tune spreads due to a weak and strong lens, respectively. Interestingly, the
weak lens reached the integer angular resonance, which is not possible in the
ideal McMillan system.

Figure 5: Plot of the radial and angular tune spread of a weak ($k=0.538\
\mathrm{m^{-1}}$) lens. The beam was tracked for 360 turns. Figure 6: Plot of
the radial and angular tune spread of a strong ($k=1.076\ \mathrm{m^{-1}}$)
lens. The beam was tracked for 430 turns.

##  5 CONCLUSIONS

This method allows for more realistic simulations of the McMillan electron
lens. As the approximation can be computationally expensive, running
simulations on parallel processors will be necessary to look at long term
motion of the beam. As such, we are planning to implement this method in a
tool with parallel processing. Further additions can be done to improve
modeling of the system. One possibility is adding space-charge both outside
and inside the lens to see how stability and tune shifts are affected, and
another is electron lens imperfections to see how sensitive the system is.
Finally, there is the question of how to best design and implement experiments
in IOTA. As the system now deviates from integrability, is there a way to
adjust IOTA such that this deviation can be minimized? Removing the phase
advance due to lens focusing from the $\pi/2$ phase advance outside the lens,
or adding a compensating solenoid elsewhere might bring the beam closer to the
ideal case. Now we can test these and other cases to determine the best way to
proceed experimentally.

##  6 ACKNOWLEDGMENTS

This manuscript has been authored by Fermi Research Alliance, LLC under
Contract No. DE-AC02-07CH11359 with the U.S. Department of Energy, Office of
Science, Office of High Energy Physics. Report no. FERMILAB-CONF-22-549-AD.

## References

  * [1] A G Ruggiero  “Integrability of the Two-Dimensional Beam-Beam Interaction in a Special Case”  In _Part. Accel._ 12, 1982, pp. 45–47  URL: https://inspirehep.net/literature/180398
  * [2] V V Danilov and E A Perevedentsev  “On Invariants and Integrability in Nonlinear Accelerator Optics”, 1994  URL: https://cds.cern.ch/record/703505
  * [3] V V Danilov and E A Perevedentsev  “Two Examples of Integrable Systems with Round Colliding Beams”  In _Proceedings of the IEEE Particle Accelerator Conference (PAC07)_ , 1998, pp. 1759–1761  URL: doi:10.1109/pac.1997.750998
  * [4] V V Danilov and V D Shiltsev  “On Possibility of Footprint Compression with One Lens in Nonlinear Accelerator Lattice”, 1998  URL: https://inspirehep.net/literature/474133
  * [5] V Danilov and V Shiltsev  “On the Possibility of Footprint Compression with One Lens in Nonlinear Accelerator Lattice”  In _J. Instrum._ 16.03 IOP Publishing, 2021, pp. P03050  URL: doi:10.1088/1748-0221/16/03/P03050
  * [6] V Danilov and S Nagaitsev  “Nonlinear Accelerator Lattices with One and Two Analytic Invariants”  In _Phys. Rev. ST Accel. Beams_ 13.8, 2010, pp. 084002  URL: doi:10.1103/PhysRevSTAB.13.084002
  * [7] S Antipov et al.  “IOTA (Integrable Optics Test Accelerator): Facility and Experimental Beam Physics Program”  In _J. Instrum._ 12.03 IOP Publishing, 2017, pp. T03002  URL: doi:10.1088/1748-0221/12/03/t03002
  * [8] Giulio Stancari  “Applications of Electron Lenses: Scraping of High-Power Beams, Beam-Beam Compensation, and Nonlinear Optics”  In _Proceedings of the 16h Advanced Accelerator Concepts Workshop_ 1777, 2016  URL: doi:10.1063/1.4965688
  * [9] G. Stancari et al.  “Beam physics research with the IOTA electron lens”  In _Journal of Instrumentation_ 16.05 IOP Publishing, 2021, pp. P05002  URL: doi:10.1088/1748-0221/16/05/p05002
  * [10] Nilanjan Banerjee et al.  “Electron Cooling With Space-Charge Dominated Proton Beams at IOTA”  In _Proceedings of The 13th International Workshop COOL’21_ , 2021, pp. S201  URL: doi:10.18429/JACoW-COOL2021-S201
  * [11] V Shiltsev et al.  “Experimental Demonstration of Colliding-Beam-Lifetime Improvement by Electron Lenses”  In _Phys. Rev. Lett._ 99 American Physical Society, 2007, pp. 244801  URL: doi:10.1103/PhysRevLett.99.244801
  * [12] G Stancari et al.  “Collimation with Hollow Electron Beams”  In _Phys. Rev. Lett._ 107 American Physical Society, 2011, pp. 084802  URL: doi:10.1103/PhysRevLett.107.084802
  * [13] W Fischer et al.  “Operational Head-on Beam-Beam Compensation with Electron Lenses in the Relativistic Heavy Ion Collider”  In _Phys. Rev. Lett._ 115 American Physical Society, 2015, pp. 264801  URL: doi:10.1103/PhysRevLett.115.264801
  * [14] Vladimir D Shiltsev  “Electron Lenses for Super-Colliders”  Springer, 2016  URL: doi:10.1007/978-1-4939-3317-4
  * [15] S Redaelli et al.  “Hollow Electron Lenses for Beam Collimation at the High-Luminosity Large Hadron Collider (HL-LHC)”  In _J. Instrum._ 16.03 IOP Publishing, 2021, pp. P03042  URL: doi:10.1088/1748-0221/16/03/P03042
  * [16] Edwin M McMillan  “A Problem in the Stability of Periodic Systems”  In _Topics in Modern Physics: A Tribute to Edward U. Condon_ Boulder, Colorado: Colorado Associated University Press, 1971, pp. 219–244
  * [17] B Cathey, G Stancari, A Valishev and T Zolkin  “Calculations of Detuning with Amplitude for the McMillan Electron Lens in the Fermilab Integrable Optics Test Accelerator (IOTA)”  In _J. Instrum._ 16.03 IOP Publishing, 2021, pp. P03041  URL: doi:10.1088/1748-0221/16/03/P03041
  * [18] Brandon Cathey and Giulio Stancari  “Progress on the Electron Gun Design for a McMillan Electron Lens in the Fermilab Integrable Optics Test Accelerator (IOTA)”, 2021
  * [19] Sergei Nagaitsev and Timofey Zolkin  “Betatron Frequency and the Poincaré Rotation Number”  In _Phys. Rev. Accel. Beams_ American Physical Society, 2020  URL: doi:10.1103/physrevaccelbeams.23.054001
  * [20] Haruo Yoshida  “Construction of higher order symplectic integrators”  In _Physics Letters A_ 150.5-7 Elsevier BV, 1990, pp. 262–268  URL: doi:10.1016/0375-9601(90)90092-3
  * [21] D Rubin  “Measurement and Diagnosis of Coupling and Solenoid Compensation”  In _Handbook of Accelerator Physics and Engineering_ World scientific, 2013, pp. 352