11institutetext: Department of Computer Information Systems, Texas A&M
University - Central Texas, Killeen TX 76549, USA
11email<EMAIL_ADDRESS>
22institutetext: School of Computer Science and Technology, Qilu Technology
University, China
22email<EMAIL_ADDRESS>
33institutetext: Department of Computer Science, Baylor University, Waco, TX
33email<EMAIL_ADDRESS>44institutetext: Department of Computer Science, The
University of Texas at Dallas, Dallas, TX
44email<EMAIL_ADDRESS>
# Profit Maximization in Social Networks and Non-monotone DR-submodular
Maximization

Shuyang Gu 11 0000-0003-4535-2280 Chuangen Gao 22 Jun Huang 33 Weili Wu 44

###### Abstract

In this paper, we study the non-monotone DR-submodular function maximization
over integer lattice. Functions over integer lattice have been defined
submodular property that is similar to submodularity of set functions. DR-
submodular is a further extended submodular concept for functions over the
integer lattice, which captures the diminishing return property. Such
functions find many applications in machine learning, social networks,
wireless networks, etc. The techniques for submodular set function
maximization can be applied to DR-submodular function maximization, e.g., the
double greedy algorithm has a $1/2$-approximation ratio, whose running time is
$O(nB)$, where $n$ is the size of the ground set, $B$ is the integer bound of
a coordinate. In our study, we design a $1/2$-approximate binary search double
greedy algorithm, and we prove that its time complexity is $O(n\log B)$, which
significantly improves the running time. Specifically, we consider its
application to the profit maximization problem in social networks with a
bipartite model, the goal of this problem is to maximize the net profit gained
from a product promoting activity, which is the difference of the influence
gain and the promoting cost. We prove that the objective function is DR-
submodular over integer lattice. We apply binary search double greedy
algorithm to this problem and verify the effectiveness.

###### Keywords:

Profit Maximization Social Networks DR-submodular binary search double greedy
approximation algorithm.

##  1 Introduction

A lot of real-world problems have objective functions with a so-called
submodular property, which reflects the diminish return nature of the
problems. Since such property exists in a vast amount of applications,
submodular optimization has caught a lot of attention during the past two
decades.

Submodular set function optimization includes maximizing or minimizing a
submodular function with or without some constraints. One of the directions is
non-monotone submodular maximization without constraint. This problem is,
given a non-negative submodular set function $f$, to find a subset $S$ that
maximizes $f(S)$. Since this problem captures many applications in machine
learning, viral marketing, etc., it has been studied extensively. A
deterministic local search gives a $1/3$ -approximation and a randomized
smoothed local search algorithm gives $2/5$-approximation [3]. Buchbinder et
al. further improve that result, they show that a deterministic double greedy
algorithm provides 1/3-approximation, and the randomized version of it gives a
1/2-approximation, both in linear time [5].

Recently, submodular optimization has been extended to functions over integer
lattice, which considers the situation that each element in the ground set can
be selected as multiple copies. The functions over integer lattice may also
have submodular property, which is defined similarly to set functions’
submodular. Due to the relationship between the two types of submodular, the
techniques for submodular set function optimization can be applied to lattice
submodular optimization. Based on the double greedy algorithm in [5], an
algorithm for submodular functions over the bounded integer lattice can be
designed with $1/3$ approximation ratio [2].

An interesting fact is that although the definition of lattice submodular is
similar to set function submodular, the lattice submodular does not imply
diminish return property like submodular set function. Soma et al. [4] thus
give a stronger generalization of submodularity on integer lattice, which is
called diminishing return submodular (DR-submodular) functions, such functions
capture various applications with diminishing return property. In this paper,
we specifically study the non-monotone DR-submodular maximization problem and
one of the applications: profit maximization in social networks.

The development of online social networks such as Facebook and Twitter
provides opportunities for large-scale online viral marketing. Under this
circumstance, influence maximization becomes a very popular research
direction, which could be described as the problem of finding a small set of
most influential nodes in a social network so that the spread of influence in
the network is maximizeds. A large amount of efforts have been made on this
research topic since Kempe et al. [24] first defined the problem and obtained
plentiful results in many ways[29, 25, 28]. Those studies are based on the
assumption that the number of influenced users determines the profit of
product [30, 24, 26, 27, 31]. The influence maximization (IM) problem and the
problems extended from IM adopt the cadinality or knapsack constraint, which
represents the seeding budget in a product promotion activity. Under such
setting, the solution, which is a set of the most influential seed nodes,
should maximizes the expected influenced nodes with the constraint of seeds
number. Since the influence spread is a non-decreasing function of the seeds
set[24], the solution seeds set is always of the limit size. In this paper, we
study the overall profit maximization, our goal is to obtain the optimal
investment to achieve the maximum net profit, which take into account the
varying cost of seeding that is proportional to the number of seeds. In this
problem, the objective function is not monotone and there is no cardinality or
knapsack constraint.

The contributions of this paper are summarized as follows.

  * •

We propose a novel problem named profit maximization

  * •

We prove the profit maximization problem is NP-hard and DR-submodular.

  * •

To solve the non-monotone DR-submodular maximization problem, we propose the
binary search double greedy algorithm.

  * •

We prove the algorithm has a 1/2- approximate ratio and the time complexity is
polynomial($n\log B$). To the best of our knowledge, this is the fastest
algorithm with the least queries to the objective function.

This article is organized as follows. In Section 2, we review the existing
work. In section 3, we present the preliminaries for submodular and DR
submodular optimization problems. Then we introduce the profit maximization
problem in section 4 and show the objective function is DR-submodular. In
section 5, the binary search double greedy algorithm is presented to solve the
DR-submodular maximization problem, we give theoretical proof of the
approximation ratio and time complexity. The conclusion is presented in
Section 6.

##  2 Related Work

Non-monotone DR-submodular Maximization is closely related to non-monotone
submodular set function maximization because the algorithm for the latter
problem can be applied to the former problem directly. The non-monotone
submodular maximization is also called Unconstrained Submodular
Maximization(USM). USM has various applications, such as marketing strategies
over social networks [18], Max-Cut[19], and maximum facility location [20].
USM problem has been studied extensively[21, 22, 23]. Buchbinder gives a tight
linear time randomized (1/2)-approximation for the problem[5].

The topic of functions over integer lattice optimization has attracted much
attention recently, the submodularity of such functions are considered.
Monotone submodular functions over integer lattice with cardinality constraint
are addressed in [10, 12, 14]. Sahin et al. study lattice submodular functions
subject to a discrete (integer) polymatroid constraint [13]. Zhang et al.
study the problem of maximizing the sum of a monotone non-negative DR-
submodular function and a supermodular function on the integer lattice subject
to a cardinality constraint[11]. The non-submodular functions on the integer
lattice are addressed in [16]. Nong et al. focus on maximizing a non-monotone
weak-submodular function on a bounded integer lattice [17]. For the problem
addressed in this paper, non-monotone DR-submodular function maximization,
Soma et al. design a $\frac{1}{2+\epsilon}$-approximation algorithm with a
running time of $O(\frac{n}{\epsilon}\log^{2}B)$ [6].

In the meantime, the discrete domains of submodular functions over integer
lattice are further extended to continuous domains, Hassani et al. study
stochastic projected gradient methods for maximizing continuous submodular
functions with convex constraints [15]. In [8, 7], the authors consider
maximizing a continuous and nonnegative submodular function over a hypercube.

For optimization problems in social networks, many fall into submodular set
function maximization subject to a cardinality constraint [24, 25, 26, 27].
The budget allocation problem [9] falls into monotone submodular function
maximization over integer lattice subject to a knapsack constraint.

##  3 Preliminaries

We say that a set function $g:2^{E}\to\mathbb{R_{+}}$ is submodular if it
satisfies following inequality:

$\displaystyle g(X)+g(Y)\geq g(X\cup Y)+g(X\cap Y),\forall X,Y\subseteq E$

The submodular definition also reflects a natural “diminishing returns”
property: the marginal gain of adding an element to a set $X$ is at least as
high as the marginal gain of adding the same element to a superset of $X$.
Formally, for every set $X,Y$ such that $X\subseteq Y\subseteq E$ and every
$e\in E\setminus Y$, it follows that

$g(X\cup\\{e\\})-g(X)\geq g(Y\cup\\{e\\})-g(Y)$

The monotonicity definition for a set function is that a function is monotone
non-decreasing iff $g(X)\leq g(Y)$ for $\forall X\subseteq Y$.

Functions over integer lattice may have similar property as submodular set
functions. A function $h:\mathbb{Z}_{+}^{E}\to\mathbb{R_{+}}$ that is defined
over the integer lattice is submodular if the following holds[2]:

$\displaystyle h(\boldsymbol{x})+h(\boldsymbol{y})\geq
h(\boldsymbol{x}\lor\boldsymbol{y})+h(\boldsymbol{x}\land\boldsymbol{y}),\boldsymbol{x},\boldsymbol{y}\in\mathbb{Z}_{+}^{E}.$

where
$(\boldsymbol{x}\lor\boldsymbol{y})(i)=\max\\{\boldsymbol{x}(i),\boldsymbol{y}(i)\\}$
and
$(\boldsymbol{x}\land\boldsymbol{y})(i)=\min\\{\boldsymbol{x}(i),\boldsymbol{y}(i)\\}$.
The vectors $\boldsymbol{x}$ and $\boldsymbol{y}$ have the same dimensions.
Hence $\boldsymbol{x}\lor\boldsymbol{y}$ represents coordinate-wise maximum,
and $\boldsymbol{x}\land\boldsymbol{y}$ denote the coordinate-wise minimum. We
can see this form of submodularity is a more generalized definition of
submodularity that covers set functions submodular, because vectors with all
entries equal to either 0 or 1 can be seen as a subset including the elements
that are equal to $1$ while excluding the elements that are equal to $0$, in
that case, $\boldsymbol{x}\land\boldsymbol{y}$ and
$\boldsymbol{x}\lor\boldsymbol{y}$ transform to set intersection and set union
of the subsets that $\boldsymbol{x}$ and $\boldsymbol{y}$ represent
respectively .

The submodular function over integer lattice does not have the diminishing
return property. To capture such property in real-world problems, a stronger
version of submodularity has been introduced, which is called DR-
submodular[4]. DR submodular function on a bounded integer lattice satisfies
the following diminish return property:

$\displaystyle h(\boldsymbol{x}+\chi_{e})-h(\boldsymbol{x})\geq
h(\boldsymbol{y}+\chi_{e})-h(\boldsymbol{y}),\forall\boldsymbol{x}\leq\boldsymbol{y},\forall
e\in E$

where $\chi_{e}$ denotes a unit vector, i.e. $\chi_{e}\in\mathbb{Z}^{E}$ is
the vector with $\chi_{e}(e)=1$ and $\chi_{e}(a)=0$ for every $a\neq e$.

The problem we consider is maximizing (non-monotone) DR-submodular functions
over bounded integer lattice. Formally, we study the optimization problem

$\displaystyle\begin{aligned} \max&&f(x)\\\ \mbox{subject
to}&&\boldsymbol{0}\leq x\leq\boldsymbol{B},\end{aligned}$ (1)

where $f:\mathbb{Z}_{+}^{E}\to\mathbb{R}_{+}$ is a non-negative DR-submodular
function and not necessarily monotone. $\boldsymbol{0}$ is the all zero
vector, and $\boldsymbol{B}\in\mathbb{Z}_{+}^{E}$ is a vector representing the
maximum value for each coordinate. When $\boldsymbol{B}$ is the all-ones
vector, the problem is equivalent to the original unconstrained submodular set
function maximization. We assume that $f$ is given as an evaluation oracle;
when we specify $\boldsymbol{x}\in\mathbb{Z}_{+}^{E}$, the oracle returns the
value of $f(\boldsymbol{x})$. We define
$f(\boldsymbol{x}|\boldsymbol{y})=f(\boldsymbol{y}+\boldsymbol{x})-f(\boldsymbol{y})$.

##  4 Profit Maximization Problem

In this section, we formulate profit maximization problem in bipartite model
formally and prove the objective function is DR-submodular.

We adopted the bipartite influence model [1], by which a social network can be
modeled as a bipartite graph. There are two types of nodes, the source nodes
(marketing channels) and the target nodes (potential customers). The marketing
channels include the social medias, TV, newspapers etc., which may initiat
marketing influence to potential customers. Each marketing channels can affect
a subset of potential customers, which are the customers follows the channel.
For example, a social media account has a group of followers, a TV channel has
relatively fixed audience.

Another assumption is that each marketing channel may influence its potential
customers multiple times, this assumption makes sense since a social media
account may post a product promotion advertisement multiple times, so does a
TV channel, a newspaper or other marketing channels. Each time when a
marketing channel initiate an influence, the influence propogate to all the
audience of that channel. If a marketing channel initiate $x$ trials of
influence, then a viewer recieves the advertisement $x$ times, we assume the
$x$ trials of influence events are independent .

The bipartite graph is denoted $G=(S,T;E)$, where $S$ is the set of source
nodes(marketing channels), $T$ is the set of target nodes(potential
customers), $E\subseteq S\times T$ is the edge set. An edge of the bipartite
graph between a source node $i$ and a target node $j$ indicates $i$ may
influence $j$ with some probability. If a customer does not follow some
channel, there is no edge between them. Each source node s has a capacity
$c(s)\in\mathbb{N_{+}}$, which stands for the trials limit at that source
node. For each source node $s$, there are a series of probabilities
$p_{s}^{1}$, $p_{s}^{2}$, $\dots p_{s}^{c(s)}$, where $p_{s}^{(i)}$ represents
the probability to activate any adjacent target node of the $s$’s $i$th trials
of influence.

Figure 1: A bipartite social network example

A mini social network shown in figure 1 is built as an example, there are
three marketing channels and five potential customers, customer $u_{1}$ and
$u_{3}$ are the followers of the marketing channel $s_{1}$, customers $u_{1}$,
$u_{2}$ and $u_{4}$ are the followers of marketing channel $s_{2}$, customer
$u_{5}$ is a follower of marketing channel $s_{3}$. Suppose channel $s_{1}$
has a marketing capacity $c(s_{1})=10$, which means the marketing influence
trials can be sent are at most 10 times from $s_{1}$. Suppose $c(s_{2})=20$,
$c(s_{3})=15$. For node $s_{1}$, $p_{s_{1}}^{1}$, $p_{s_{1}}^{2}$, $\dots
p_{s_{1}}^{10}$ are given. Similarly, we are given $p_{s_{2}}^{1}$,
$p_{s_{2}}^{2}$, $\dots p_{s_{1}}^{20}$ and $p_{s_{3}}^{1}$, $p_{s_{3}}^{2}$,
$\dots p_{s_{3}}^{15}$.

The goal is to find the optimal number of influence trials for each source
node respecting the capacity of that node, and maximizes the overall profit.
We call the solution a marketing strategy, which is denoted as the vector m,
thus $\textbf{m}(s)$ is the number of influencing trials at the source node
$s$. Note that for one potential customer, he/she may be connected to more
than one marketing channels.

In the above example, if a marketing strategy $\textbf{m}=(2,1,0)$ is applied,
node $u_{1}$ receives the influence three times, two times from the source
node $s_{1}$, one time from $s_{2}$, the three events are independent. The
probability that the node $u_{1}$ is activated is
$1-(1-p_{s_{1}}^{1})\cdot(1-p_{s_{1}}^{2})\cdot(1-p_{s_{2}}^{1})$.

For the general problem, let $\Gamma(t)$ be the set of source nodes that are
adjacent to node $t$. The probability that the node $t$ is activated is:

$\displaystyle
p_{t}({\textbf{m}})=1-\prod_{s\in\Gamma(t)}\prod_{i=1}^{\textbf{m}(s)}{(1-p^{i}_{s})}$
(2)

The optimization target is the expected overall profit, which should be the
difference between the expected influenced nodes $\sigma({\textbf{m}})$ and
the cost of marketing $\delta({\textbf{m}})$. We can obtain
$\sigma({\textbf{m}})$ by summing $p_{t}({\textbf{m}})$ for all $t\in T$,

$\displaystyle\sigma({\textbf{m}})=\sum_{t\in T}p_{t}({\textbf{m}})=\sum_{t\in
T}{(1-\prod_{s\in\Gamma(t)}\prod_{i=1}^{\textbf{m}(s)}{(1-p^{i}_{s})})}$ (3)

The marketing cost $\delta({\textbf{m}})$ is proportional to the number of
influencing trials, let $\delta_{s}$ be the unit cost for each trial at the
marketing channel $s$. Then the total cost of all marketing channels is

$\displaystyle\delta({\textbf{m}})=\sum_{s\in S}\textbf{m}(s)\cdot\delta_{s}$
(4)

Hence, the objective function is

$\displaystyle
f({\textbf{m}})=\sigma({\textbf{m}})-\delta({\textbf{m}})=\sum_{t\in
T}{(1-\prod_{s\in\Gamma(t)}\prod_{i=1}^{\textbf{m}(s)}{(1-p^{i}_{s})})}-\sum_{s\in
S}\textbf{m}(s)\cdot\delta_{s}$ (5)

######  Definition 1 (Profit Maximization Problem(PM))

Given a social network $G=(S,T;E)$, the marketing capacity vector c, the
influencing probabilities $p_{s}^{1},p_{s}^{2},\dots,p_{s}^{c(s)}$ for each
node $s\in S$, and the unit marketing cost $\delta_{s}$, find a marketing
strategy m, which represents the number of influencing trials at the marketing
channels, to maximize the expected profit through influence propagation:

$\displaystyle\max f(\textbf{m})$ (6) $\displaystyle
s.t.\textbf{0}\leq\textbf{m}\leq\textbf{c}$ (7)

Next we show the objective function of profit maximization problem is DR-
submodular. We assume $p_{e}^{i}\leq p_{e}^{j}$, for any $e\in E$, and $i\geq
j$, because an advertisement has less marketing effect at the $i$th time
people watch it than at an earlier $j$th time.

###### Theorem 4.1

$f(\textbf{m})$ is non-monotone DR-submodular.

The proof of Theorem 1 relies upon two lemmas.

###### Lemma 1

$\sigma({\textbf{m}})$ is DR-submodular.

Proof. It suffices if $p_{t}({\textbf{m}})$ is DR-submodular, because
$\sigma({\textbf{m}})$ is a linear summation of $p_{t}({\textbf{m}})$,
$\forall t\in T$. Suppose ${\textbf{x}}\leq{\textbf{y}}$,
${\textbf{x}},{\textbf{y}}\in\mathbb{Z}_{+}^{S}$. We have

$\displaystyle
p_{t}({\textbf{x}})=1-\prod_{s\in\Gamma(t)}\prod_{i=1}^{\textbf{x}(s)}{(1-p_{s}^{i})}$
$\displaystyle
p_{t}({\textbf{x}}+\chi_{e})=1-[\prod_{s\in\Gamma(t)}\prod_{i=1}^{\textbf{x}(s)}{(1-p^{i}_{s})}]\cdot(1-p_{e}^{\textbf{x}(s)+1})$

Thus,

$\displaystyle
p_{t}(\chi_{e}|{\textbf{x}})=p_{t}({\textbf{x}}+\chi_{e})-p_{t}({\textbf{x}})=[\prod_{s\in\Gamma(t)}\prod_{i=1}^{\textbf{x}(s)}{(1-p_{s}^{i})}]\cdot
p_{e}^{\textbf{x}(e)+1}$

Similarly, we have

$\displaystyle
p_{t}(\chi_{e}|{\textbf{y}})=p_{t}({\textbf{y}}+\chi_{e})-p_{t}({\textbf{y}})=[\prod_{s\in\Gamma(t)}\prod_{i=1}^{\textbf{y}(s)}{(1-p_{s}^{i})}]\cdot
p_{e}^{\textbf{y}(e)+1}$

Since ${\textbf{x}}\leq{\textbf{y}}$, so $\textbf{x}(s)\leq\textbf{y}(s)$,
therefore

$\displaystyle\prod_{s\in\Gamma(t)}\prod_{i=1}^{\textbf{x}(s)}{(1-p_{s}^{i})}\geq\prod_{s\in\Gamma(t)}\prod_{i=1}^{\textbf{y}(s)}{(1-p_{s}^{i})}$

Since ${\textbf{x}}\leq{\textbf{y}}$, we have
$\textbf{x}(e)+1\leq\textbf{y}(e)+1$. So $p_{e}^{\textbf{x}(e)+1}\geq
p_{e}^{\textbf{y}(e)+1}$. Hence,

$\displaystyle p_{t}({\textbf{x}}+\chi_{e})-p_{t}({\textbf{x}})\geq
p_{t}({\textbf{y}}+\chi_{e})-p_{t}({\textbf{y}})$

That means $p_{t}({\textbf{m}})$ is DR-submolar, and so does
$\sigma({\textbf{m}})$. ∎

###### Lemma 2

If function $h(\textbf{x})$ is DR-submodular, function $l(\textbf{x})$ is
modular, then the function $f(\textbf{x})=h(\textbf{x})-l(\textbf{x})$ is DR-
submodular.

Proof.

$\displaystyle f({\boldsymbol{x}}+\chi_{e})-f({\boldsymbol{x}})$
$\displaystyle=h({\boldsymbol{x}}+\chi_{e})-l({\boldsymbol{x}}+\chi_{e})-[h({\boldsymbol{x}})-l({\boldsymbol{x}})]$
(8)
$\displaystyle=h({\boldsymbol{x}}+\chi_{e})-h({\boldsymbol{x}})-[l({\boldsymbol{x}}+\chi_{e})-l({\boldsymbol{x}})]$
(9) $\displaystyle\geq
h({\boldsymbol{y}}+\chi_{e})-h({\boldsymbol{y}})-[l({\boldsymbol{x}}+\chi_{e})-l({\boldsymbol{x}})]$
(10)
$\displaystyle=h({\boldsymbol{y}}+\chi_{e})-h({\boldsymbol{y}})-[l({\boldsymbol{y}}+\chi_{e})-l({\boldsymbol{y}})]$
(11) $\displaystyle=f({\boldsymbol{y}}+\chi_{e})-f({\boldsymbol{y}})$ (12)

The inequality (10) holds because of $h$’s DR-submolarity, the equality (11)
is due to $l$’s modularity. ∎

Based on the above two lemmas, we can easily conclude that the objective
function $f({\textbf{m}})$ is DR-submolar since $\sigma({\textbf{m}})$ is DR-
submodular and $\delta({\textbf{m}})$ is modular. It is apparent that both the
function $\sigma({\textbf{m}})$ and $\delta({\textbf{m}})$ are monotone non-
decreasing, the difference between the monotone submodular functions and the
monotone modular function may not be monotone.

For the computational complexity of the proposed problem, we know that the NP-
hard Max Cut problem is a special case of the unconstrained submodular set
function maximization [3], therefore the more general form lattice submodular
function maximization is also NP-hard.

##  5 Algorithm

In this section, we present the algorithm for non-monotone DR-submodular
function maximization. The main idea is inspired by the double greedy
algorithm for the unconstrained submodular maximization(USM)[5] on set
functions. The algorithm can be extended to accommodate DR-submodular function
over integer lattice[6], because DR-submodular function can be treated as
submodular set function on each coordinate. We investigate some interesting
properties for DR-submodular functions to further speed up the algorithm.

We define two functions
$\phi(b):=f(\boldsymbol{\chi}_{e}|\boldsymbol{x}+b\boldsymbol{\chi}_{e})$
,$\psi(b):=f(-\boldsymbol{\chi}_{e}|\boldsymbol{y}-b\boldsymbol{\chi}_{e})$,
where $b\in\mathbb{Z}^{+}$. Both functions are non-increasing functions of $b$
because the function $f$ is DR-submodular.

Algorithm 1 Binary Search Greedy Algorithm

Input: $f:\mathbb{Z}_{+}^{E}\to\mathbb{R}^{+}$,
$\boldsymbol{B}\in\mathbb{Z}_{+}^{E}$
Assumption: $f$ is DR-submodular

1: $\boldsymbol{x}\leftarrow\boldsymbol{0}$,
$\boldsymbol{y}\leftarrow\boldsymbol{B}$;

2: for $e\in E$ do

3: Find $\arg\min_{b}{\phi(b)}$ such that $\phi(b)<0$ by binary search.

4: $u\leftarrow\boldsymbol{x}(e)+\arg\min_{b}\phi(b)-1$.

5: Find $\arg\min_{b}{\psi(b)}$ such that $\psi(b)<0$ by binary search.

6: $v\leftarrow\boldsymbol{y}(e)-\arg\min_{b}\psi(b)+1$.

7: while $\boldsymbol{x}(e)<\boldsymbol{y}(e)$ do

8:
$\sigma\leftarrow\max(\lfloor\frac{\boldsymbol{y}(e)-\boldsymbol{x}(e)}{2}\rfloor,1)$

9: $\alpha\leftarrow f(\sigma\boldsymbol{\chi}_{e}|\boldsymbol{x})$ and
$\beta\leftarrow f(-\sigma\boldsymbol{\chi}_{e}|\boldsymbol{y})$

10: if $\beta\leq 0$ then

11: $\boldsymbol{x}(e)\leftarrow\boldsymbol{x}(e)+\sigma$

12: else if $\alpha\leq 0$ then

13: $\boldsymbol{y}(e)\leftarrow\boldsymbol{y}(e)-\sigma$

14: else

15: Randomly update $\boldsymbol{x}(e)\leftarrow\boldsymbol{x}(e)+\sigma$ or
$\boldsymbol{y}(e)\leftarrow\boldsymbol{y}(e)-\sigma$; the former case occurs
with probability $\frac{\alpha}{\alpha+\beta}$, the later case with the
probability $\frac{\beta}{\alpha+\beta}$.

16: end if

17: end while

18: if $\boldsymbol{x}(e)\geq u$ then

19: $\boldsymbol{x}(e)\leftarrow u$, $\boldsymbol{y}(e)\leftarrow u$

20: end if

21: if $\boldsymbol{y}(e)\leq v$ then

22: $\boldsymbol{y}(e)\leftarrow v$, $\boldsymbol{x}(e)\leftarrow v$

23: end if

24: end for

25: return $\boldsymbol{x}$

The algorithm starts with two vectors, $x=\boldsymbol{0}$ and
$y=\boldsymbol{c}$. For each coordinate $e\in E$ it iteratively either
increase ${\textbf{x}}(e)$ or decrease ${\textbf{y}}(e)$ by $\sigma$, which
depends on the marginal gain by adding $\sigma$ to ${\textbf{x}}(e)$ and the
marginal gain by removing $\sigma$ to ${\textbf{y}}(e)$. This procedure
continues until ${\textbf{x}}(e)={\textbf{y}}(e)$. Then it moves on to work on
the next coordinate, after x and y agrees on all coordinates $e\in E$,
${\textbf{x}}={\textbf{y}}$, and the vector is the output of the algorithm.
Different from applying the double greedy algorithm directly, which tightens
the gap one unit per step, algorithm 1 tightens it by half in each iteration.
The binary search nature of this algorithm guarantees that the number of
iterations needed is a logarithm of $B$. Next let us firstly give a few
results based on the diminish return property, which will be used in proving
the theoretical guarantee of the algorithm later.

###### Lemma 3

For $\forall\boldsymbol{x}\leq\boldsymbol{y},k\geq 1,k\in\mathbb{Z}^{+}$, and
the value of $k$ does not violate the integer bound. We have

$\displaystyle f(\boldsymbol{x}+k\boldsymbol{\chi}_{e})-f(\boldsymbol{x})\geq
f(\boldsymbol{y}+k\boldsymbol{\chi}_{e})-f(\boldsymbol{y})$

###### Proof

By the definition of DR-submodular, we have

$\displaystyle\begin{aligned}
f(\boldsymbol{x}+\boldsymbol{\chi}_{e})-f(\boldsymbol{x})&\geq
f(\boldsymbol{y}+\boldsymbol{\chi}_{e})-f(\boldsymbol{y})\\\
f(\boldsymbol{x}+2\boldsymbol{\chi}_{e})-f(\boldsymbol{x}+\boldsymbol{\chi}_{e})&\geq
f(\boldsymbol{y}+2\boldsymbol{\chi}_{e})-f(\boldsymbol{y}+\boldsymbol{\chi}_{e})\\\
&\vdots\\\
f(\boldsymbol{x}+k\boldsymbol{\chi}_{e})-f(\boldsymbol{x}+(k-1)\boldsymbol{\chi}_{e})&\geq
f(\boldsymbol{y}+k\boldsymbol{\chi}_{e})-f(\boldsymbol{y}+(k-1)\boldsymbol{\chi}_{e})\end{aligned}$

Sum up the above inequalities, the lemma holds. ∎

Note that based upon lemma 3, we have

$\displaystyle\begin{aligned}
\alpha+\beta=f(\boldsymbol{x}+\sigma\boldsymbol{\chi}_{e})-f(\boldsymbol{x})-(f(\boldsymbol{y}+\sigma\boldsymbol{\chi}_{e})-f(\boldsymbol{y}))\geq
0\end{aligned}$ (13)

###### Lemma 4

For $\forall\boldsymbol{x}\leq\boldsymbol{y},k\geq 1,k\in\mathbb{Z}^{+}$,
$k\leq\boldsymbol{x}(e)$, we have

$\displaystyle f(\boldsymbol{x}-k\boldsymbol{\chi}_{e})-f(\boldsymbol{x})\leq
f(\boldsymbol{y}-k\boldsymbol{\chi}_{e})-f(\boldsymbol{y})$

Lemma 4 can be easily obtained from lemma 3.

###### Lemma 5

Given $p\leq q$, $p,q\in Z^{+}$, if
$f(\boldsymbol{\chi}_{e}|\boldsymbol{x}+(q-1)\boldsymbol{\chi}_{e})\geq 0$,
then

$\displaystyle 0\leq f(p\boldsymbol{\chi}_{e}|\boldsymbol{x})\leq
f(q\boldsymbol{\chi}_{e}|\boldsymbol{x})$

###### Proof

$\displaystyle\begin{aligned}
f(p\boldsymbol{\chi}_{e}|\boldsymbol{x})=f(\boldsymbol{\chi}_{e}|\boldsymbol{x})+f(\boldsymbol{\chi}_{e}|\boldsymbol{x}+\boldsymbol{\chi}_{e})+\dots+f(\boldsymbol{\chi}_{e}|\boldsymbol{x}+(p-1)\boldsymbol{\chi}_{e})\\\
f(q\boldsymbol{\chi}_{e}|\boldsymbol{x})=f(\boldsymbol{\chi}_{e}|\boldsymbol{x})+f(\boldsymbol{\chi}_{e}|\boldsymbol{x}+\boldsymbol{\chi}_{e})+\dots+f(\boldsymbol{\chi}_{e}|\boldsymbol{x}+(q-1)\boldsymbol{\chi}_{e})\end{aligned}$

Since the values of the terms in the above equations are non-increasing from
left to right,
$f(\boldsymbol{\chi}_{e}|\boldsymbol{x}+(q-1)\boldsymbol{\chi}_{e})\geq 0$, so
all terms are greater than or equal to 0. And
$f(q\boldsymbol{\chi}_{e}|\boldsymbol{x})$ has more terms, so the lemma
holds.∎

We can obtain a similar property in terms of the vector $\boldsymbol{y}$.

###### Lemma 6

Given $p\leq q$, $p,q\in Z^{+}$, if
$f(-\boldsymbol{\chi}_{e}|\boldsymbol{y}-(q-1)\boldsymbol{\chi}_{e})\geq 0$,
then

$\displaystyle 0\leq f(-p\boldsymbol{\chi}_{e}|\boldsymbol{y})\leq
f(-q\boldsymbol{\chi}_{e}|\boldsymbol{y})$

The rest of this section is devoted to proving that Algorithm 1 provides an
approximation ratio of $1/2$ for DR-submodular maximization. Let us begin the
analysis of Algorithm 1 with the introduction of some notation. Let
$\boldsymbol{x}_{i}^{e}$ and $\boldsymbol{y}_{i}^{e}$ be random variables
denoting the vectors generated by the algorithm at the end of the i-th
iteration for coordinate $e$, let the number of iterations for coordinate $e$
is $\theta_{e}$, note that $1\leq i\leq\theta_{e}\leq\log B$. Denote by
$\boldsymbol{opt}$ the optimal solution. Let us define the following random
variable:
$\boldsymbol{opt}_{i}^{e}\triangleq(\boldsymbol{opt}\lor\boldsymbol{x}_{i}^{e})\land\boldsymbol{y}_{i}^{e}$.
Note that $\boldsymbol{x}_{0}^{e}(e)=0$, $\boldsymbol{y}_{0}^{e}(e)=B$, and
$\boldsymbol{opt}_{0}^{e}(e)=\boldsymbol{opt}(e)$. Additionally, the following
always holds:
$\boldsymbol{opt}_{\theta_{e}}^{e}(e)=\boldsymbol{x}_{\theta_{e}}^{e}(e)=\boldsymbol{y}_{\theta_{e}}^{e}(e)$,
$\forall e\in E$.

Let us analyze the approximation ratio of the randomized algorithm. We
consider the subsequence
$\mathbb{E}[f(\boldsymbol{opt}_{0}^{e})],\dots,\mathbb{E}[f(\boldsymbol{opt}_{\theta_{e}}^{e})]$
for any dimension $e\in E$, and a whole sequence which is a combination of
every such subsequence for each element $e\in E$. This sequence starts with
$f(\boldsymbol{opt})$ and ends with the expected value of the algorithm’s
output. The following lemma upper bounds the loss between every two
consecutive elements in the sequence. Formally,
$\mathbb{E}[f(\boldsymbol{opt}_{i-1}^{e})-f(\boldsymbol{opt}_{i}^{e})]$ is
upper bounded by the average expected change in the value of the two solutions
maintained by the algorithm, i.e.,
$\frac{1}{2}\mathbb{E}[f(\boldsymbol{x}_{i}^{e})-f(\boldsymbol{x}_{i-1}^{e})+f(\boldsymbol{y}_{i}^{e})-f(\boldsymbol{y}_{i-1}^{e})]$.

###### Lemma 7

For every $1\leq i\leq\theta_{e}$,

$\displaystyle\mathbb{E}[f(\boldsymbol{opt}_{i-1}^{e})-f(\boldsymbol{opt}_{i}^{e})]\leq\frac{1}{2}\mathbb{E}[f(\boldsymbol{x}_{i}^{e})-f(\boldsymbol{x}_{i-1}^{e})+f(\boldsymbol{y}_{i}^{e})-f(\boldsymbol{y}_{i-1}^{e})]$
(14)

where expectations are taken over the random choices of the algorithm.

###### Proof

Notice that it suffices to prove the inequality conditioned on any event of
the form $\boldsymbol{x}_{i-1}^{e}=\boldsymbol{s}_{i-1}^{e}$, where
$\boldsymbol{s}_{i-1}^{e}\in\mathbb{Z_{+}^{E}}$, for which the probability
that $\boldsymbol{x}_{i-1}^{e}=\boldsymbol{s}_{i-1}^{e}$ is nonzero. Hence,
fix such an event corresponding to an integer vector
$\boldsymbol{s}_{i-1}^{e}$. The rest of the proof implicitly assumes
everything is conditioned on this event. Since the analysis is same for every
coordinate, we omit the superscript $e$ in $x_{i}^{e},y_{i}^{e},s_{i}^{e}$ and
$opt_{i}^{e}$ in the following proof. After an iteration $i$ on coordinate
$e$, denote by $\delta_{i}$ the distance between $x_{i}(e)$ and $y_{i}(e)$,
which can be calculate as
$\delta_{i}=y_{i}(e)-x_{i}(e)=B-\sum_{k=1}^{i}\sigma_{k}$. The parameter
$\sigma_{i}$ can be obtained iteratively as
$\sigma_{1}=\lfloor\frac{B}{2}\rfloor$,
$\sigma_{i}=\lfloor\frac{B-\sum_{k=1}^{i-1}\sigma_{k}}{2}\rfloor=\lfloor\frac{\delta_{i}}{2}\rfloor$.
Due to the conditioning, the following random variables become constants:

  1. 1.

$\boldsymbol{y}_{i-1}$, where
$\boldsymbol{y}_{i-1}(e)=\boldsymbol{s}_{i-1}(e)+\delta_{i-1}$

  2. 2.

$\boldsymbol{opt}_{i-1}\triangleq(\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1}$,
where
$\boldsymbol{opt}_{i-1}(e)=\boldsymbol{s}_{i-1}(e)+\min(\boldsymbol{opt}(e)-\boldsymbol{s}_{i-1}(e),\delta_{i-1})$

  3. 3.

$\alpha_{i}$ and $\beta_{i}$, which refer to $\alpha,\beta$ at the iteration
$i$ .

By Lemma 3, $\alpha_{i}+\beta_{i}\geq 0$. Thus at most one of $\alpha_{i}$ and
$\beta_{i}$ is strictly less than zero. We need to consider the following
three cases for the value of $\alpha_{i}$ and $\beta_{i}$:

Case 1: ($\alpha_{i}\geq 0$ and $\beta_{i}\leq 0$). In this case the vector
$\boldsymbol{y}$ does not change: $\boldsymbol{y}_{i}=\boldsymbol{y}_{i-1}$.
The vector $\boldsymbol{x}$ changes.
$\boldsymbol{x}_{i}\leftarrow\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e}$.
Hence, $f(\boldsymbol{y}_{i})-f(\boldsymbol{y}_{i-1})=0$. Also, by our
definition
$\boldsymbol{opt}_{i}\triangleq(\boldsymbol{opt}\lor\boldsymbol{x}_{i})\land\boldsymbol{y}_{i}=(\boldsymbol{opt}\lor(\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e}))\land\boldsymbol{y}_{i}$.
Thus, we are left to prove that

$\displaystyle
f((\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1})-f((\boldsymbol{opt}\lor(\boldsymbol{x}_{i-1}+\sigma_{i}\chi_{e}))\land\boldsymbol{y}_{i})$
$\displaystyle\leq\frac{1}{2}[f(\boldsymbol{x}_{i})-f(\boldsymbol{x}_{i-1})]=\frac{\alpha_{i}}{2}$
(15)

We prove it considering the relationship among $\boldsymbol{x}_{i-1}(e)$,
$\boldsymbol{x}_{i}(e)$ and $\boldsymbol{opt}_{i}(e)$.

Case 1.1:
$\boldsymbol{x}_{i}(e)=\boldsymbol{s}_{i-1}(e)+\sigma_{i}\leq\boldsymbol{opt}(e)$.

This condition implies $\boldsymbol{x}_{i-1}(e)\leq\boldsymbol{opt}(e)$. Since
$\boldsymbol{y}_{i}=\boldsymbol{y}_{i-1}$, the left-hand side of the
inequality (15) is 0, which is definitely not greater than the nonnegative
$\frac{\alpha_{i}}{2}$.

Case 1.2: $\boldsymbol{s}_{i-1}(e)\geq\boldsymbol{opt}(e)$.

This condition implies that
$\boldsymbol{x}_{i}(e)=\boldsymbol{s}_{i-1}(e)+\sigma_{i}>\boldsymbol{opt}(e)$.

We can see that
$(\boldsymbol{opt}\lor(\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e}))\land\boldsymbol{y}_{i}=(\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e}=\boldsymbol{opt}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e}\leq\boldsymbol{y}_{i-1}$,
by diminish return submodularity we have

$\displaystyle\begin{aligned}
f((\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1})-f((\boldsymbol{opt}\lor(\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e}))\land\boldsymbol{y}_{i})\\\
=f(-\sigma_{i}\boldsymbol{\chi}_{e}|\boldsymbol{opt}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e})\leq
f(-\sigma_{i}\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i-1})=\beta\leq
0\leq\frac{\alpha_{i}}{2}\end{aligned}$

Case 1.3: $\boldsymbol{s}_{i-1}(e)\leq\boldsymbol{opt}(e)$ and
$\boldsymbol{x}_{i}(e)=\boldsymbol{s}_{i-1}(e)+\sigma_{i}>\boldsymbol{opt}(e)$.

Then we have

$\displaystyle((\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1})-(\boldsymbol{opt}\lor(\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e})\land\boldsymbol{y}_{i})=-(\boldsymbol{s}_{i-1}(e)+\sigma_{i}-\boldsymbol{opt}(e))\boldsymbol{\chi}_{e}$

Let $\boldsymbol{s}_{i-1}(e)+\sigma_{i}-\boldsymbol{opt}(e)=\delta$, then

$\displaystyle((\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1})-(\boldsymbol{opt}\lor(\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e})\land\boldsymbol{y}_{i})=-\delta\boldsymbol{\chi}_{e}.$

And

$\displaystyle\begin{aligned}
&f((\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1})-f((opt\lor(\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e}))\land\boldsymbol{y}_{i})\\\
=&f(-\delta\boldsymbol{\chi}_{e}|(\boldsymbol{opt}\lor(\boldsymbol{x}_{i-1}+\sigma_{i}\chi_{e}))\land\boldsymbol{y}_{i})\\\
=&f(-\delta\boldsymbol{\chi}_{e}|\boldsymbol{opt}_{i}).\end{aligned}$ (16)

By the definition of the random variable $\boldsymbol{opt}_{i}$, we have

$\displaystyle\boldsymbol{x}_{i}\leq\boldsymbol{opt}_{i}\leq\boldsymbol{y}_{i}$

Note that $0\leq\delta<\sigma_{i}$. Since
$\psi(b):=f(-\boldsymbol{\chi}_{e}|\boldsymbol{y}-b\boldsymbol{\chi}_{e})$ is
a non-increasing function on b.
$f(-\sigma_{i}\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i})\leq 0$ implies
$f(-\delta\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i}-\sigma_{i}\boldsymbol{\chi}_{e})\leq
0$. We note that in the $i$the iteration,
$\boldsymbol{y}_{i}=\boldsymbol{y}_{i-1}$ and due to the condition of case
1.3, we have
$\boldsymbol{y}_{i}-\sigma_{i}\boldsymbol{\chi}_{e}\geq\boldsymbol{opt}_{i}$,
thus $f(-\delta\boldsymbol{\chi}_{e}|\boldsymbol{opt}_{i})\leq
f(-\delta\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i}-\sigma_{i}\boldsymbol{\chi}_{e})\leq
0\leq\frac{\alpha_{i}}{2}$.

Case 2: ($\alpha_{i}<0$ and $\beta_{i}>0$).This case is analogous to the
previous one, and therefore we omit its proof.

Case 3: ($\alpha_{i}\geq 0$ and $\beta_{i}>0$). With probability
$\frac{\alpha_{i}}{\alpha_{i}+\beta_{i}}$ the following events happen:
$\boldsymbol{x}_{i}\leftarrow\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e}$
and $\boldsymbol{y}_{i}\leftarrow\boldsymbol{y}_{i-1}$; while with probability
$\frac{\beta_{i}}{\alpha_{i}+\beta_{i}}$ the following events happen:
$x_{i}\leftarrow\boldsymbol{x}_{i-1}$ and
$\boldsymbol{y}_{i}\leftarrow\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e}$
Thus,

$\displaystyle\begin{aligned}
\mathbb{E}[f(\boldsymbol{x}_{i})-f(\boldsymbol{x}_{i-1})+f(\boldsymbol{y}_{i})-f(\boldsymbol{y}_{i-1})]&=\frac{\alpha_{i}}{\alpha_{i}+\beta_{i}}[f(\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e})-f(\boldsymbol{x}_{i-1})]\\\
&+\frac{\beta_{i}}{\alpha_{i}+\beta_{i}}[f(\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e})-f(\boldsymbol{y}_{i-1})]\\\
&=\frac{\alpha_{i}^{2}+\beta_{i}^{2}}{\alpha_{i}+\beta_{i}}\end{aligned}$ (17)

Next, we upper bound
$\mathbb{E}[f(\boldsymbol{opt}_{i-1})-f(\boldsymbol{opt}_{i})]$.

$\displaystyle\begin{aligned}
&\mathbb{E}[f(\boldsymbol{opt}_{i-1})-f(\boldsymbol{opt}_{i})]\\\
=&\frac{\alpha_{i}}{\alpha_{i}+\beta_{i}}[f((\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1})-f((\boldsymbol{opt}\lor(\boldsymbol{x}_{i-1}+\sigma_{i}\boldsymbol{\chi}_{e}))\land\boldsymbol{y}_{i})]\\\
&+\frac{\beta_{i}}{\alpha_{i}+\beta_{i}}[f((\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1})-f((\boldsymbol{opt}\lor\boldsymbol{x}_{i})\land(\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e}))]\\\
\leq&\frac{\alpha_{i}\beta_{i}}{\alpha_{i}+\beta_{i}}\end{aligned}$ (18)

The final inequality follows by considering two cases. The first case is:
$\boldsymbol{y}_{i}(e)=\boldsymbol{y}_{i-1}(e)-\sigma_{i}$,
$\boldsymbol{x}_{i}(e)=\boldsymbol{x}_{i-1}(e)$, the first term of the left-
hand side of the last inequality equals zero. There are three subcases,

Case 3.1:
$(\boldsymbol{x}_{i}(e)\leq\boldsymbol{y}_{i}(e)=\boldsymbol{y}_{i-1}(e)-\sigma_{i}<\boldsymbol{y}_{i-1}(e)\leq\boldsymbol{opt}(e))$.

Thus
$(\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1}=(\boldsymbol{opt}\lor\boldsymbol{x}_{i})\land(\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e})+\sigma_{i}\boldsymbol{\chi}_{e}$,
and
$(\boldsymbol{opt}\lor\boldsymbol{x}_{i})\land(\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e})\geq\boldsymbol{x}_{i-1}$,
hence

$\displaystyle\begin{aligned}
&f((\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1})-f((\boldsymbol{opt}\lor\boldsymbol{x}_{i})\land(\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e}))\\\
=&f(\sigma_{i}\boldsymbol{\chi}_{e}|(\boldsymbol{opt}\lor\boldsymbol{x}_{i})\land(\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e}))\leq
f(\sigma_{i}\boldsymbol{\chi}_{e}|\boldsymbol{x}_{i-1})=\alpha_{i}\end{aligned}$

Case 3.2:
$(\boldsymbol{opt}(e)\leq\boldsymbol{y}_{i}(e)=\boldsymbol{y}_{i-1}(e)-\sigma_{i}<\boldsymbol{y}_{i-1}(e))$.

In this case, the second term of the left-hand side of inequality (18) also
equals zero, thus inequality (18) follows.

Case 3.3:
$(\boldsymbol{x}_{i}(e)\leq\boldsymbol{y}_{i}(e)=\boldsymbol{y}_{i-1}(e)-\sigma_{i}\leq\boldsymbol{opt}(e)<\boldsymbol{y}_{i-1}(e))$.

We have
$(\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1}=(\boldsymbol{opt}\lor\boldsymbol{x}_{i})\land(\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e})+(\boldsymbol{opt}(e)-\boldsymbol{y}_{i-1}(e)+\sigma_{i})\boldsymbol{\chi}_{e}$.
Let $\mu=\boldsymbol{opt}(e)-\boldsymbol{y}_{i-1}(e)+\sigma_{i}$, then
$0<\mu\leq\sigma_{i}$, and

$\displaystyle\begin{aligned}
&f((\boldsymbol{opt}\lor\boldsymbol{x}_{i-1})\land\boldsymbol{y}_{i-1})-f((\boldsymbol{opt}\lor\boldsymbol{x}_{i})\land(\boldsymbol{y}_{i-1}-\sigma_{i}\chi_{e}))\\\
=&f(\mu\boldsymbol{\chi}_{e}|(\boldsymbol{opt}\lor\boldsymbol{x}_{i})\land(\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e}))\\\
\leq&f(\mu\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e})\leq
0\leq\alpha_{i}\end{aligned}$

The line 18-23 in the algorithm guarantees that
$f(-\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i-1}-(\sigma-1)\boldsymbol{\chi}_{e}))\geq
0$. By lemma 5, we have
$f(-\sigma\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i-1})\geq 0$. Also
$f(-\mu\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i-1}-(\sigma-\mu)\boldsymbol{\chi}_{e})\geq
0$. Thus,

$\displaystyle\begin{aligned}
f(-\mu\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i-1}-(\sigma-\mu)\boldsymbol{\chi}_{e})=-f(\mu\boldsymbol{\chi}_{e}|\boldsymbol{y}_{i-1}-\sigma_{i}\boldsymbol{\chi}_{e})\geq
0\end{aligned}$

By now, we show that the inequality (18) holds for the case
$\boldsymbol{y}_{i}(e)=\boldsymbol{y}_{i-1}(e)-\sigma_{i}$,
$\boldsymbol{x}_{i}(e)=\boldsymbol{x}_{i-1}(e)$. The other case is that
$\boldsymbol{y}_{i}(e)=\boldsymbol{y}_{i-1}(e)$,
$\boldsymbol{x}_{i}(e)=\boldsymbol{x}_{i-1}(e)+\sigma_{i}$, which is analogous
to the previous case, we omit the proof here.

Now we show inequality (18) follows for all situations. By (17) and (18)
inequality (14) holds if

$\displaystyle\frac{\alpha_{i}\beta_{i}}{\alpha_{i}+\beta_{i}}\leq\frac{1}{2}\cdot\frac{\alpha_{i}^{2}+\beta_{i}^{2}}{\alpha_{i}+\beta_{i}}$

which can easily be verified.

###### Theorem 5.1

Algorithm 1 is a randomized $O(n\log B)$ time (1/2)-approximation algorithm
for the DR-Submodular Maximization problem.

###### Proof

Summing up lemma 6 for every $1\leq i\leq\theta_{e}$ for each $e\in E$ gives

$\displaystyle\begin{aligned} \ &\sum_{e\in
E}\sum_{i=1}^{\theta_{e}}\mathbb{E}[f(\boldsymbol{opt}_{i-1}^{e})-f(\boldsymbol{opt}_{i}^{e})]\\\
\leq&\frac{1}{2}\sum_{e\in
E}\sum_{i=1}^{\theta_{e}}\mathbb{E}[f(\boldsymbol{x}_{i}^{e})-f(\boldsymbol{x}_{i-1}^{e})+f(\boldsymbol{y}_{i}^{e})-f(\boldsymbol{y}_{i-1}^{e})]\end{aligned}$
(19)

The above sum is telescopic. We define that the algorithm executes on the
vector coordinates ordered by $e_{1},\dots,e_{n}$. Collapse the inequality, we
get

$\displaystyle\begin{aligned}
f(\boldsymbol{opt}_{0}^{e_{1}})-f(\boldsymbol{opt}_{\theta_{e}}^{e_{n}})&\leq\frac{1}{2}\mathbb{E}[f(\boldsymbol{x}_{\theta_{e_{n}}}^{e_{n}})-f(\boldsymbol{x}_{0}^{e_{1}})+f(\boldsymbol{y}_{\theta_{e_{n}}}^{e_{n}})-f(\boldsymbol{y}_{0}^{e_{1}})]\\\
&\leq\frac{1}{2}\mathbb{E}[f(\boldsymbol{x}_{\theta_{e_{n}}}^{e_{n}})+f(\boldsymbol{y}_{\theta_{e_{n}}}^{e_{n}})]\end{aligned}$
(20)

Recalling the definitions of $\boldsymbol{opt}_{i}^{e}$,
$\boldsymbol{opt}_{0}^{e_{1}}=\boldsymbol{opt}$,
$\boldsymbol{opt}_{\theta_{e}}^{e_{n}}=\boldsymbol{x}_{\theta_{e_{n}}}^{e_{n}}=\boldsymbol{y}_{\theta_{e_{n}}}^{e_{n}}$
is the output solution, thus
$\mathbb{E}[f(\boldsymbol{x}_{\theta_{e_{n}}}^{e_{n}})]=\mathbb{E}[f(\boldsymbol{y}_{\theta_{e_{n}}}^{e_{n}})]\geq
f(\boldsymbol{opt})/2$. It is clear that the algorithm makes $O(n\log B)$
oracle calls since for each coordinate $e\in E$ the number of oracle calls is
at most $\log B$ and there are $n=|E|$ coordinates.

##  6 Conclusions

In this paper, we study the non-monotone DR-submodular maximization problem
over bounded integer lattice, and specifically we study a Profit Maximization
problem in social networks and show its DR-submodularity. By theoretically
mining the special property of DR-submodular function, we propose a binary
search double greedy algorithm to the optimization problem. We show algorithm
improves the approximation ratio and significantly reduces the time complexity
compared to the existing results.

## References

  * [1] N. Alon, I. Gamzu, and M. Tennenholtz, “Optimizing budget allocation among channels and influencers,” in _Proceedings of the 21st international conference on World Wide Web_ , 2012, pp. 381–388.
  * [2] C. Gottschalk and B. Peis, “Submodular function maximization on the bounded integer lattice,” in _International Workshop on Approximation and Online Algorithms_. Springer, 2015, pp. 133–144.
  * [3] U. Feige, V. S. Mirrokni, and J. Vondrák, “Maximizing non-monotone submodular functions,” _SIAM Journal on Computing_ , vol. 40, no. 4, pp. 1133–1153, 2011.
  * [4] T. Soma and Y. Yoshida, “A generalization of submodular cover via the diminishing return property on the integer lattice,” _Advances in neural information processing systems_ , vol. 28, 2015.
  * [5] N. Buchbinder, M. Feldman, J. Seffi, and R. Schwartz, “A tight linear time (1/2)-approximation for unconstrained submodular maximization,” _SIAM Journal on Computing_ , vol. 44, no. 5, pp. 1384–1402, 2015.
  * [6] T. Soma and Y. Yoshida, “Non-monotone dr-submodular function maximization,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 31, no. 1, 2017.
  * [7] R. Niazadeh, T. Roughgarden, and J. Wang, “Optimal algorithms for continuous non-monotone submodular and dr-submodular maximization,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [8] A. Bian, K. Levy, A. Krause, and J. M. Buhmann, “Continuous dr-submodular maximization: Structure and algorithms,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [9] T. Soma, N. Kakimura, K. Inaba, and K.-i. Kawarabayashi, “Optimal budget allocation: Theoretical guarantee and efficient algorithm,” in _International Conference on Machine Learning_. PMLR, 2014, pp. 351–359.
  * [10] T. Soma and Y. Yoshida, “Maximizing monotone submodular functions over the integer lattice,” _Mathematical Programming_ , vol. 172, no. 1, pp. 539–563, 2018.
  * [11] Z. Zhang, D. Du, Y. Jiang, and C. Wu, “Maximizing dr-submodular+ supermodular functions on the integer lattice subject to a cardinality constraint,” _Journal of Global Optimization_ , vol. 80, no. 3, pp. 595–616, 2021.
  * [12] L. Lai, Q. Ni, C. Lu, C. Huang, and W. Wu, “Monotone submodular maximization over the bounded integer lattice with cardinality constraints,” _Discrete Mathematics, Algorithms and Applications_ , vol. 11, no. 06, p. 1950075, 2019.
  * [13] A. Sahin, J. Buhmann, and A. Krause, “Constrained maximization of lattice submodular functions,” in _IN: ICML 2020 workshop on Negative Dependence and Submodularity for ML, Vienna, Austria, PMLR_ , vol. 119, 2020.
  * [14] Z. Zhang, L. Guo, Y. Wang, D. Xu, and D. Zhang, “Streaming algorithms for maximizing monotone dr-submodular functions with a cardinality constraint on the integer lattice,” _Asia-Pacific Journal of Operational Research_ , vol. 38, no. 05, p. 2140004, 2021.
  * [15] H. Hassani, M. Soltanolkotabi, and A. Karbasi, “Gradient methods for submodular maximization,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [16] A. Kuhnle, J. D. Smith, V. Crawford, and M. Thai, “Fast maximization of non-submodular, monotonic functions on the integer lattice,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 2786–2795.
  * [17] Q. Nong, J. Fang, S. Gong, D. Du, Y. Feng, and X. Qu, “A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice,” _Journal of Combinatorial Optimization_ , vol. 39, no. 4, pp. 1208–1220, 2020.
  * [18] J. Hartline, V. Mirrokni, and M. Sundararajan, “Optimal marketing strategies over social networks,” in _Proceedings of the 17th international conference on World Wide Web_ , 2008, pp. 189–198.
  * [19] M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” _Journal of the ACM (JACM)_ , vol. 42, no. 6, pp. 1115–1145, 1995.
  * [20] A. A. Ageev and M. I. Sviridenko, “An 0.828-approximation algorithm for the uncapacitated facility location problem,” _Discrete Applied Mathematics_ , vol. 93, no. 2-3, pp. 149–156, 1999.
  * [21] S. O. Gharan and J. Vondrák, “Submodular maximization by simulated annealing,” in _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_. SIAM, 2011, pp. 1098–1116.
  * [22] N. Buchbinder and M. Feldman, “Deterministic algorithms for submodular maximization problems,” _ACM Transactions on Algorithms (TALG)_ , vol. 14, no. 3, pp. 1–20, 2018.
  * [23] X. Pan, S. Jegelka, J. E. Gonzalez, J. K. Bradley, and M. I. Jordan, “Parallel double greedy submodular maximization,” _Advances in Neural Information Processing Systems_ , vol. 27, 2014.
  * [24] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in _Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2003, pp. 137–146.
  * [25] S. Gu, C. Gao, R. Yang, W. Wu, H. Wang, and D. Xu, “A general method of active friending in different diffusion models in social networks,” _Social Network Analysis and Mining_ , vol. 10, no. 1, pp. 1–13, 2020.
  * [26] C. Gao, S. Gu, J. Yu, H. Du, and W. Wu, “Adaptive seeding for profit maximization in social networks,” _Journal of Global Optimization_ , vol. 82, no. 2, pp. 413–432, 2022.
  * [27] C. Gao, S. Gu, R. Yang, H. Du, S. Ghosh, and H. Wang, “Robust profit maximization with double sandwich algorithms in social networks,” in _2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)_. IEEE, 2019, pp. 1539–1548.
  * [28] C. Gao, S. Gu, R. Yang, J. Yu, W. Wu, and D. Xu, “Interaction-aware influence maximization and iterated sandwich method,” _Theoretical Computer Science_ , vol. 821, pp. 23–33, 2020.
  * [29] W. Chen, Y. Wang, and S. Yang, “Efficient influence maximization in social networks,” in _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2009, pp. 199–208.
  * [30] P. Domingos and M. Richardson, “Mining the network value of customers,” in _Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2001, pp. 57–66.
  * [31] Q. Ni, J. Guo, W. Wu, H. Wang, and J. Wu, “Continuous influence-based community partition for social networks,” _IEEE Transactions on Network Science and Engineering_ , vol. 9, no. 3, pp. 1187–1197, 2021.


Table 8: Spectroscopic observations of ASASSN-15hy. JD | UT Date | Phase | Telescope | Instrument | Ref.aa1: Frohmaier et al. 2015; 2: Stahl et al. 2020; 3: this work; 4: Childress et al. 2016.
---|---|---|---|---|---
Optical
2457139.9 | 2015-04-27 |  $-$11.6 | ESO-NTT | EFOSC2 | 1
2457140.0 | 2015-04-27 |  $-$11.4 | Shane | KAST | 2
2457142.2 | 2015-04-29 |  $-$9.3 | NOT | ALFOSC | 3
2457142.2 | 2015-04-29 |  $-$9.2 | ANU | WiFeS | 4
2457146.3 | 2015-05-03 |  $-$5.2 | ANU | WiFeS | 4
2457148.7 | 2015-05-06 |  $-$2.9 | LT | SPRAT | 3
2457150.3 | 2015-05-07 |  $-$1.3 | ANU | WiFeS | 4
2457150.7 | 2015-05-08 |  $-$0.9 | LT | SPRAT | 3
2457151.7 | 2015-05-09 | 0.0 | LT | SPRAT | 3
2457153.7 | 2015-05-11 | 2.0 | LT | SPRAT | 3
2457155.0 | 2015-05-12 | 3.3 | FLWO 1.5m | FAST | 3
2457155.9 | 2015-05-13 | 4.2 | FLWO 1.5m | FAST | 3
2457156.2 | 2015-05-13 | 4.5 | ANU | WiFeS | 4
2457160.9 | 2015-05-18 | 9.1 | FLWO 1.5m | FAST | 3
2457161.9 | 2015-05-19 | 10.1 | FLWO 1.5m | FAST | 3
2457187.0 | 2015-06-13 | 34.7 | Shane | KAST | 2
2457189.5 | 2015-06-16 | 37.2 | Keck-I | LRIS | 2
2457191.1 | 2015-06-17 | 38.7 | NOT | ALFOSC | 3
2457192.0 | 2015-06-18 | 39.6 | Shane | KAST | 2
2457194.9 | 2015-06-21 | 42.5 | FLWO 1.5m | FAST | 3
2457196.9 | 2015-06-23 | 44.5 | Shane | KAST | 2
2457198.2 | 2015-06-24 | 45.7 | ANU | WiFeS | 4
2457205.1 | 2015-07-01 | 52.5 | ANU | WiFeS | 4
2457212.1 | 2015-07-08 | 59.4 | ANU | WiFeS | 4
2457217.9 | 2015-07-14 | 65.1 | Shane | KAST | 2
2457225.5 | 2015-07-22 | 72.5 | du Pont | WFCCD | 3
2457227.9 | 2015-07-24 | 74.9 | Shane | KAST | 2
2457234.9 | 2015-07-31 | 81.8 | ANU | WiFeS | 4
2457252.0 | 2015-08-17 | 98.6 | ANU | WiFeS | 4
2457258.9 | 2015-08-24 | 105.3 | Shane | KAST | 2
2457286.7 | 2015-09-21 | 132.6 | Shane | KAST | 2
2457305.6 | 2015-10-10 | 151.2 | Shane | KAST | 2
2457306.7 | 2015-10-11 | 152.3 | Shane | KAST | 2
2457309.7 | 2015-10-14 | 155.2 | Shane | KAST | 2
Near-infrared
2457143.0 | 2015-04-30 |  $-$8.5 | GN | GNIRS | 3
2457150.1 | 2015-05-07 |  $-$1.5 | GN | GNIRS | 3
2457159.9 | 2015-05-17 | 8.1 | GN | GNIRS | 3
2457174.9 | 2015-06-01 | 22.8 | Baade | FIRE | 3
2457181.7 | 2015-06-08 | 29.5 | GS | F2 | 3
2457224.7 | 2015-07-21 | 71.7 | GS | F2 | 3

##  Appendix B $K$\- and $S$-corrections

In this work, $K$-corrections (Oke & Sandage, 1968) were performed in the
optical $BVri$ bands for all the comparison SNe Ia presented in Section 4.
Note that for SN 2007if and SN 2012dn, the SNIFS absolute-flux-calibrated
spectra (Scalzo et al., 2010; Taubenberger et al., 2019) were used to
calculate the magnitudes by integrating the flux directly under the CSP
Swope+e2v passbands, hence no $K$\- or $S$-corrections were needed. The
$K$-corrections of SN 2007af, SN 2006bt and LSQ12gdj were computed using
SNooPy, which uses the Hsiao templates (Hsiao et al., 2007) for SNe Ia.

For other peculiar 03fg-like objects, such as SN 2006gz, SN 2009dc, and
ASASSN-15pz, the spectral time series of SN 2009dc (Silverman et al., 2011;
Taubenberger et al., 2011), SN 2012dn (Taubenberger et al., 2019), and the
Hsiao normal SN Ia templates (Hsiao et al., 2007) were used as different
options for the assumed SED in order to determine the $K$-corrections and the
corresponding errors. The following procedures were followed for each SN Ia:
(1) warp all the spectral sets (SN 2009dc, SN 2012dn, Hsiao templates, and the
observed spectra of the SN Ia in question) to match the observed photometric
colors of the SN Ia; (2) calculate the $K$-correction using the warped spectra
from the above step; (3) interpolate the $K$-corrections to the photometric
epochs with Gaussian process (Rasmussen & Williams, 2005) and with constant
extrapolation if the desired epoch is outside the covered range; (4) choose
the SED option that produces the smallest $\chi^{2}$ in $K$-correction values
compared to the ones obtained from the observed spectra of the SN Ia in
question, in order to produce the final $K$-correction; and (5) at each
photometric epoch, adopt the standard deviation of the $K$-correction from all
SED options as the final $K$-correction errors. Following the above
procedures, the optimal SED set for SN 2006gz, SN 2009dc, and ASASSN-15pz were
spectral time series of SN 2012dn, SN 2009dc, and SN 2009dc, respectively.

For photometry published in the natural system with known filter response
functions, such as that obtained by the Harvard-Smithsonian Center for
Astrophysics (CfA) Supernova Group (Hicken et al., 2007, 2012), the light
curves are also $S$-corrected to the CSP-II Swope+e2v natural system. For
photometry published in the standard systems, the light curves are left as
published without removing or applying color terms, such as the Las Cumbres
Observatory $BVri$ light curves of ASASSN-15pz from Chen et al. (2019) and the
multi-instrument S-corrected $BV$ light curves of SN 2009dc from Taubenberger
et al. (2011). When computing the $K$-corrections in step 2), the rest-frame
filters were set to be the CSP-II Swope+e2v $BVri$ filters.

The optical spectroscopic data set of ASASSN-15hy are quite complete in time
coverage and rapid in cadence. Thus, it forms the base set of SEDs for the
$K$-correction calculations for ASASSN-15hy. Figure B17 presents the
comparison of $K$-corrections computed with various SED options for
ASASSN-15hy. The different sets of $K$-corrections are similar at early times
but diverge after +10 d past maximum light, especially in the $i$ band where
03fg-like SNe Ia show peculiar light-curve evolution compared to normal SNe
Ia. This divergence is captured in the adopted $K$-correction errors. Among
four 03fg-like objects, SN 2006gz, SN 2009dc, ASASSN-15pz, ASASSN-15hy, the
average adopted $K$-correction error is 0.01 mag. This is on the same level as
the errors attributed to the diversity of spectroscopic features in normal SNe
Ia (Hsiao et al., 2007).

Figure B17: The comparison of $K$-correction estimates for ASASSN-15hy, using
various spectral time series (SN 2009dc, SN 2012dn, Hsiao normal SN Ia
templates, and observed spectra of ASASSN-15hy) as the assumed SED. The final
adopted $K$-correction values and the corresponding errors are also plotted.

##  Appendix C Host-Galaxy Analysis

###  C.1 Integral-field Spectroscopy

The analysis of the MUSE integral-field spectroscopy of the ASASSN-15hy host
is detailed here, while the main results were presented in Section 3.2. First,
the MW extinction-corrected maps of the most prominent emission lines were
constructed. Spectra were then extracted using a 1.6″ diameter aperture,
similar to the FWHM of the observation, and centered at two positions: one at
the brightest nearby host H$\alpha$ structures toward the SE of the SN (marked
as Structure A in the right panel of Fig. 4) and the other at the position of
ASASSN-15hy. A simple stellar populations analysis was performed on these two
spectra and on the integrated global spectrum of the galaxy by summing up the
spectra in all spaxels while accounting for spatial covariance in the error
budget. Several galactic parameters were obtained from the three spectra
including the ongoing SFR determined from the H$\alpha$ emission line, the
ratio of young-to-old populations determined from the H$\alpha$ EW, and the
oxygen abundance (12 + $log_{10}(O/H)$) in both the O3N2 (Marino et al., 2013)
and D16 (Dopita et al., 2016) scales.

The spectrum extracted at the location of ASASSN-15hy has a low S/N with a
very noisy stellar continuum. The Balmer H$\alpha$ and $H\beta$ lines were
detected, and they indicate the presence of gas ionized by ongoing star
formation at that location. This location show subsolar oxygen abundance
implied by both O3N2 and D16 calibrators and relatively high sSFR. From the
spectrum extracted at the location of Structure A, the oxygen abundance is
substantially subsolar. The oxygen line at $\lambda$5007 is as bright as
H$\alpha$, pointing to very low metal content. This is supported by the
location of the line ratios in the BPT diagram (Baldwin et al., 1981), falling
below the Kewley et al. (2001) demarcation line at the edge where low-
metallicity regions fall, similar to the host of LSQ14fmg (Hsiao et al.,
2020). The H$\alpha$EW of Structure A is relatively high, indicating a
significant contribution from populations as young as $\sim$10 Myr (See
Kuncarayakti et al. 2018 for example). Regarding global properties, we found a
SFR of 0.048 $\pm$ 0.007 M⊙ yr-1 and a stellar mass of (0.77 $\pm$ 0.16)
$\times$ 109 M⊙, corresponding to a log10(sSFR) of $-$10.21 $\pm$ 0.31 yr-1.
The global spectrum also yielded relatively high H$\alpha$EW and low subsolar
oxygen abundances in both the O3N2 and D16 calibrators. As discussed in
Section 3.2, such low-mass and low-metallicity host environment are typical
for the 03fg-like SNe. Analysis with a larger sample are underway (L. Galbany
et al, in preparation).

###  C.2 Detection Limit of Na i D

A detection limit of EW $\leq$ 0.1 Å was estimated using the WiFeS spectrum
taken on 2015 May 13, selected for its relatively high resolution and S/N.
Here, we outline the procedures for estimating the detection limit. First, an
idealized spectrum was created by Gaussian smoothing and oversampling the
observed WiFeS spectrum. Artificial absorption lines with varying depths and
widths, simulating the narrow Na i D absorptions, were then added to the
idealized spectrum. The resolution was degraded to match the resolution of
WiFeS with the R3000 grating. The spectrum was then resampled at the same
wavelength grid as the observed WiFeS spectrum. Finally, random flux noise was
added using the uncertainties measured from the observed spectrum.

The strength of the simulated Na i D absorption was decreased until the EW
measured from the degraded spectrum was on the same level as the $1\sigma$ EW
measurement error determined through 100 realizations of degraded spectra. The
EW measured using the corresponding idealized spectrum is then taken as the
detection limit. We estimated for ASASSN-15hy that the Na i D EW is 0.0 $\pm$
0.1 Å. Note that the derived detection limit is robust against varying width
of the simulated Na i D absorption, as well as resolution further degraded by
seeing, for example, by a factor of 2.

###  C.3 Comparisons of Spectral Energy Distribution

Figure C18: The host-galaxy extinction simulation of ASASSN-15hy by matching
the SED to SN 2009dc (top row, using $Swift$ $uvm2~{}u$ and CSP $uBgVri$
bands) and ASASSN-15pz (bottom row, using $Swift$ $uvm2~{}u$ and Las Cumbres
Observatory $BVri$ bands). The left-hand panels of each row show the averaged
NRMSE between the reference SED and simulated SED of ASASSN-15hy with
corresponding extinction parameters, ratio $R_{V}$ and color excess $E(B-V)$,
ranging from 0.1 to 6.0 and 0.01 to 0.04 mag respectively. Note that it would
require unusually high UV flux if ASASSN-15hy were to have a similar flux as
SN 2009dc/ASASSN-15pz in the optical.

By comparing the SED (covering from $\sim$2000 to $\sim$8000 Å) of ASASSN-15hy
to those of well-studied 03fg-like SNe, we further investigate whether the
relative faintness of ASASSN-15hy in the optical is due to host-galaxy
extinction. SN 2009dc (Taubenberger et al., 2011; Krisciunas et al., 2017) and
ASASSN-15pz (Chen et al., 2019) were chosen for this test due to their
similarity in spectroscopic properties with ASASSN-15hy and the availability
of photometry in the UV. They have host color excess $E(B-V)$ values of 0.1
(Taubenberger et al., 2011) and 0.0 mag (Chen et al., 2019), determined by the
EW of Na i D, from the corresponding literature. The SED of ASASSN-15hy is
extinction and reddening “corrected” to match those of SN 2009dc and
ASASSN-15pz. The best matching extinction parameters, $R_{V}$ and $E(B-V)$,
were selected by locating the minimum of the averaged Normalized Root Mean
Square Error (NRMSE) between the comparison SEDs over the selected four epochs
presented in Fig. C18. Note that the weight of the $uvm2$ was set to 0.05 when
calculating the NRMSE to avoid bias due to the significant extinction in the
UV.

Unusually high intrinsic UV flux would be required for ASASSN-15hy if it is to
match the overall SED of the reference SNe, especially in the optical region,
with the best-fit $R_{V}$ and $E(B-V)$. The derived intrinsic SED of
ASASSN-15hy has an average of 2 and 5 times of the flux in the $uvm2$ band
compared to those of SN 2009dc and ASASSN-15pz respectively, which translates
to $\sim$0.8 and $\sim$1.7 mag brighter in magnitudes. Such high UV flux is
not likely as SN 2009dc and ASASSN-15pz are already UV bright compared to
normal SNe Ia (Taubenberger et al., 2011; Brown et al., 2014b; Chen et al.,
2019). Given the above result from the SED extinction test and the minimal
extinction derived from the nondetection of Na i D, we suggest that the
apparent differences in the SEDs are intrinsic to the SNe or their immediate
surrounding environment.

##  Appendix D Model Selection in the Core Degenerate Scenario

In the context of the CD scenario, we explain how the photometric and spectral
properties of ASASSN-15hy translate to our chosen model parameters in details
in this section, with the main results summarized in Section 6. Our goal is to
show how we obtain our best fit model parameters and not to present an overall
model grid for the CD scenario. In a star undergoing a common-envelope phase,
we would expect that the hydrogen envelope is most stripped. We note however,
that every AGB star removes its envelope in the final stages such that it
forms a naked C/O core that later is seen as a white dwarf. One of the goals
of this investigation is to probe for the ignition mechanism in ASASSN-15hy.

###  D.1 Model Construction and Free Parameters

In this work, we use the parameterized framework of spherical envelope models
(Hoeflich & Khokhlov, 1996) and make use of the spectral evolution of elements
and photometric properties to constrain model parameters. Similar models were
presented for the 03fg-like object LSQ14fmg (Hsiao et al., 2020). Here we list
the main parameters and selection criteria as mentioned in Section 6. The main
parameters are:

  1. 1.

the mass of the nondegenerate envelope $M_{\text{env}}$,

  2. 2.

the radius of the nondegenerate envelope $R_{\text{env}}$,

  3. 3.

the size of the He and C layers in mass and velocity space,

  4. 4.

the initial metallicity $Z$,

  5. 5.

the mass of the hydrostatic (possibly rotating) core; referred to as the core
mass, $M_{\text{core}}$,

  6. 6.

the amount of mass burnt in the deflagration phase, $M_{\text{defl}}$ or the
transition density from the deflagration to detonation burning
$\rho_{\text{tr}}$,

  7. 7.

possible interaction with the nearby environment or wind.

The parameters of the presented models are determined by the observational
constraints. The primary selection criteria allow us to determine the model
parameter based on the observation properties are:

  1. 1.

$M_{\text{env}}$ determines the final “shell” velocity indicated by the $Si$
line region formed in quasi statistical equilibrium (QSE; Hoeflich & Khokhlov
1996; Quimby et al. 2007),

  2. 2.

$R_{\text{env}}$ determines the width of the shell. With increasing radius,
the shell becomes more confined in velocity space (Fig. D19),

  3. 3.

$M_{\text{core}}$ determines the diffusion time scales, therefore, the rise
time to maximum light (Hoeflich & Khokhlov, 1996; Shen & Moore, 2014; Dessart
et al., 2014). The detonation in a sub-$M_{\text{Ch}}$ ($\sim$1$M_{\odot}$)
model produces a rise time that is too short, and models with $1.8M_{\odot}$
produces one that is too long by several days. The best agreement was found
with a model of 1.47 $M_{\odot}$ that puts ASASSN-15hy near but over
$M_{\text{Ch}}$.

The secondary selection criteria in the case of DCD are: $\rho_{\text{tr}}$ or
$M_{\text{defl}}$ which regulates the 56Ni production and therefore the
luminosity, if all other parameters are kept the same, as in the classical
delayed detonation models (e.g., Hoeflich et al., 2002). Note that in general
within the CD scenario, Z and the relative amount of $M_{\text{He}}$ controls
the color $B-V$, the UV and NIR flux, and the CO-formation.

###  D.2 Structure of the Explosion Models

For the simulations, we used our HYDrodynamical RAdiation code (HYDRA) which
utilizes a nuclear network of 218 isotopes during the early phases of the
explosion and detailed, time-dependent non-LTE models for atomic level
populations and diatomic molecules (Sharp & Hoeflich, 1990; Hoeflich et al.,
1995), including $\gamma$\- and positron transport and radiation-hydrodynamics
to calculate LCs and spectra (Höflich, 2003; Penney & Hoeflich, 2014; Hoeflich
et al., 2017). Here, 912 to 1812 depth points are used. For possible
interaction, a recent module is used based on the work presented in Gerardy et
al. (2007); Dragulin & Hoeflich (2016), and Hsiao et al. (2020), covering a
larger parameter space than existing published models (Hoeflich & Khokhlov,
1996; Hsiao et al., 2020). The ranges covered are $1.2~{}M_{\odot}\leq
M_{\text{core}}\leq 1.8~{}M_{\odot}$, where we assume that the rotationally
supported degenerate core follows the solutions of Yoon & Langer (2005);
$0.01~{}M_{\odot}\leq M_{\text{env}}\leq 0.8$ $M_{\odot}$;
$5~{}R_{\text{core}}\leq R_{\text{env}}\leq 250~{}R_{\text{core}}$;
$10^{-10}~{}Z_{\odot}\leq Z\leq 1~{}Z_{\odot}$. The metallicity range is
chosen to cover the range from extreme Population III to Population I stars.
Only the baseline and best matching model are presented here, but the entire
set of models will be discussed and applied to analyze a sample of 03fg-like
SNe Ia in future work.

Although the elemental contribution of a specific feature changes with time,
we use the models to identify the velocity range in which specific elements
are present. Note that the model parameters have not been fine-tuned, and that
Rayleigh-Taylor instabilities are suppressed in spherical models, but may
smear-out the edges in velocity space by about $1{,}000$ km s-1. The baseline
model (DCD07) has the following parameters: $M_{\text{env}}=0.7~{}M_{\odot}$,
$R_{\text{env}}=10~{}R_{\text{core}}$, $M_{\text{He,env}}=0.1~{}M_{\odot}$,
$M_{\text{core}}=1.47~{}M_{\odot}$, $Z=10^{-10}~{}Z_{\odot}$,
$M_{\text{defl}}=0.42~{}M_{\odot}$, and the total 56Ni mass $=$
$0.87~{}M_{\odot}$. The resulting density and abundance structures are shown
in Fig. D19.

The overall structure consists of a central core of nuclear statistical
equilibrium (NSE) burning products, layers of IME produced by explosive O
burning (Si/S & Ca) and explosive C burning (Mg, Ne, O), and outer unburned
C/O and He layers originating from the initial structure. As usual in this
class of models, the presence of a nondegenerate envelope results in the
compression in velocity space of all burning layers (Hoeflich & Khokhlov,
1996; Quimby et al., 2007).

Two peculiarities of the baseline model are: (1) the lack of a pronounced
density shell when compared to a more typical envelope model or the large-
amplitude pulsating delayed-detonation (DDT) models (Hoeflich & Khokhlov,
1996; Quimby et al., 2007; Hoeflich et al., 2017; Hsiao et al., 2020), and (2)
that parts of the C/O envelope undergo burning. Both are a direct consequence
of the small $R_{\text{env}}$ of $10~{}R_{\text{core}}$ rather than an
extended envelope with e.g. $100~{}R_{\text{core}}$ (see Fig. D19). Typically,
an exploding WD reaches the initial stage of free expansion after about 10 to
20 seconds. However, in DCD07, the compact shell gets overrun by the ejecta
within 1 to 2 seconds. Thus, a new pressure equilibrium between the shell and
the inner material can be reached leading to a very shallow density shell-like
feature between 0.7 and 1.4 $M_{\odot}$ (see the left panels of Fig. D19).
Moreover, the large envelope mass $M_{\text{env}}$, combined with the early
interaction and lack of geometrical dilution of the ejecta, results in
sufficiently high densities and peak temperature in the inner layers of the
shell for explosive C burning (producing O, Ne, and Mg) to take place (see the
right panels of Fig. D19). In the model DCD07, the NSE, QSE and explosive
C-burning products are below $7{,}500$ km s-1, $6{,}500-14{,}000$ km s-1, and
$8{,}200-14{,}500$ km s-1, respectively. The S velocity range is shifted
relative to Si by $\approx-500$ and $-1{,}000$ km s-1 at the inner and outer
edges of explosive O burning, when the transitions to NSE and C-burning occur,
respectively.

In this model, very limited He burning, below the abundance level of
$10^{-3}$, takes place via helium capture on carbon,
12C($\alpha,\gamma)^{16}$O, which also occurs during normal helium burning.
For models with similar parameters but smaller $M_{\text{env}}$, larger
$M_{\text{He}}$, or smaller $R_{\text{env}}$, explosive He burning can lead to
an increased outer abundance of NSE, QSE, and explosive C-burning products at
high velocities, as is seen in some sub-$M_{\text{Ch}}$ or
$M_{\text{Ch}}$-mass models with He-donors (Nomoto, 1982; Hoeflich & Khokhlov,
1996; Shen & Moore, 2014; Hoeflich et al., 2019). Corollary models with the
same parameters as DCD07 but with a larger $R_{\text{env}}$ produce very few
products of explosive C burning (lower right panel of Fig. D19) compared to
our model that shows more O/Ne/Mg (upper-right panel of Fig. D19).666Note that
$M_{\text{He}}$ can be slightly lower than $0.1~{}M_{\odot}$ without changing
the discussion above. However, more C/O would result in an earlier onset of CO
formation at $\approx 180$ d in this model.

Figure D19: Structure of the DCD07 envelope model for ASASSN-15hy (upper
panels) and, for comparison, a model with the same parameters but an envelope
25 times its size (lower panels). The density and velocity structure is given
as a function of mass (left panels), and the abundances of the $\alpha$
elements are given as a function of velocity (right panels). The model with
the compact envelope shows no pronounced high-density shell and the IME,
though confined, occupies a wider velocity range. In contrast, a large
$R_{\text{env}}$ results in IME confined to a narrow velocity range (see
text). Note that the bump in 56Ni corresponds to the refraction wave produced
by the DDT transition as is an artifact of the spherical models.

###  D.3 Resulting Spectral Constraints

Observed spectral measurements of ASASSN-15hy allow us to select the basic
parameters for the model. In the baseline model the Si abundance peaks at
about $8{,}500$ km s-1, which compares well with the observed Si ii
$\lambda$6355 velocity plateau in Fig. 12 and allows us to set
$M_{\text{env}}$. $R_{\text{env}}$ determines the velocity range of elements.
Our choice of $R_{\text{env}}$ is determined such that silicon is produced
between $7{,}000-14{,}000$ km s-1. The absorption minimum indicates a velocity
range for Si ii $\lambda$6355 of $5{,}000-9{,}500$ km s-1. At later times, the
feature around $\lambda 6200$ becomes increasingly dominated by blends of Fe
II lines (Fisher et al., 1999; Hoeflich, 1995). Therefore, the lower velocity
limit is uncertain. The upper end of the Si velocity is better determined by
the blue wing of the Si during early times (Hoeflich, 1995; Quimby et al.,
2006) because Si is needed to produce a wing. The observed value of the wing
indicates a somewhat larger value ($\approx 14{,}000-16{,}000$ km s-1) than in
our models. This may indicate a slightly smaller $R_{\text{env}}$ than
adopted. However, Shallow line wings are subject to blends and noise.

As discussed in Section 5.1.2 and common in thermonuclear explosions (Branch
et al., 1983; Hoeflich, 1995), the spectral feature at roughly $\lambda 6200$
transitions from being formed by Si ii to Fe ii dominated when the photosphere
recedes from S/Si to the NSE layers past maximum. By +2 d from maximum light,
the Si ii $\lambda$6355 feature is blended with Fe ii $\lambda$6456,
$\lambda$6516\. Note that the Fe is not primordial but produced by the
radioactive decay chain 56Ni $\rightarrow$ 56Co $\rightarrow$ 56Fe with half-
life times of 6.1 and 77.1 d, respectively. The decay results in an Fe mass
fraction $X_{\text{Fe}}\sim 0.1$ at $\sim 40$ d past the explosion. Therefore,
the interpretation of this feature being blended by Fe ii does not depend on
the initial $Z$. The theoretical Mg velocities ($8{,}200-14{,}500$ km s-1) are
consistent with the observations discussed in the observational sections. A
potential challenge for the model comes from the observed velocity range of
the optical C ii $\lambda$6580 from $9{,}300$ km s-1 at $-11$ d to about
$5{,}000$ km s-1 at $\sim+10$ d past maximum light. If the weak feature in the
NIR at 1.03 $\mu m$ is indeed C i, it implies a higher velocity of $12{,}000$
km s-1 at $\sim-$8.5 d. The early C i and C ii velocities are marginally
consistent with the model which shows C down to $\sim 9{,}000$ km s-1, but the
C ii velocity past maximum is not.

The systematically lower velocity of C ii $\lambda$6580 may be understood as a
limb effect. The optical C ii $\lambda$6580 feature is situated on the
emission portion of the Si ii $\lambda$6355 P-Cygni profile, subjecting the C
ii feature to a pronounced limb-brightening effect (Hoeflich, 1990). The C ii
absorbs radiation from an underlying disk that brightens towards the edge. The
result is that the C ii absorption profile is dominated by low absorption
velocities, due to the fact that the observer sees the projected velocities
(Hoeflich et al., 2002).

The possible early C i velocity in the NIR agrees with the peak C abundance in
the models. C i has been previously identified in SN 1999by, a subluminous SN
Ia with an extended C-rich layer (Hoeflich et al., 2002). SN 1999by and
ASASSN-15hy are both red in their $B-V$ colors at maximum light. Rather than
being dominated by ionized C, very strong C i lines in the NIR are expected if
the envelope of ASASSN-15hy is C rich. Since ASASSN-15hy does not show strong
C i lines but requires a large envelope mass for the overall abundance
distribution, we conclude that the He layer provides the mass without
additional spectral features.

By about maximum light, the photosphere is formed in the NSE and IME layers.
As in SN 1999by, the ejecta are dominated by singly ionized iron-group
elements, namely Fe ii and Co ii. Within the spectral constraints, we suggest
a possible interpretation for the difference between the $H$\- and $K$-band
features in this object as an effect related to the velocity gradient
($\frac{dv}{dr}$). As discussed in section 5.2, ASASSN-15hy shows the
individual components of Co/Fe multiplets in the $K$ but not in the $H$ band.

The appearance of $H$-band emission has been attributed to the fact that the
photosphere recedes within the NSE region and that the emission is powered by
the incomplete Rosseland cycle (Mihalas, 1978) well above the optical
photosphere. Because the envelope is optically thick in the UV to the outer
layers, the Rosseland cycle redistributes UV photons to the NIR. The emission
is expected to be formed at similar radii in both the $H$ ($1.6\pm
0.3~{}\mu$m) and $K$ ($2.2\pm 0.4~{}\mu$m) bands because the lines originate
from atomic levels with similar oscillator strengths and excitation energies
(Fig. D20, lower panel). As this process is dominated by atomic physics, one
would assume it should also hold true for 03fg-like SNe Ia. However,
observations show that this is not the case. In 03fg-like SNe, the 56Ni region
is located in the deeper, high density layers where the photosphere recedes
more slowly with time. Thus, less IGE are above the photosphere at comparable
times, and the features are weaker and develop later in time.

As a second effect, the quantitative difference between the $H$\- and $K$-band
properties in normal SNe Ia versus 03fg-like and subluminous SNe Ia can be
understood in terms of differences in the velocity gradient. More precisely,
the differences in the opacities in the $H$ and $K$ bands are manifested by
the quasi-continuum produced by many overlapping lines. The optical depth due
to expansion opacities is $\propto\frac{dv}{dr}$ (Karp et al., 1977; Hoeflich
et al., 1993), which is illustrated in Fig. D20. The opacity is smaller by a
factor of $2-3$ in 03fg-like SNe compared to normal SNe Ia, and the quasi-
continuum over the $H$-band region is larger by a factor of two compared to
the $K$-band region (see Fig. D20, upper panel). As a result, the quasi-
continuum forms close to the outer edge of 56Ni in the $H$ band, whereas the
photosphere recedes to well within the 56Ni region in the $K$ band.

This interpretation is supported by the similarity of 03fg-like SNe and SN
1999by in their NIR evolution of the IGE spectral features (Hoeflich et al.,
2002). The larger emission in the $H$ band is mostly due to thermalization at
the photosphere and results in a weak $H$-band break and weaker but present
$K$-band features. In both cases, the 56Ni is confined to low velocities
layers (less than 6,000 to $7{,}000$ km s-1), whereas the 56Ni in normal SNe
Ia extends to about 12,000 to $14{,}000$ km s-1.

Note that temperature in the outer layers of the envelope is sufficiently low
and the density is sufficiently high for CO formation $\sim$1 month after the
explosion. However, with He substituting for the C/O mixture in the envelope,
our model forms CO only when the C/O is at low velocities and has cooled down,
that is, $5-6$ months after explosion. However, the exact details of CO
formation are subject to numerical uncertainties.

Figure D20: Formation of the $H$\- and $K$-band features. Upper panel: The
effect of the velocity gradient on the quasi-continuum opacity in the NIR. For
illustration, we show the broadband mean, quasi-continuum opacities
(resolution R=10) as a function of wavelength for gradients corresponding to a
normal SN Ia for a $M_{\text{Ch}}$ mass explosion and our model (DCD07). Lower
panel: We show the last scattering radius for a normal bright SN Ia calculated
with HYDRA (adopted from Wheeler et al. 1998). Individual emission features
are formed if the individual components are well above the continuum. Although
the opacities of the individual components of the multiplets are comparable,
in the $K$ band the larger wavelength separation results in a smaller quasi-
continuum opacity, by a factor of 2. As a result, in DCD07 and subluminous SNe
Ia the $K$-band features are formed well above the continuum whereas the
photosphere in $H$ remains close to the outer edge of the 56Ni region. Hence
no emission features are formed early on.

###  D.4 Resulting Light-curve Constraints

The comparison between the DCD07 model and observed light curves is shown in
Fig. 15. For comparison to observations, we adopted a distance modulus of
$\mu=34.33$ mag (see Section 3.1), applied only the Galactic reddening
correction of $E(B-V)_{\rm{MW}}=0.13$ mag (see Section 3.3), and aided our
choice of the best matching model with comparisons to the Doppler shifts of
observed spectral features. The model’s post-maximum decline generally agrees
with that of ASASSN-15hy. As usual for cool envelope models (Hoeflich &
Khokhlov, 1996; Hsiao et al., 2020), they do not show a strong secondary
maximum, with the exception of luminous SNe, small $M_{\text{env}}$, and high
metallicity, $Z\sim Z_{\sun}$. High metallicity is needed to produce a
secondary maximum because iron group elements dominate the opacity. The NIR
flux is formed in the Wien tail of the energy distribution, thus the NIR
luminosity $L_{IR}$ scales as $\propto T\,R_{ph,IR}^{2}$. For bright SNe Ia,
the photospheric radius increases well beyond the first maximum (Hoeflich et
al., 1995). However, for low temperatures, the photosphere begins to recede
near the time of maximum light and the secondary maximum in the $i$-band
merges with the primary maximum (Hoeflich et al., 1995; Taubenberger, 2017;
Hsiao et al., 2020). The challenge is to find a model within our framework
that is red in $B-V$, dim in the $B$ band compared to other 03fg-like objects,
and luminous in both the UV and the NIR. while at the same time maintaining
agreement in the spectroscopic properties that set $M_{\text{env}}$ and
$R_{\text{env}}$.

As has been shown with previous envelope models with a detonation and a
$1.2~{}M_{\odot}$ core (Hoeflich & Khokhlov (1996); see left panel of Fig.
15), the rise times increase with $M_{\text{env}}$, and the light curve
becomes dimmer and broader because geometrical dilution in the material of the
degenerate WD decreases. However, for ASASSN-15hy, the core mass needed to be
increased to beyond $M_{\text{Ch}}$, $M_{\text{core}}=1.47~{}$$M_{\odot}$ to
increase the diffusion time scales in the core, leading to a slow pre-maximum
rise consistent with observations.

A large $M_{\text{env}}$ is inferred from the low Si ii velocity and narrow Si
ii distribution in the observed spectra. However, we need a fast receding
photosphere and low opacities to avoid the photosphere forming in the massive
C/O layers. Opacities are dominated by IGEs with solar composition, or even
typical Pop II abundances with $Z=Z_{\odot}/3$. For low continuum opacities,
we need He-rich material and a C/O ratio larger than that in carbon stars,
with a metallicity set to $Z=10^{-10}~{}Z_{\odot}$ for the baseline model. The
shell becomes optically thin within days, even in the UV, resulting in a
significant amount of hard UV and X-rays ($\approx 40-50\%$ of the
luminosity), during the phase dominated by 56Ni decay in the early part of the
light curve. This avoids the redistribution of the IR luminosity via the
incomplete Rosseland cycle mentioned above. Virtually any metals would absorb
the hard radiation from the inner region, heating the shell and boosting the
optical and IR luminosity by volume driven bound-free and free-free emission.
The need for a low-metallicity model is consistent with the low metallicity of
the host galaxy and the surrounding environment of ASASSN-15hy (see Section
3.2 and Appendix C.1).

The model $M_{\text{core}}$ places ASASSN-15hy in the regime of
super-$M_{\text{Ch}}$ degenerate cores but only slightly above
$M_{\text{Ch}}$. Models with even larger $M_{\text{core}}$, such as that
produced by the merging of two WDs on dynamical time scales, would start as
detonations and produce more 56Ni resulting in a brighter SN (Pakmor et al.,
2012). Being close to $M_{\text{Ch}}$ makes the ignition of deflagration
burning likely (Khokhlov, 1995; Niemeyer et al., 1996). One of the key
ingredients of the CD model is an extended deflagration phase that results in
pre-expansion of the core prior to the deflagration to detonation transition.
Here, we use an extended deflagration burning of $M_{\text{defl}}\approx
0.42~{}M_{\odot}$ to avoid a strong increase in the 56Ni production for a
small $R_{\text{env}}$. Note that such a late transition from deflagration to
detonation has only been found in very subluminous SNe Ia (Hoeflich et al.,
2017), which are rare in their own right.

The $Z=10^{-10}~{}Z_{\odot}$ model produced early light curves that are
approximately 1 mag brighter than the ASAS-SN nondetection limits. Parts of
the delay between the explosion and first light can be understood in terms of
the initial reheating phase. At early times, the temperature in the envelope
cools rapidly, within minutes by adiabatic expansion. Because of the small
expansion velocity in the nickel region, $\gamma$-rays are mostly trapped and
don’t contribute to the heating of the outer material, resulting in delayed
heating of the outer layers compared to normal SNe Ia. The duration of this
phase mostly depends on the geometrical dilution of the 56Ni layers and thus,
on the expansion velocity of the 56Ni layers since the $\gamma$-ray opacity
does not depend on temperature. This phase lasts until $\approx 0.5$ to $3.5$
days after the explosion for normal and subluminous SNe Ia, respectively
(Hoeflich et al., 2002, 2017). As a result of the low temperature in these
phases, the optical opacities are very low, and this phase is characterized by
an increasing photospheric velocity with time, and rather blue $B-V$ colors
compared to models with solar metallicity and large envelope masses, which
have $B-V\approx 0.3-0.4$ mag (Hoeflich & Khokhlov, 1996). In ASASSN-15hy, the
velocities are similar to a subluminous SNe Ia, but the mass is larger and
thus, the density is higher, leading to high luminosity from the degenerate
core. The $\gamma$-rays then start to heat the outer layers of the degenerate
core similar to subluminous SNe Ia after about $\sim 4-5$ days. With $Z\sim
0$, the early radiation cannot excite C/O rich material, due to the lack of
strong line blanketing as commonly produced by lines of iron group elements.
To effectively block the early radiation, we need some elements with lower
ionization potential and strong lines such as IGEs, for example, by mixing a
small amount of IGEs into the inner shell, boosting the opacity. More extended
mixing would shorten the reheating.

The metallicity777For numerical reasons, a resolution of only $\approx
10^{-4}$$M_{\odot}$ is used at the interface between the core and the
envelope. was increased to $Z=10^{-4}~{}Z_{\odot}$ at the interface of the
degenerate core and the C/O region of the shell. That is, the metallicity of
the envelope was increased. Since the degenerate core fully burns increasing
the metallicity there will only have small effects and here, we are interested
only in the opacity effects of the envelope on the light curve, not in
producing fully self-consistent models. The result is an extended ‘dark(er)’
phase, lasting about one week after the explosion and an early red color (see
Fig. 15). The increase in $Z$ and the corresponding dark phase bring this
model within agreement of the ASAS-SN $V$-band nondetections and reproduces
the observed apparent rise time of $\sim 24$ days. Thus, we choose this
modified baseline model with $Z=10^{-4}~{}Z_{\odot}$ as our best matching
model. The $V$-band last nondetection flux at 16 d is slightly lower than the
theoretical flux, but a change of 1 day in phase from explosion between
observations and the model is well within the model uncertainties expected by
mixing at the chemical interface between QSE and IGE elements (see Fig. D19).
The increase in metallicity also brings the best matching model into closer
agreement with the UV observations (Section 4). The early low luminosity
excludes the presence of an ongoing interaction as suggested for LSQ14fmg
(Hsiao et al., 2020), which would add a constant early luminosity. Using the
same approach and the nondetections being 2 mag below maximum light provides
an upper limit of the mass-loss rate of the AGB star to $\approx 2\times
10^{-7}$ $M_{\odot}$ $yr^{-1}$.

The mass of the degenerate core suggests the ignition begins as a deflagration
and subsequently turns into a detonation as discussed above. To produce a
subluminous SN we require a late transition density. A deflagration to
detonation transition is a common characteristic in reactive fluids in
general, but the details in stellar explosions are still under debate and may
involve the Zel’dovich mechanism (i.e., the mixing of burned and unburned
material), crossing shock waves, magnetohydrodynamic-instabilities, and shear
flows in a highly turbulent medium (Niemeyer et al., 1996; Khokhlov et al.,
1997; Livne, 1999; Poludnenko et al., 2011; Hristov et al., 2018). Recently,
semi-analytical solutions have been developed that suggest that a DDT is
unavoidable under C/O-WD conditions and that the transition density decreases
with increasing specific nuclear energy production (Poludnenko et al., 2019).
The model has low metallicity, resulting in a late DDT transition and a
subluminous SN. Therefore, we expect these ASASSN-15hy-like objects are rare.

###  D.5 Future Prospects

We outline the limitations of this study, which should be seen as a starting
point towards understanding the nature of 03fg-like SNe Ia. Due to the
sensitivity of the models to the rise time and the possible ‘dark phase’,
early-time data are extremely important. Such data may be expected from
ongoing and future campaigns such as and in particular, early time UV spectra
with HST to test for the chemical signature of the outer few tenths of a solar
mass. The simulations are based on spherical explosions involving
deflagrations and shell interaction, both of which are Raleigh-Taylor (RT)
unstable. The steep chemical gradients are likely to be smeared out on RT
scales, but full 3D hydro-simulations are needed to determine the details. The
picture provided by the model is consistent with the observations of
ASASSN-15hy, but forces the models into a particular corner of parameter
space. Two 03fg-like objects, ASASSN-15hy and LSQ14fmg are consistent with the
scenario suggested here with clear predictions for larger samples. The super-
Chandrasekhar value of $M_{\text{core}}$ lends credence to the DCD scenario.
However, both ASASSN-15hy and LSQ14fmg are odd-balls in some respects. The
lack of polarization in a few other 03fg-like explosions, such as SN 2009dc
(Tanaka et al., 2010) and SN 2007if (Cikota et al., 2019) is expected within
the CD scenario, but not in merger scenarios without massive envelopes.
However, this does not exclude the possibility that a majority of 03fg-like
SNe are the result of dynamical mergers. A larger sample of 03fg-like events
is needed for further analyses. A key difference between scenarios should be
expected in the predictions of the nature of the nearby environment. X-ray and
radio observations and a better characterization of the hosts are needed.
Because of the similarity of the $BV$ bands with normal SNe Ia, 03fg-like SNe
could hide in data sets where the light curves are followed in only a few
photometric bands. Observations of redder bands such as the $i$ band are
required in order to distinguish these peculiar events as well as to exclude
them for cosmological use.