Bruno Escoffier
email: bruno.escoffier@lip6.fr

Vangelis Th Paschos
email: paschos@lamsade.dauphine.fr

Emeric Tourniaire
email: tourniaire@lamsade.dauphine.fr

SUPER-POLYNOMIAL APPROXIMATION BRANCHING ALGORITHMS *

Keywords: Mathematics Subject Classification. 68W25, 05C85, 68Q25 Branching algorithm, moderately exponential approximation, approximation schema

We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (i.e., algorithms achieving ratios 1 ± , for arbitrarily small ) for broad classes of combinatorial optimization problems via a well-known technique widely used for deriving exact algorithms, namely the branching tree pruning.

Introduction

Polynomial time approximation, exponential time computation and fixed parameter tractability (FPT) are three main fields aiming at coping with NP-hard problems.

In polynomial time approximation (see for instance [START_REF] Ausiello | Complexity and approximation. Combinatorial optimization problems and their approximability properties[END_REF]), one tries to devise polynomial time algorithms that compute feasible solution that are as close as possible to the optimal one, under an a priori defined criterion, called approximation ratio.

The goal of exponential time computation (see [START_REF] Fomin | Exact exponential algorithms[END_REF]) is to devise exact algorithms whose worst case complexity, though not polynomially bounded, is as low as possible. For many NP-hard problems, the best known algorithm works in exponential time O * (γ n ) (meaning O(γ n poly(n)) for some polynomial poly), for some γ > 1. A natural objective is then to minimize the value of γ.

Fixed parameter tractability is in some sense a complementary field where an instance is given together with a parameter k ∈ N; the goal is to know whether the problem is solvable by an algorithm working in time O(f (k)poly(n)) for some function f and some polynomial p [START_REF] Downey | Parameterized complexity. Monogr. Comput. Sci. Springer[END_REF]. Such an algorithm is called an FPT algorithm, and if such an algorithm exists the problem is in the FPT class (for this particular parameterization). A usual parameter (called standard parameter) is the value of the sought solution. Formally, for the standard parameterization (we will use the standard parameterization in all this article), a problem is in FPT if there exists an algorithm such that given an instance I of size n and an integer k, (i) it outputs YES if there is a solution of value at least k (for a maximization problem, at most k for a minimization problem) and NO otherwise; (ii) it works in time O(f (k)poly(n)) for some function f and polynomial p.

Interestingly, negative results have been obtained in these three fields. For polynomial time approximation, tight lower bounds are known for many optimization problem, under the hypothesis P = NP. For instance, Max 3SAT3 is well known to be approximable in polynomial time within ratio 7/8, and not approximable in polynomial time within ratio 7/8 + unless P = NP for any > 0 [START_REF] Håstad | Some optimal inapproximability results[END_REF]. Dealing with exponential time computation, the Exponential Time Hypothesis (ETH ), introduced in [START_REF] Impagliazzo | On the complexity of k-sat[END_REF][START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF], conjectures that there is no algorithm for Max 3SAT that works in time 2 o (n) where n is the number of variables. Under ETH, many classical optimization problems do not have subexponential time algorithms 4 . Finally, the parameterized complexity theory considers the hypothesis W[1] = FPT (see [START_REF] Downey | Parameterized complexity. Monogr. Comput. Sci. Springer[END_REF] for the definition of the class W [START_REF] Ausiello | Complexity and approximation. Combinatorial optimization problems and their approximability properties[END_REF]) under which it is shown that many optimization problems do not admit FPT algorithms (under the standard parameterization for instance).

In recent years several very interesting studies try to put together either polynomial approximation and exact computation, or parameterized computation and polynomial approximation, in order to build new tools coping with intractability (see, for example [START_REF] Bourgeois | Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms[END_REF][START_REF] Cai | Fixed-parameter approximation: conceptual framework and approximability results[END_REF][START_REF] Chen | On parameterized approximability[END_REF][START_REF] Cygan | Exact and approximate bandwidth[END_REF][START_REF] Dantsin | max sat approximation beyond the limits of polynomial-time approximation[END_REF][START_REF] Downey | Parameterized approximation problems[END_REF][START_REF] Escoffier | Approximating max sat by moderately exponential and parameterized algorithms[END_REF][START_REF] Fürer | An exponential time 2-approximation algorithm for bandwidth[END_REF][START_REF] Marx | Parameterized complexity and approximation algorithms[END_REF]. One of the basic goals of all these works is to show how one can achieve ratios unachievable in polynomial time spending time that is much lower than the best-known exact or parameterized time for the problems handled. Let us note that we say that a minimization (maximization, respecitvely) problem Π, together with a parameter p, is parameterized ρ-approximable if there exists an FPT-time algorithm which computes a solution of size at most (at least, respectively) ρp whenever the input instance has a solution of size at most (at least, respectively) p; otherwise, the algorithm returns some feasible solution.

Our aim in this paper is to study links between approximation and exact computation (whatever the parameter measuring complexity is) by devising a unified framework that handles exact and parameterized computations and approximation. Furthermore, rather than focusing on one particular optimization problem, we tackle the question of giving sufficient conditions for any problem optimally solved by branching algorithms to admit good approximation algorithms in exponential time, with respect to any parameter used to measure its complexity.

Our basic guideline here is the following. Consider a problem Π parameterized by some parameter p (that can be the size n of its instance, the value k of its optimal solution, the treewidth of the input-graph, if it is a graph-problem,. . . ). Suppose that Π is inapproximable within some ratio ρ (in polynomial time) and, moreover, that the best-known algorithm for Π runs in O * (F (p)) 5 , for some function F that increases with p. Does there exist an approximation algorithm for Π, achieving ratio better than ρ and running in time much smaller than O * (F (p))? Especially, we focus on the existence of "approximation schemata", i.e., algorithms with ratios 1 ± , for arbitrarily small , with running time O * (F (p)), where F < F for a problem solvable (exactly) in O * (F (p)). Typically, if F (p) = γ p for some γ, we seek F (p) = γ p for γ < γ.

The paper is organized as follows. In Section 2, we give sufficient conditions to derive approximation schemata using branching algorithms. Then, in Section 3, we derive such schemata parameterized by n (the size of the instance) and p (the standard parameter), for some well-known problems. Finally, in Section 4, we sketch a formal framework of a structure for moderately exponential and parameterized approximation.

Approximation schemata by branching algorithms

In both exact and parameterized computation, a very popular technique for achieving exact algorithms with non-trivial running-time results is the so-called "search-tree pruning". So, a natural question that arises ant is handled in this section, is whether its applicability can be extended for deriving good approximation results or not. Let us first note that a class of problems is already known to admit such exponential time approximation schemata (with respect to n), the class of hereditary maximization problems6 (see, for instance, [START_REF] Bourgeois | Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms[END_REF]): by partitioning the instance, if a hereditary graph problem is solvable in O * (γ n ) then it is ρ-approximable in time O * (γ ρn ) for any ratio ρ. The same holds also for Max SAT in [START_REF] Dantsin | max sat approximation beyond the limits of polynomial-time approximation[END_REF][START_REF] Escoffier | Approximating max sat by moderately exponential and parameterized algorithms[END_REF]. In the second of these papers such schemata are obtained with respect to both n (the number of variables), m (the number of clauses), and k the standard parameter, i.e., the number of satisfied clauses.

I I

1 I 2 I r . . . PB 1 (S 1 ) PB 2 (S 2 ) S 2 . . . PB r (S r ) . . . S r S 1

Payback functions

Example 1. We give a basic overview of the schema for Max Independent Set (with respect to n). Using classical reduction rules (including vertex folding, see for instance [START_REF] Fomin | A measure & conquer approach for the analysis of exact algorithms[END_REF]), vertices of degree at most two can be removed from the instance in polynomial time. When there is no such vertex, the naive exact algorithm is to pick a vertex, and to branch on it in the following way: either we add the vertex in the final solution and remove its neighbors, or we remove this vertex. In the first case, the size of the instance decreases by at least 4 (one vertex in the solution and at least three vertices removed) ; in the second, the size decreases by 1, and this gives a complexity

O * (1.38 n ) (solution of C(n) C(n -4) + C(n -1)).
In this situation we can achieve a 1/2-ratio by removing an additional vertex in the first branching case. The complexity of this new algorithm satisfies C(n) C(n -5) + C(n -1) O * (1.32 n ). Note that much better exact algorithms are known for Max Independent Set, and that it is easy to improve this technique of approximation (remove a clique for instance). The aim of this simple example is only to illustrate the basic idea that will be developed in the sequel.

Given an instance I of an optimization problem, we denote by S (I) the set of feasible solutions of I, by f (I) the optimal value of I, and by f (I, S) ∈ N, or f (S) when no confusion is possible, the value of S ∈ S (I). We adopt a measure function I → p. Note that p can be any parameter of the instance (including f (I), |I|,. . . ). We just require that when f (I) = 0 the instance is solvable in polynomial time 7 . For clarity we will suppose that p ∈ N but similar results can be obtained with p ∈ R + (in particular p can be the weight associated to |I| in the measure and conquer paradigm [START_REF] Fomin | A measure & conquer approach for the analysis of exact algorithms[END_REF]).

A branching algorithm solves a given optimization problem by building a search tree. To each node of the tree is associated an instance; a branching rule (such as "take a particular vertex in the solution or do not take it") gives rise to several instances that are the children of this node 8 . The leaves of the tree correspond to trivial instances. This might be formalized as follows in the case of a maximization problem. Definition 2.1 (Branching rule; Fig. 1). A branching rule of fan-out r is a mapping from an instancen I to a set of r instances (I 1 , I 2 , . . . , I r ) and a set of algorithms (PB 1 , . . . , PB r ), called payback functions, with the following properties: (a) If S i is a solution for the instance I i , then PB i (I, I i , S i ) is a solution for I (for simplicity, we will denote PB i (I, I i , S i ) by PB i (S i )).

(b) The branching and every payback function are computable in polynomial time with respect to the size of the instance. (c) (parameter reduction) There exists a sequence of positive numbers (a i ) i=1,...,r giving a guarantee on the instance size decreasing. This gives Rule (B1): ∀i, p i pa i . (d) (exhaustiveness) For (at least) one of the instances I i , the payback function increases the value of a feasible solution by at least the difference in the optimum between I and I i . This, gives Rule (B2): ∃i, ∀S ∈ S (I i ),

f (PB i (S)) -f (S) f (I) -f (I i ).
Obviously, the larger the a i (in Rule (B1)), the faster the algorithm. Exhaustiveness ensures that an optimal solution for an instance can be found with the branching rule. Indeed, exhaustiveness is satisfied in branching algorithms in the branch corresponding to the choice of an optimum solution.

Example 2 (Example 1 continued). For Max Independent Set, if we branch on a vertex v and I 1 (resp., I 2 ) is the branch where v is taken (resp., discarded), then PB 1 (I, I 1 , S) = S ∪ {v} and PB 2 (I, I 2 , S) = S.

Given an optimization problem P with such a branching rule, we define the branching Algorithm 1. The following result is folklore. We give it for reasons of self-readability of the paper.

Algorithm 1: Naive branching algorithm.

Input : An instance I0 Output: An optimal solution for I0 1 Build a tree using the following rule: a) Each node is labeled with an instance, the root's label being I0. b) Each node with a non-empty instance I has r children, given by the reduction rule. c) Each node with an empty instance is a leaf. 2 for each leaf in the tree do 3 Compute an optimal solution. Use the payback functions to get a solution for the root of the tree in a bottom up fashion: the solution for a node with instance I is the best solution among the r solutions computed by the payback functions. Proof. Let us denote by I 0 the instance in the root of the tree. At least one child of I 0 satisfies Rule (B2). We call this child I 1 . Then I 1 has a child I 2 that satisfies the same rule, and so on until we reach a leafk I k . The instance on the leaf is solvable exactly in polynomial time, giving a solution S k such that f (S k ) = f (I k ). Then, we use the payback functions to compute solutions for every instance from I k to I 0 , and we call these solutions S k , S k-1 , . . . , S 0 . With these solution, we have, using (B2), f

(S i ) -f (S i+1 ) f (I i ) -f (I i+1 ), for i = 0, . . . , k -1. Summing these inequalities, we get f (S 0 ) -f (S k ) f (I 0 ) -f (I k ). So, f (S 0 ) = f (I 0 ), which proves the correctness of the algorithm.
The complexity is given by the number of nodes in the tree. For a parameter p, this number satisfies the equation C(p) C(pa 1 ) + C(pa 2 ) + . . . + C(pa r ), which gives the complexity claimed.

In the case of a parameterized problem with the standard parameterization, the previous algorithm provides (with the same complexity) an optimal solution if there is a solution of value at least p in the instance (with a slight obvious modification in the leaves when there is no solution of the seek value).

Given a maximization problem, assume that a branching algorithm as Algorithm 1 has been devised. We are interested in modifying it, in order to get an approximation algorithm with a better running time. We show that two properties are sufficient to reach this for any ratio ρ = 1, i.e., to get an exponential time approximation schema. The first condition, called strict monotonicity, deals with the branching rule. Note that it is generally satisfied by most of the branching rules used in the literature for classical optimization problems. The other condition, called diminution rule, is independent on the branching rule (it it directly linked to the problem and not to a particular branching algorithm).

Definition 2.3 (Strict monotonicity).

A branching rule is said to be strictly monotonic if for at least one instance I i the payback function increases (strictly) the value of such solutions (while the other ones do not decrease the value of feasible solutions). Formally, there exists a sequence of nonnegative integers (s i ) i=1,...,r , with at least one of them greater than 0 such that the following rule is satisfied:

Rule (B3): ∀i, ∀S ∈ S (I i ), f (PB i (S)) f (S) + s i .
Obviously, the greater the integers s i , the faster the approximation algorithm. In Example 1, the branching rule is strictly monotonic: the payback function will increase by one the value of the solutions in the branch where we have taken v (and by 0 in the other branch).

Definition 2.4 (Diminution rule; Fig. 2). A diminution rule is a mapping from an instance I to another instance I together with an polynomial time algorithm (which we call payback function) PB , with the following properties:

(1) The parameter decreases by at least one. This gives Rule (D1): p p -1.

(2) The value of the optimal solutions does not decrease by more than one. This results in Rule (D2):

f (I ) f (I) -1. (3)
The payback function PB preserves the value of the solutions. This gives Rule (D3): ∀S ∈ S (I ), f (PB (S )) f (S ).

Example 3 (Example 1 continued). For Max Independent Set, using as parameter the number of vertices, the diminution rule used consists of removing a vertex from the graph: from a graph G we obtain a graph G with one vertex less (Rule (D1)). Obviously, the optimum value in G is at most the optimum value in G plus one (Rule (D2)). The payback function is the identity function (an independent set in G is an independent set in G) that satisfies Rule (D3).

Given a problem that has both a diminution rule and a strictly monotonic branching rule, we can define the ρ-approximation Algorithm 2. As for the exact branching algorithm, the case of a parameterized problem with standard parameter, a slight and obvious modification of Algorithm 2 allows to output a solution of value at least ρp (and even at least ρf (I)) if there is a solution of value at least p in the instance. Note that γ 1 (for ρ = 1) corresponds to the complexity of the exact branching algorithm (its complexity is O * (γ n 1 )). The fact that γ ρ < γ 1 for any ρ = 1 follows from the fact that at least one s i is strictly positive by hypothesis.

Proof. (Thm. 2.5). We first analyze the approximation ratio of the algorithm. Let us show that each internal node [I, α] in the tree has at least one child [I , α ] with a payback function PB, and satisfying the following:

∀S ∈ S (I ), f(PB(S )) -f (S ) + 1 1 + α 0 (α -α ) α 0 1 + α 0 (f (I) -f (I )). (2.1)
Concerning α and α 0 , we examine the following two cases.

(i) α α 0 . Then I is derived from I using the diminution rule. For any solution S ∈ S (I ), we call S = PB(S ). Then using Rule (D3), we have f (S)f (S ) 0. Also, as we used a diminution, we know that α = αα 0 , and so:

1 1 + α 0 (α -α ) = 1 1 + α 0 × α 0 = α 0 1 + α 0 •
Using Rule (D2), since f (I)f (I ) 1, it holds that:

α 0 1 + α 0 (f (I) -f (I )) 1 1 + α 0 (α -α ) f (S) -f (S ) + 1 1 + α 0 (α -α ) .
(ii) α < α 0 . Then, I has up to r children. Using Rule (B2), we immediately derive that, for one child [I , α ] and for any solution S ∈ S (I ), f (S)f (S ) f (I)f (I ), where S = PB(S ). In particular:

α 0 1 + α 0 (f (S) -f (S )) α 0 1 + α 0 (f (I) -f (I )) . (2.2)
Also, we use the definition of α and α , and Rule (B3), and we have f (S)f (S ) αα. So:

1 1 + α 0 (f (S) -f (S )) + 1 1 + α 0 (α -α ) 0. (2.3) Summing (2.
2) and (2.3), we get:

1 + α 0 1 + α 0 (f (S) -f (S )) + 1 1 + α 0 (α -α ) α 0 1 + α 0 (f (I) -f (I ))
which derives (2.1).

From the above cases, one can see that it is possible to find a branch in the tree, going from the root [I 0 , 0] to a leaf [I f , α f ], satisfying (2.1) at each step. We build in polynomial time a solution S f for the instance I f , and then apply the payback functions to build a solution S 0 on I 0 . If we sum the equations derived from (2.1), we get:

f (S 0 ) -f (S f ) + 1 1 + α 0 (-α f ) α 0 1 + α 0 (f (I 0 ) -f (I f )) .
Since α f 0, and f (S f ) = f (I f ) 0, we have:

f (S) -f (S f ) α 0 1 + α 0 f (I) - α 0 1 + α 0 f (I f ) =⇒ f (S) α 0 1 + α 0 f (I) + f (S f ) - α 0 1 + α 0 f (I f ) 0 α 0 1 + α 0 f (I) = ρf (I)
that concludes the proof of the ratio. We now study the running-time of the algorithm. Set, for each node

[I, α], T ([I, α]) = |I| -α/α 0 .
When applying a branching rule, a node is replaced by at most r nodes of sizes |I|a 1 , |I|a 2 , . . . , |I|a r , and with α values α + s 1 , α + s 2 , . . . , α + s r . Note that, for each child, there are at most |I| (i.e., a polynomial number) diminutions (the size decrease by one after a diminution).

In any diminution that transforms [I, α] into [I , α ], the quantity T becomes T T ; so, this will not affect the overall computation time of the algorithm. Indeed, |I | |I| -1, because of Rule (D1). Also we have α = αα 0 , due to the definition of the algorithm. Then:

T = |I | - α α 0 |I| -1 - α -α 0 α 0 = |I| - α α 0 = T.
With the branching rule, if the kth child of [I, α] is [I k , α k ], and the quantity T becomes T k , then we have

T k T -a k -s k /α 0 . Indeed, using Rule (B1), |I k | |I| -a k .
Also, by definition, α k = α + s k . Then:

T k = |I k | - α k α 0 |I| -a k - α + s k α 0 = T -a k - s k α 0 •
So, the complexity according to the quantity T satisfies:

C(T ) r k=1 C T -a k - s k α 0 •
For the first node, the quantity T equals the parameter of the initial instance. Finally, we get a complexity

O * (γ |I| ρ )
, where γ ρ is the largest real root of the equation 1 =

r k=1 γ -a k -s k (1-ρ)/ρ ρ , as claimed.
This technique can be adapted to work for minimization problems also. It suffices that Rule (B2) becomes

Rule (B2'): ∃i, ∀S i ∈ S (I i ), f (PB i (S i )) -f (S i ) f (I) -f (I i ).
For the diminution rule, we need the same properties with the following modifications:

• Rule (D2) becomes: Rule (D2'): f (I ) f (I).

• Rule (D3) becomes: Rule (D3'): ∀S ∈ S (I ), f (PB (S )) 1+f (S), i.e., the PB function will not increase the parameter of a solution by more than one.

Example 4. For Min Vertex Cover, the branching rule "corresponding" to that of Example 1 is either to add a vertex v to the vertex cover (and to remove it from the graph), or to take all its neighbors in the vertex cover (and to remove them together with v from the graph). This branching rule clearly satisfies Rules (B2') and (B3). Now take the rule consisting of removing a vertex v in the graph G (thus getting a graph G ) and putting it into the vertex cover under construction. Given a vertex cover on G , the payback function simply adds v to G , thus producing a vertex cover of G. Then, Rules (D1), (D2') and (D3') are obviously satisfied. This example is also a simple example (not leading to some interesting result) for illustrating the idea in minimization problems.

When setting α 0 = 1 ρ-1 in Algorithm 2 (now ρ > 1) to deal with minimization problems, then the following holds.

∀S ∈ S (I ), f(PB(S )) -f (S ) + α -α α 0 α 0 + 1 α 0 (f (I) -f (I )). (2.1')
Indeed, we have two cases with respect to α. α α 0 . In this case, I is derived from I using the diminution rule. For any solution S ∈ S (I ), we call S = PB (S ). Then with Rule (D3'), we have f (S)f (S ) 1. Also, as we used a diminution, we know that α = αα 0 , and so:

f (S) -f (S ) + α -α α 0 1 -1 0
Using Rule (D2'), we know that f (I)f (I ) 0, which gives (2.1').

α < α 0 . Then, I has up to r children, and using Rule (B2'), we know that for one child [I , α ], and for any solution S ∈ S (I ), f (S)f (S ) f (I)f (I ) where S = PB(S ). Also, f (S)f (S ) αα (cf. Rule (B3)). So, it holds that:

f (S) -f (S ) + α -α α 0 1 + α 0 α 0 (f (S) -f (S )) 1 + α 0 α 0 (f (I) -f (I )) .
The end of the proof is therefore the same as previously.

Let us conclude this section by the following remark. For simplicity, we have fixed differences in Rules (D1) and (D2) to 1. It is worth noticing that similar results would immediately follow using other (constant) values. In particular (this will be useful for the results given later), suppose that we simply replace Rule (D2) by a new Rule (D2"): there exists k such that f (I ) f (I)k. In this case, all we have to do is dividing the evaluation function by k, which preserves the approximation ratio. Therefore, the parameters s i will become s i /k (see Rule (B3)), and the complexity will now be O * (γ p ), with γ root of 1 = r i=1 γ -ai-(si/k)(1-ρ)/ρ .

Using approximate branching to get approximation schemata

Parameterization by the instance size

Feedback vertex set

Given a graph of order n, Feedback Vertex Set consists of finding a minimum-size set of vertices whose deletion makes the graph acyclic. This problem is NP-hard in both directed and undirected graphs [START_REF] Karp | Reducibility among combinatorial problems[END_REF] and can be optimally solved in O * (1.9977 n ) [START_REF] Razgon | Computing minimum directed feedback vertex set in o(1.9977 n )[END_REF], and in O * (1.7347 n ) [START_REF] Fomin | Finding induced subgraphs via minimal triangulations[END_REF], respectively. Both cases are approximable in polynomial time within ratio 2 [START_REF] Becker | Optimization of pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem[END_REF]. We show how our method can be used in order to obtain ratios between 1 and 2 with improved computation times.

To obtain a branching rule for this problem, we formalize an instance of Feedback Vertex Set as a graph G(V, E) with a set D of vertices excluded from the solution (we set D = ∅ at the beginning of the algorithm). The size of an instance is |V | -|D|. If we have an instance I = (G, D), we can pick a vertex v from V -D and define I 1 = (G[V -{v}], D) and I 2 = (G, D ∪ {v}). Our payback functions are PB 1 (S) = S ∪ {v} and PB 2 (S) = S. Note that if D ∪ {v} contains a cycle, then we can skip the I 2 branch as this instance will not have a solution. This branching has the desired properties: the size of the instance decreases by one on each branch, the payback functions give a feasible solution, they can be computed in polynomial time and the optimal solution can be reached (take the first branch only when the vertex v is in the optimal solution), which ensures exhaustiveness.

We have the following diminution rule: in instance I = (G, D), pick any vertex v and we have I = (G[V -{v}], D) and PB (S) = S ∪ {v}. We can see that the size of the instance decreases by one, the computations are polynomial and the payback function does not increase the size of a solution by more than one.

Discussion above, immediately derives the following theorem.

Theorem 3.1. Feedback Vertex Set can be approximately solved within any ratio ρ in time O * (γ n ), with γ solution of the equation γ γ -1 + γ -ρ (this result is summarized Fig. 4).

More generally, suppose that P is a minimization problem where given an instance I, feasible solutions are subsets of a given set S that satisfy a given property π such that if S ⊆ S satisfies π, then any S ⊇ S satisfies π, the goal being to minimize the size of the subset.

Then, we rephrase the problem as in the maximization case by considering the sets T and D of already taken and discarded vertices. A feasible solution is a set S ⊆ S \ (T ∪ D) such that S ∪ T satisfies π, and its value is |S |. We can use as branching rule the same as above. The diminution rule is to take an element that and put it in the solution, which satisfies Rule (D2'). This allow us to find,a s claimed, a ρ-approximation in O * (γ n ), γ being the solution of the equation 1 = γ -1 + γ -ρ .

Max cut

Given a graph G(V, E), Max Cut consists of partitioning V into two subsets V 1 and V 2 such that the number of edges having one endpoint in V 1 and the other one in V 2 is maximal. The set of these crossing edges is called the cut (associated to V 1 ).

The basic branching schema consisting of fixing, let say, set V 1 and then of considering, for every vertex, that either it belongs, or it does not belongs to V 1 , solves the problem in time O * (2 n ). In sparse graphs, i.e., in graphs with maximum degree bounded by d, the problem is solvable in time O * (2 (1-(2/d))n ) [START_REF] Della Croce | An exact algorithm for max cut in sparse graphs[END_REF]. On the other hand, Max Cut is approximable in polynomial time within ratio 0.8785 [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF], but it is APX-hard [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF].

Consider a graph with maximum degree d. We will show how we can use the techniques developed above in order to get non-trivial moderately exponential ratios.

To obtain a branching rule for this problem guaranteeing that, at least one child will increase the size of any solution by one (cf. Rule (B3)), we first eliminate one pathological case. If the graph is not connected, then we apply our algorithm on each connected component (which gives, of course, the optimal solution). Therefore, we will suppose in the following that our graph is connected. In the initial instance, we pick one vertex arbitrarily, and we assign it to V 1 . Then, the branching rule is to choose a vertex that is adjacent to another one in V 1 or V 2 , and to make two children, placing this vertex in V 1 or V 2 . If the first node was in V 1 , then placing the node in V 2 will guarantee an increasing of the solution of at least one.

For the diminution rule, if we consider a graph G of degree at most d, then we can use the following easy result: in a graph of degree at most d, removing a vertex and all its edges decreases the size of the maximum cut by at most d. So, the diminution rule is as follows: take a vertex, throw it away and remove every edge adjacent to this vertex in the same time, and the following holds.

Proposition 3.2. Max Cut can be approximately solved within ratio ρ in time O

* (γ |V | ), with γ the largest real solution of 1 = γ -1 + γ -1-(1-ρ)/dρ .

Maximization hereditary problems

Let P be a maximization problem where, given an instance I, feasible solutions are subsets of a given set S that satisfy a given hereditary property π, the goal being to maximize the size of the subset.

To make hereditary problems fitting the previous framework, we formulate P in a different (equivalent) manner, defining a problem P where an instance is given by: (i) an instance I for the problem P ; (ii) a set of elements in the solution T ⊆ S; (iii) a set of elements not in the solution D ⊆ S with D ∩ T = ∅. Feasible solutions of an instance (I, T, D) of P are subsets S ⊆ S \ (T ∪ D) such that T ∪ S satisfies π (i.e., these are the feasible solutions of I containing T ). The value of the solutions S is its size |S |.

As already mentioned, for any instance (I, T, D) of this new problem P , we have a natural branching rule: we take an element from S that is neither in T nor in D, and we add it either in T or in D. The branching continue as long as T is a feasible solution. This gives a trivial branching algorithm in time O * (2 n ), where n = |S|. This branching rule is strictly monotonic. As a diminution rule, we only add one element to D. In the worst case, the element was in the optimal solution, then its size decreases by one. So our algorithm applies, and gives an answer with approximation ratio ρ and computation time in O * (γ n ρ ), γ ρ being the greatest real solution of the equation 1

= γ -1 ρ + γ -1-(1-ρ)/ρ ρ
. Note that if this indicates that approximate branching algorithms seems to apply to more problems than the technique of partitioning the instance, it is worth noticing that the latter technique derives better running times for hereditary problems (compare γ ρn with the running time of Thm. 2.5).

Max k-coverage

In the Max k-coverage problem, given a graph G(V, E) and an integer k, we ask for finding a subset S of V of size k that maximizes the number of edges incident to a vertex in S. Here again, we will consider graphs of bounded degree d. Note that this problem is solvable in O * (2 (d-1)n/(d+1) ) by the basic branching schema (take a vertex or do not take it), in graphs with maximum degree d [START_REF] Della Croce | Efficient algorithms for the max k-vertex cover problem[END_REF], and it is approximable in polynomial time within ratio 3/4 [START_REF] Feige | Approximation algorithms for maximization problems arising in graph partitioning[END_REF][START_REF] Jäger | Improved approximation algorithms for maximum graph partitioning problems[END_REF], but it is APX-hard as generalization of Min vertex cover.

Max k-Coverage problem is polynomial if k is bounded by a fixed constant. The branching rule is trivial: take a vertex, add it in the solution or not. Stop branching when k vertex have been added. The diminution rule is simply to take a vertex and eliminate it. As the degree of the graph is bounded, then this elimination can't decrease the solution's size by more than d. We get a similar result as in the case of Max cut.

Standard parameterization and minimization problems

Let us consider the Min Vertex Cover problem with the standard parameterization. Here, there exists a naive well known branching with complexity O * (2 p ) that allows to determine if there is a vertex cover of size p (and even to build one if so): consider an uncovered edge, and branch adding either one or the other of its extremities. This branching fits our definition, and we use the following diminution rule: we consider any edge, and we add both its endpoints in the solution, following the spirit of the modified version of Algorithm 2 for minimization problems. When applying this diminution rule on an instance I we get an instance I where f (I ) f (I) -1, p p -1 and f (PB(S)) 2 + f (P B(S)), so the rule fulfills the requirements. Note that this algorithm, leading to an approximation schema, is very similar in the case of vertex cover to the works of [START_REF] Fellows | Parameterized approximation via fidelity preserving transformations[END_REF] and [START_REF] Brankovic | Combining two worlds: parameterized approximation for vertex cover[END_REF]. Note also that the diminution rule can be combined with other parameterized algorithms (better than O * (2 p )) to derive better running times exactly in the same way.

The discussion made above can be generalized to capture more FPT problems (parameterized by the standard parameter). Consider, for instance, problems consisting of finding a minimum-size set of items satisfying some property π such that every set containing a subset satisfying π, also satisfies π.

If there exists a branching rule that any time adds an item among r in the solution (that is the parameter diminishes by at least 1 on any branch), this gives rise to an FPT exact algorithm running in time O * (r p ). Then, a simple reduction rule consists of adding the r items of a given step in the solution. Using the same analysis as in Theorem 2.6, we derive the following result.

Theorem 3.3. Problems satisfying properties as π are ρ-approximable, for any

ρ > 1, in FPT-time O * (r k(r-ρ)/(r-1) ).
The above discussion can be immediately generalized to enhance also maximization problems.

Towards a formal definition of structure for moderately exponential and parameterized approximation

Approximation classes for moderately exponential approximation

We focus on the well known class NPO of optimization problems: an NPO problem Π is defined on a set I of instances. To each instance I ∈ I corresponds a set S (I) of feasible solutions. A function f associates for each instance I and each feasible solution S ∈ S (I) a value f (I, S) ∈ N, to be either maximized or minimized. In the class NPO, the following assumptions are required:

• instances can be recognized in polynomial time;

• the size of feasible solutions are polynomially bounded in the size of the instance; moreover, it can be checked in polynomial time whether a given S is in S (I) or not; • f is polynomially computable.

An optimal solution of an instance I will be denoted OPT(I), or simply OPT if there is no ambiguity. We use the notation f (I) for f (I, OPT(I)).

Following the discussion in introduction, considering an optimization problem that is solvable in time O * (γ n ), we may wonder whether the problem is ρ-approximable in time O * (γ n ρ ) with γ ρ < γ for some ratio ρ, or even for any ratio ρ, or not. This motivates the definition of the following two classes. Note that we give the definition for maximization problems, but everything said in this section can be easily translated to minimization problems.

Class 1 (EAS). For δ > 1, a maximization NPO problem is in EAS[δ] if, for any ρ < 1, there exists a ρ-approximation algorithm with computation time O * (δ n ρ ), with δ ρ < δ. This defines a notion of approximation schema, the existence of which of course depends on the parameter δ which is the "target" basis of the exponential function expressing the running time. Dealing with approximation for a specific ratio, we define the class EAX[γ, ρ].

Class 2 (EAX). For δ > 1, an NPO problem is in EAX[γ, ρ] if there exists a ρ approximation algorithm with computation time O * (γ n ).

Let us begin with some properties of these classes. First, note that, obviously, any problem that can be solved exactly in time O * (δ n ) is in EAS[δ ] for any δ > δ. On the other hand, one may expect at first sight that if a problem is in EAS[δ], then the problem will be solvable in O * (δ n ). This is the case for several exponential approximation schemata obtained so far in the literature, but the following result is worth being mentioned: Max Unused Colors9 can be approximated with ratio (1 -) in time O * (2 n ) and polynomial space for any > 0, whereas the best known exact algorithm in polynomial space is in O * (2.25 n ) [START_REF] Bourgeois | Efficient approximation of min coloring by moderately exponential algorithms[END_REF].

To get this "reverse" property, we need to enforce the notion of approximation schema. As in the polytime approximation framework, we may say that a problem has a full γ-exponential approximation schema if it is possible to perform a (1 -) approximation in time p(1/ , n) × γ n for some polynomial p and γ < γ. Then, we have the following easy property. Proof. If the value is bounded by q(n), with q a polynomial, then using the schema, we can get a (1+1/(q(n)+1))approximation in time O(p(q(n) + 1, n)γ n ), which is a computation time O * (γ n ). With this ratio, the difference between the optimal solution and the obtained solution would be less than one, which means that we have an exact solution. Now, let us make some observation on the classes EAS and EAX. The following inclusions are trivial. Property 4.2. The following holds:

(i) ∀δ < δ EAS[δ] ⊆ EAS[δ ]; (ii) ∀γ < γ , ∀ρ, EAX[γ, ρ] ⊆ EAX[γ , ρ]; (iii) ∀γ, ∀ρ < ρ, EAX[γ, ρ] ⊆ EAX[γ, ρ ].
An interesting question is whether these inclusions are strict or not. Let us consider the strong exponential time hypothesis (SETH) [START_REF] Impagliazzo | On the complexity of k-sat[END_REF], which claims that there is no constant γ < 2 such that SAT is solvable in time O * (γ n ). Proof. We first deal with the first inclusion Let δ and δ be two real numbers such that 1 < δ < δ . We create a problem where the value of solutions is either 0 or 1, and such that it is solvable in O * (δ" n ) for some δ , δ < δ < delta (and hence is in EAS[δ ]) but not in O * (δ n ) under SETH (and hence not in EAS[δ] since obviously any approximate solution allows to solve optimally the problem).

Let P δ,δ be the following problem. An instance of the problem is a set of n variables (x 1 , . . . x n ), n non-negative integers (a 1 , . . . , a n ) such that the average value a i = n i=1 a i /n lies in the interval (ln(δ)/ ln(2), ln(δ )/ ln(2)], and a polynomially computable function f : N n → {0, 1}. Every variable x i can take values from 0 to 2 ai -1 (this defines the set of feasible solutions), and the value of a solution is f (x 1 , . . . , x n ), to be maximized. This problem is obviously in NPO.

Note that n i=1 2 ai = 2 n i=1 ai ≤ δ n , so an exhaustive search allows to solve the problem in time O * (δ n ). Now, take an instance of SAT with N variables. Let n = ln(2)N/ ln(δ ) . Note that:

ln(2)N ln (δ ) ≤ n < ln(2)N ln (δ ) + 1 =⇒ ln(2) ln (δ ) ≤ n N < ln(2) ln (δ ) + 1 N ≤ ln(2) ln(δ)
for N large enough. Then choose n nonnegative integers a i such that n i=1 a i = N . Intuitively, if for instance a i = 2 this means that our variable x i will have value in {0, 1, 2, 3} which allows to simulate 2 variables of the SAT instance. In this way, since n i=1 a i = N , each variable of the SAT instance is simulated in our set of n variables with value in {0, . . . , 2 ai -1}. The function f is now trivial: its value is 1 if (x 1 , . . . , x n ) corresponds to a truth value that satisfies the SAT instance, and 0 otherwise. Now, note that δ n < 2 n i=1 ai = 2 N , so an algorithm solving P δ,δ in O * (δ n ) would contradict SETH.

The same argument shows the second claimed inclusion. Take a problem that is not solvable in O * (γ n ) under SETH like in the above construction but define the values to be either 1 or ρ (instead of either 1 or 0).

For the third one, simulate with the previous trick SAT by a problem not solvable in O * (δ n ) under SETH, and state f (x 1 , . . . , x n ) = 1 if this corresponds to a satisfying assignment, and f (x 1 , . . . , x n ) = ρ otherwise. Any solution is a ρ approximation, while getting a ρ approximation would solve SAT.

FPT and exponential time approximation schemata

As pointed out in Section 1, our main concern in this article is to provide sufficient conditions for a problem solvable in time O * (γ n ) to be in EAS[γ]. To this aim, we provided in Section 2 and 3 a general method to derive exponential time approximation schemata. We now show that schemata can be also derived in an easy way for FPT problems having some basic properties. Property 4.4. Let Π be a maximization (resp., minimization) problem in FPT solvable in O * (δ k ) such that:

1. the value of any feasible solution is at most n (n is the size of the instance); 2. if there exists a solution of value k, then there is a solution of value l, for any l k (resp., for any k l n).

Then Π is also in EAS[δ], and it is possible to reach any approximation ratio ρ in computation time O * (δ ρn ) (resp., O * (δ n/ρ )).

Proof. Let us first consider that Π is a maximization problem. Given a ρ ∈ (0, 1), we apply the parameterized algorithm with every value for k between 0 and ρn. If the best solution has value at most ρn, we find it. Otherwise, the optimum value is between ρn and n, hence there is a solution of value ρn. We will find such a solution, that trivially achieves an approximation ratio ρ. The complexity is clearly in O * (δ ρn ).

If Π is a minimization problem, for ρ ≥ 1, we apply the parameterized algorithm with every value for k between 0 and n/ρ. If no solution is found, we output any feasible solution (by hypothesis we know how to compute a feasible solution in polynomial time). If the optimal value is at most n/ρ we find it. Otherwise, any feasible solution achieves an approximation ratio ρ. The complexity is O * (δ n/ρ ).

The conditions in Property 4.4 are not very restrictive and applies to a large range of problems, including for instance Min Vertex Cover, Max SAT, . . . On the basis of what has been discussed in this section, we conclude the paper by sketching a class-landscape for parameterized approximation. As mentioned in introduction, several recent articles aim at combining parameterized complexity and approximation algorithms (see, for instance, [START_REF] Marx | Parameterized complexity and approximation algorithms[END_REF]). Note that we only consider here the standard parameterization.

Class 3 (AFPT). A problem is in AFPT[ρ]

if there exists a function f such that, for any instance of size n, it is possible in time O * (f (k, ρ)) either to find a solution of value at least ρk or to show that there is no solution of value k.

A similar definition can be given for minimization problems.

Class 4 (ASFPT)

. A problem is said to have an ASFPT if it is in AFPT[ρ] for any ρ = 1.

Clearly, we know that FPT ⊆ AFPT[ρ] for any ρ. Though there does not exist to our knowledge a "natural" problem that distinguishes between these classes, the inclusion is indeed strict. Take a ρ > 1 and the following problem: given a graph G, feasible solutions are proper colorings of G, and a coloring has value 3 if it uses at most 3 colors and 3ρ otherwise. Clearly, this problem is ρ approximable in polynomial time (hence in FPT time) and is not in XP (so not in FPT) unless P = NP. We also know that APX[ρ] ⊆ AFPT[ρ] (where APX[ρ] denotes the set of problems ρ-approximable in polynomial time). Note that Min Vertex Cover is in FPT but is NP-hard to approximate with ratio ρ < 1.36 [START_REF] Dinur | The importance of being biased[END_REF]. This shows strict inclusion for ratios ρ < 1.36. An amplification of the value of solutions allows to extend the strict inclusion for any ratio ρ: take t such that 1.36 t > ρ, and define a modified vertex cover problem where the value of a vertex cover V is |V | t . Then the problem is still FPT but a polytime approximation ratio smaller than 1.36 t would solve vertex cover within ratio 1.36. Finally, in the field of approximation parameterized algorithms, strong negative results have been obtained for Min Independent Dominating Set 11 by [START_REF] Downey | Parameterized approximation problems[END_REF], leaving as open questions the existence of approximation parameterized algorithms for Max Independent Set and Min Dominating Set. As a last result, we deduce from the self-improvement property of Max Independent Set [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF] that either Max Independent Set has a parameterized approximation schema or it does not admit constant approximation parameterized algorithms for any ratio. Note that this result has been used in [START_REF] Bonnet | On subexponential and fpt-time inapproximability[END_REF] to obtain conditional negative results for the existence of parameterized approximation algorithms for Max Independent Set. Proof. We suppose that Max Independent Set is AFPT[ρ], which means that we have an algorithm with complexity O(f (k)poly(n)) (with poly a polynomial function) that either outputs an independent set of size at least ρk or outputs no (and in this latter case there is no independent set of size k). Let G(V, E) be a graph of size n. We build a new graph G [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF] with n 2 vertices V i,j , with 1 i n and 1 j n. There is an edge between (i 1 , j 1 ) and (i 2 , j 2 ) if:

• i 1 = i 2 and (j 1 , j 2 ) ∈ E;

• i 1 = i 2 and (i 1 , i 2 ) ∈ E.

First, we remark that if we have an independent set of size k in G, then we have an independent set of size k 2 in G . Reciprocally, if we have an independent set of size k in G , then we can find an independent set of size √ k in G:

• either this independent set has vertices in more than √ k copy of G, and then the numbers of these copy give an independent set on G;

• or is has vertices in less than √ k copy of G, and then there is at least √ k vertices in one of them, which gives an independent set on G too.

When given a graph G and a parameter k, we apply our parameterized algorithm to G with the parameter k 2 . If the algorithm outputs no, then we know that there is no independent set of size k in G and we output no too. Else, the algorithm outputs an independent set of size ρk 2 on G . We know that this leads to an independent set of size √ ρk on G. The complexity of this new algorithm O(f (k 2 )p(n 2 )). In other words, we know that Max Independent Set is now AFPT[ √ ρ]. Iterating this process proves the claimed result.

Figure 1 .

 1 Figure 1. Branching rule.

4 end 5 Proposition 2 . 2 .

 522 Output the solution of the tree's root. Algorithm 1 gives an optimal solution in time O * (γ p0 ), with γ the only positive solution of the equation 1 = r i=1 γ -ai .

Figure 2 .

 2 Figure 2. Diminution rule.

Theorem 2 . 5 .'Figure 3 .

 253 Figure 3. Illustration of Algorithm 2.

Theorem 2 . 6 .

 26 For a minimization problem, with the new set of properties, Algorithm 2 outputs a ρ-approximate solution in time O * (γ p ρ ), where γ ρ is the only positive root of the equation 1 = r i=1 γ -ai-si(ρ-1) ρ . Proof. To prove the correctness, we have nearly the same property as in the demonstration of the maximization case: each non-leaf node [I, α] in the tree has at least one child [I , α ] with a payback function PB, and satisfying:

Figure 4 .

 4 Figure 4. Approximating Feedback Vertex Set. The grey area represents the improvement over the existing.

Property 4 . 1 .

 41 If an NPO maximization problem has a full γ-exponential approximation schema and is polynomially bounded 10 , then it can be solved in time O * (γ n ).

Property 4 . 3 .

 43 Assuming SETH:(i) ∀δ < δ EAS[δ] EAS[δ ]; (ii) ∀γ < γ , ∀ρ, EAX[γ, ρ] EAX[γ , ρ]; (iii) ∀γ, ∀ρ < ρ, EAX[γ, ρ] EAX[γ, ρ ].

Property 4 . 5 .

 45 ∀ρ, FPT AFPT[ρ], unless P = NP.

Property 4 . 6 .

 46 ∀ρ, APX[ρ] AFPT[ρ] unless P = NP.

Theorem 4 . 7 .

 47 If there is a ratio ρ such as Max Independent Set is in AFPT[ρ], then it is also in AFPT[1-],for any .

Given a set of binary variables and a set of clauses, Max SAT is to find a truth assignment of variables that maximizes the number of satisfied clauses. Max kSAT is a restricted version where each clause contains exactly k literals.

Note that speaking of (sub)exponential time algorithm requires to have defined a parameter representing the size of the instance, such as the number of vertices in a graph, with respect to which the complexity is measured.

Note that in this article, with a slight abuse of notation, O * (F (p)) means F (p)q(|I|) for some polynomial q.

Maximization problems where, given an instance I, feasible solutions are subsets of a given set S that satisfy a given hereditary property π (if S ⊆ S satisfies π, then any S ⊆ S satisfies π), the goal being to maximize the size of the subset.

This is obviously the case for any parameterized problem in XP.

Note that branching algorithms usually use reduction rules that are polynomial time rules applied on each node to simplify the instance. Reduction rules can be formally incorporated in the branching rule, so we do not need to state them explicitly.

Given a graph G on n vertices, the goal is to find a proper coloring of G maximizing n -k where k is the number of colors of the coloring.

This means that the value of a solution is bounded by a polynomial in the size of the instance.

* Research supported by the French Agency for Research under the DEFIS program TODO, ANR-09-EMER-010


M B Doost

Resonant-state-expansion Born approximation with a correct eigen-mode normalisation

Keywords: numbers: 03.50.De, 42.25.-p, 03.65.Nk

The Born approximation (Born 1926 Z.Phys.38.802) is a fundamental result in physics, it allows the calculation of weak scattering via the Fourier transform of the scattering potential. As was done by previous authors (Ge et al 2014 New J. Phys. 16 113048) the Born approximation is extended by including in the formula the resonant-states (RSs) of the scatterer. However in this study unlike previous studies the included eigen-modes are correctly normalised with dramatic positive consequences for the accuracy of the method. The normalisation of the RSs used in the previous RSE Born approximation or resonant-state-expansion Born approximation made in Ge et al (2014 New J. Phys. 16 113048) has been shown to be numerically unstable in Muljarov et al (2014 arXiv:1409.6877) and by analytics here. The RSs of the system can be calculated using my recently discovered RSE perturbation theory for dispersive electrodynamic scatterers (Muljarov et al 2010

I. INTRODUCTION

Fundamental to scattering theory, the Born approximation consists of taking the incident field in place of the total field as the driving field at each point inside the scattering potential, it was first discovered by Max Born and presented in Ref. [1]. The Born approximation gave an expression for the differential scattering cross section in terms of the Fourier transform of the scattering potential. The Born approximation is only valid for weak scatterers as we will see in the numerical demonstrations.

In this paper I provide an extension to the Born approximation which allows an arbitrary number of resonant states (RSs) to be taken into account. I have named this extension to the Born approximation the Resonantstate-expansion correction to the Born approximation or the RSE Born approximation. An almost identical approach is already available in the literature [2] however its derivation differed by including an unstable normalisation formula for the RS eigen-modes of the system which was then subsequently used to expand Born's approximation incorrectly. The normalisation derived in Ref. [15] and used in the previous RSE Born approximation made in Ref. [2] has been shown to be numerically unstable in Ref. [10] and shown to be unstable using analytics in Appendix C. Furthermore the numerical study made in Ref. [2] only included a single RS in the expansion of the Born approximation, most likely to avoid divergence caused by their incorrect normalisation of the RSs.

Recently there has been developed [3,8,9] a rigorous perturbation theory called resonant-state expansion (RSE) which was then applied to one-dimensional (1D), 2D and 3D systems [4-7, 11, 12] which only calculates the modes and makes no use of them. The RSE accurately and efficiently calculates RSs of an arbitrary system in terms of an expansion of RSs of a simpler, unperturbed one. RSs are normalised correctly to appear in spectral Green's functions (GFs) via the flux volume normalisation [7] and hence the RSE Born approximation. In the limit where an infinite number of these resonances are included in the RSE Born approximation we will observe convergence of the method towards the exact solutions. That the RSE can reproduce both the correctly normalised RS fields as well as frequencies was demonstrated in Ref. [4] with the convergence and extrapolation algorithm which I contributed to that paper.

Interestingly the resonant-state-expansion is a near identical translation to Electrodynamics of a much earlier theory from Quantum Mechanics by More, Gerjuoy, Bang, Gareev, Gizzatkulov and Goncharov Ref. [8,9]. The only difference between the two approaches is the choice of RS normalisation method. I am able to show in this manuscript that the general normalisation of resonant-states which I derived in Ref. [7] is the most numerically stable available normalisation method. The general normalisation which I derived in Ref. [7] is based on a prototype normalisation which appeared in Ref. [3].

The concept of RSs was first conceived and used by Gamow in 1928 in order to describe mathematically the process of radioactive decay, specifically the escape from the nuclear potential of an alpha-particle by tunnelling. Mathematically this corresponded to solving Schrödinger's equation for outgoing boundary conditions (BCs). These states have complex frequency ω with negative imaginary part meaning their time dependence exp(-iωt) decays exponentially, thus giving an explanation for the exponential decay law of nuclear physics. The consequence of this exponential decay with time is that the further from the decaying system at a given instant of time the greater the wave amplitude. An intuitive way of understanding this divergence of wave amplitude with distance is to notice that waves that are further away have left the system at an earlier time when less of the particle probability density had leaked out. There already exists numerical techniques for finding eigenmodes such as finite element method (FEM) and finite difference in time domain (FDTD) method to calculate resonances in open cavities. However determining the effect of perturbations which break the symmetry presents a significant challenge as these popular computational techniques need large computational resources to model high quality modes. Also these methods generate spurious solutions which would damage the accuracy of the RSE Born approximation if included in the basis.

The paper is organized as follows, Sec. II outlines the derivation of the RSE Born approximation, Sec. III discusses normalisations of RSs by other authors, Sec. IV outlines the application of the RSE Born approximation to planar slabs, Sec. V gives the numerical validation of the new method along with a comparison of the alternative RSE approaches.

II. DERIVATION OF THE RSE BORN APPROXIMATION

I will in the following section re-derive the method for calculating the full GF of an open electrodynamic system in the same way as Ref. [2] however unlike previous authors I use the numerically stable normalisation of RSs which I derived in Ref. [7,12]. These methods are required to calculate transmission and scattering crosssection from the dispersive RSE perturbation theory with mathematical rigour and accuracy.

For an electrodynamic system with local frequency dependent dielectric permittivity tensor εk (r) and permeability µ = 1, where r is the three-dimensional spatial position, Maxwell's wave equation for the electric E(r)field with a current source J(r) oscillating at frequency k, which can be real or complex, is

-∇ × ∇ × E(r) + k 2 εk (r)E(r) = ik 4π c J(r) . (1)
The time-dependent part of the field is given by exp(-iωt) with the complex eigen-frequency ω = ck, where c is the speed of light in vacuum. The Green's function (GF) of an open electromagnetic system is a tensor Ĝk which satisfies Maxwell's wave equation Eq. (1) with a delta function source term,

-∇ × ∇ × Ĝk (r, r ′ ) + k 2 εk (r) Ĝk (r, r ′ ) = 1δ(r -r ′ ) , (2)
where 1 is the unit tensor. Physically, the GF describes the response of the system to a point current with frequency ω, i.e. an oscillating dipole.

The importance of Ĝk comes from the fact we can see from Eqs. (2) that Eqs. (1) can be solved for E(r) by convolution of Ĝk with the current source J(r ′ ),

E(r) = Ĝk (r, r ′ )ik 4π c J(r ′ )dr ′ . (3)
Inside the system we can use the RSE to calculate the GF. In Appendix A I derive for dispersive systems (for which I have recently developed a dispersive RSE perturbation theory [11,12]) a convenient form of the spectral GF, valid inside the scatterer only, Ĝk (r,

r ′ ) = n E n (r) ⊗ E n (r ′ ) 2k(k -k n ) . ( 4
)
The E n are RSs of the open optical system and are defined as the eigen-solutions of Maxwell's wave equation,

∇ × ∇ × E n (r) = k 2 n εk (r)E n (r) , (5)
satisfying the outgoing wave BCs. I have also taken the resonator to be embedded in free space (ε = 1) without loss of generality. Here, k n is the wave-vector eigen-value of the RS numbered by the index n, and E n (r) is its electric field eigen-function. The RSs which are solutions of Eq. ( 5) which are either stationary or decaying in time.

Modes appearing in Eq. ( 4) are normalized [7,12] according to the flux-volume normalisation

δ 0,kn + 1 = V E n (r) • ∂(k 2 εk (r)) ∂(k 2 ) k=kn E n (r)dr (6) + lim k→kn SV E n • ∇E -E • ∇E n k 2 -k 2 n dS ,
where the first integral is taken over an arbitrary simply connected volume V enclosing the inhomogeneity of the system and the center of the spherical coordinates used, and the second integral is taken over its surface S V . This normalization is required [7] for the validity of the spectral representation Eq. ( 4). Numerically Eq. ( 6) has been validated by its use in RSE perturbation theory [4-7, 11, 12]. A discussion of the dispersive RSE for nano-particles is given in Appendix B. The generalisation of my Eq. ( 6) to k n = 0 modes is attributable solely to E. A. Muljarov in Ref. [7] (I derived the normalisation proof for Ref. [7] without k = 0 modes), however that part of the proof of the normalisation can only be further generalised to dispersive systems using the spectral GF Eq. ( 4) derived in Appendix A. The required derivation is identical except that it makes use of the rigorously derived spectral GF Eq. ( 4) instead of the identical GF derived in a less mathematically rigorous way for non-dispersive systems. This last step is vital for the accuracy of the method. Further I note that just as I explained in Ref. [12] εk must be a symmetric matrix or a scalar in order to calculate the dispersion factor as shown.

Various schemes exist to evaluate the surface integral limit in Eq. ( 6) such as analytic methods in Ref. [3,7,10] or numerically extending the surface into a nonreflecting, absorbing, perfectly matched layer where it vanishes.

The derivation of the RSE Born approximation by Ge et al. [2] has been made using the normalization introduced by Leung et al. [15] the limit of infinite volume V is taken:

1 = lim V →∞ V ∂k 2 εk (r) ∂(k 2 ) k=kn E 2 n (r)dr+ i 2k n SV E 2 n (r)dS , (7)
It was numerically found [13] that the surface term was leading to a stable value of the integral for the relatively small volumes available in 2D finite difference in time domain (FDTD) calculations. However, it was discovered at the time that this was not the case for low-Q modes. It was wrongly shown by Muljarov et al [10] that Eq. ( 7) is actually diverging in the limit V → ∞, and therefore the expansion of the Born approximation in [2] and the normalization Eq. ( 7) are incorrect. In Appendix C I provided a mathematically rigorous disproof of some of E. A. Muljarov's points and make some correct points about the unsuitability of Eq. ( 7) for the RSE perturbation theory myself. Hence although being a cornerstone of the scattering theory of open systems the correct expansion of the Born approximation in terms of RSs to the exact solution was not previously available.

Analogously to Ref. [2] the derivation of the RSE Born approximation of Ge et al. [2] is made but in this case using my correct normalisation formula for modes.

That the E n (r) and k n can be calculated accurately by the RSE perturbation theory and normalised correctly by Eq. ( 6) makes possible the RSE Born approximation.

The free space GF Ĝfs k is now introduced

-∇ × ∇ × Ĝfs k (r, r ′ ) + k 2 Ĝfs k (r, r ′ ) = 1δ(r -r ′ ) , (8)
which has the solution,

Ĝfs

k (r, r ′ ) = - e ik|r-r ′ | 4π|r -r ′ | 1 , (9)
The systems associated with Ĝk and Ĝfs k are related by the Dyson Equations perturbing back and forth with ∆ε

k (r) = εk (r) -1 [2], Ĝk (r, r ′′ ) = Ĝfs k (r, r ′′ ) (10) -k 2 Ĝfs k (r, r ′′′ )∆ε k (r ′′′ ) Ĝk (r ′′′ , r ′′ )dr ′′′ , Ĝk (r ′′′ , r ′′ ) = Ĝfs k (r ′′′ , r ′′ ) (11) -k 2 Ĝk (r ′′′ , r ′ )∆ε k (r ′ ) Ĝfs k (r ′ , r ′′ )dr ′ ,
Combining Eq. ( 10) and Eq. ( 11) it is obtained as in Ref. [2] Ĝk (r, r ′′ ) = Ĝfs k (r, r ′′ )

-k 2 Ĝfs k (r, r ′ )∆ε k (r ′ ) Ĝfs k (r ′ , r ′′ )dr ′ + k 4 Ĝfs k (r, r ′ )∆ε k (r ′ ) Ĝk (r ′ , r ′′′ ) × ∆ε k (r ′′′ ) Ĝfs k (r ′′′ , r ′′ )dr ′′′ dr ′ . ( 12
)
In order to improve the numerical performance further I make a final few steps as in the original Born approximation [1], I define unit vector r such that r = rr and k s = kr. Then for r >> r ′ ,

k|r -r ′ | = kr ± k s • r ′ + O 1 r > 0 (13)
Therefore substituting Eq. ( 4) and Eq. ( 9) in to Eq. ( 12) and using Eq. ( 13) because both r, r ′′ are far from the scatterer we arrive at the RSE Born approximation Ĝk (r,

r ′′ ) = - e ik|r-r ′′ | 4π|r -r ′′ | 1 -k 2 e ik(r+r ′′ ) 16π 2 rr ′′ e i(ks-k ′′ s )•r ′ ∆ε k (r ′ )dr ′ + k 3 e ik(r+r ′′ ) 16π 2 rr ′′ n A n (k s ) ⊗ A n (-k ′′ s ) 2(k -k n ) . (14)
or using Eq. (A1) instead Ĝk (r,

r ′′ ) = - e ik|r-r ′′ | 4π|r -r ′′ | 1 -k 2 e ik(r+r ′′ ) 16π 2 rr ′′ e i(ks-k ′′ s )•r ′ ∆ε k (r ′ )dr ′ + k 4 e ik(r+r ′′ ) 16π 2 rr ′′ n A n (k s ) ⊗ A n (-k ′′ s ) 2k n (k -k n ) . (15)
The vector A n is defined as a Fourier transform of the RSs,

A n (k s ) = e iks•r ′ ∆ε k (r ′ )E n (r ′ )dr ′ . (16)
I note that the fast Fourier transform method is available. Furthermore I note that for the inverse scattering problem at resonance the inverse Fourier transformation is also available. The first two terms in Eq. ( 15) correspond to the standard Born approximation, the final summation term corresponds to the RSE correction to the Born approximation.

A simple corollary of this theory is as follows, we can see from the arguments just stated that from Eq.( 10) if r ′′ is inside the resonator and r >> r ′′ then Ĝk

(r, r ′′ ) = - e ik|r-r ′′ | 4π|r -r ′′ | 1 + k e ikr 4πr n A n (k s ) ⊗ E n (r ′′ ) 2(k -k n ) , (17)
or using Eq. (A1) instead Ĝk (r,

r ′′ ) = - e ik|r-r ′′ | 4π|r -r ′′ | 1 + k 2 e ikr 4πr n A n (k s ) ⊗ E n (r ′′ ) 2k n (k -k n ) , (18)
similarly from Eq.( 11) if r is inside the resonator and

r ′′ >> r then Ĝk (r, r ′′ ) = - e ik|r-r ′′ | 4π|r -r ′′ | 1 + k e ikr ′′ 4πr ′′ n E n (r) ⊗ A n (-k ′′ s ) 2(k -k n ) , (19)
or using Eq. (A1) instead Ĝk (r,

r ′′ ) = - e ik|r-r ′′ | 4π|r -r ′′ | 1 + k 2 e ikr ′′ 4πr ′′ n E n (r) ⊗ A n (-k ′′ s ) 2k n (k -k n ) , (20)
other permutations are possible.

III. OTHER NORMALISATIONS A. Normalisation by Sauvan and co-workers

The rigorously derived normalisation of Sauvan and co-workers that they gave in Ref. [18] as

2 = V E n (r) • ∂(k 2 εk (r)) ∂(k 2 ) k=kn E n (r)dr (21)
- V H n (r) • ∂(k 2 εk (r)) ∂(k 2 ) k=kn H n (r)dr ,
requires that the integral V be continued into a perfectly matched layer where it is attenuated to zero, thus eliminating the need for surface terms in the normalisation. As such it is most suitable for FEM and FDTD calculations. Further I note that just as I explained in Ref. [10] εk (r) must be a symmetric matrix or a scalar in order to calculate the dispersion factor as shown. I generate this normalisation by combining the RSE normalisation for H n and E n , I note that this alternative approach to deriving Sauvan's normalisation was discussed with E. A. Muljarov at some point but without discussing k n = 0 modes. I also note that k n = 0 modes have only H field or E field component by Maxwell's equations because they are curl free modes. k n = 0 are by definition modes which satisfy the condition of being curl free. These two points explain why the addition of k n = 0 modes to Sauvan and co-worker's normalisation takes the form it does. Actually the RSE normalisation for H n modes was first shown to me in an email attachment, by E. A. Muljarov several years ago but without any derivation and without k n = 0 modes or differential dispersion factor included.

The rigorous derivation of the relationship between normalised E-field and normalised H-field can be found in appendix D of my PhD thesis [20].

Clearly as the perturbation is increased there is a critical perturbation strength at which the RSE becomes less efficient than FDTD and FEM and beyond this point one should use the RSE Born approximation with the normalisation of Ref. [18] and FDTD or FEM.

B. Radiation mode normalisation

I have recently written a paper on the RSE Born approximation for waveguides with dispersion [12]. I found that such modes for cylindrical/effectively-2D waveguides can be normalised by reducing Maxwell's equation to effectively 2D and replacing the operation ∇×∇× with a suitable linear operator L invariant along the length of the waveguide. A similar approach is found in Ref. [19] and further comparison of the two methods is required.

IV. APPLICATION TO PLANAR SYSTEMS

In this section we discuss the application of the RSE Born approximation to exactly solvable 1D scattering problems in electrodynamics. This is in order to prove the converges of the new method to the exact solutions available for 1D problems in Sec. V. The dielectric profile is described by a scalar frequency independent dielectric profile, i.e. εk (z) = 1ε(z), ∆ε k (z) = 1∆ε(z). As unperturbed system we use a homogeneous planar slab of half width a, so that

ε(z) = ǫ s for |z| < a , 1 elsewhere . (22)

A. Wave equation and normalisation formula in 1D

In this sub-section I consider how Maxwell's wave equation transforms to 1D. I also consider how the normalisation formula transforms to 1D.

Maxwell's wave equations for a planar dielectric structure with permeability µ = 1 surrounded by vacuum is reduced for 1D to the following equation:

∂ 2 z E n (z, t) = ε(z)∂ 2 t E n (z, t) , (23)
We take the transverse eigen-modes with index n to have zero in-plane wave number. The eigen-modes can be factorised as

E n (z, t) = E n (z) exp(-ick n t)ŷ (24)
with time independent part satisfying the wave equation:

∂ 2 z + ε(z)k 2 n E n (z) = 0 , (25)
The electric field and its first derivative are continuous everywhere. Eigenmodes of Maxwell's wave equation for open systems have outgoing boundary conditions. In 1D non-dispersive systems the RSs E n (z) with frequency k n are orthogonal and normalized correctly in 1D according to [3] a

-a ε(z)E n (z)E m (z) dz - E n (-a)E m (-a) + E n (a)E m (a) i(k n + k m ) = δ nm , (26)
where z = ±a are the positions of the boundaries of the unperturbed system.

B. Resonant states of the unperturbed slab

In this sub-section I give the RSs used to calculate the RSE Born approximation in Sec. V.

Solving the wave equation Eq. ( 25) for dielectric constant ε(z) given by Eq. ( 22), the electric field of RS n, normalized according to Eq. ( 26), takes the form [3]

E n (z) =    (-1) n A n e -iknz , z < -a , B n [e i √ ǫsknz + (-1) n e -i √ ǫsknz ] , |z| ≤ a , A n e iknz , z > a , (27)
where

A n = e -ikna a(ǫ s -1) , B n = (-i) n 2 √ aǫ s , (28)
with

k n = 1 2a √ ǫ s (πn -i ln γ), n = 0, ±1, ±2, ... , (29)
and

γ = √ ǫ s + 1 √ ǫ s -1 , ( 30
)
the imaginary part of the wave vectors k n are all the same.

C. The form of the RSE Born approximation in the one dimensional case

It is demonstrated in this section that the 1D RSE Born approximation can be used in conjuncture with the RSE perturbation theory (to generate the normalised eigen-modes of planar systems with arbitrary dielectric profile and dispersion) [3,4,6,12] to offer a possible alternative to the scattering matrix method of Ref. [17]. The same method for planar waveguides can be developed in an analogous way except the eigen-modes should be calculated as in Ref. [6,12].

In 1D the GF G k (z, z ′′ ) is the solution of the equation

∂ 2 z + ε k (z)k 2 G k (z, z ′′ ) = δ(z -z ′′ ) , (31)
which from Eq. ( 4) we can see is given by

G k (z, z ′′ ) = n E n (z)E n (z ′′ ) 2k(k -k n ) . ( 32
)
The free space GF is a solution of

∂ 2 z + k 2 G k (z, z ′′ ) = δ(z -z ′′ ) , (33)
and is given by

G k (z, z ′′ ) = - e ik|z-z ′′ | 2ik . ( 34
)
Hence in 1D the RSE Born approximation is greatly simplified to

G k (z, z ′′ ) = - e ik(z ′′ -z) 2ik + e ik(z ′′ -z) 4 a -a ∆ε k (z ′ )dz ′ - ke ik(z ′′ -z) 4 n A n (k s )A n (k ′′ s ) 2(k -k n ) , (35)
where A n is defined as the Fourier transform,

A n (k s ) = a -a e iksz ′ ∆ε k (z ′ )E n (z ′ )dz ′ , (36)
which in the case of a homogeneous slab treated here is calculated to be

A n (k s ) = B n ∆ε e i(ks+ √ ǫskn)z ′ i(k s + √ ǫ s k n ) + (-1) n e i(ks-√ ǫskn)z ′ i(k s - √ ǫ s k n ) a -a
(37) Interestingly in 1D we do not require the far field approximation to make the simplification of the Green's function required to bring the RSE Born approximation to the form of Eq. (35). Hence in 1D the RSE Born approximation is valid everywhere outside of the slab and not just in the far field.

V. NUMERICAL VALIDATION

In this section we calculate the 1D GF outside of the homogeneous slab given by Eq. (22) where ǫ s = 2.25. We do this using the RSE Born approximation, analytically using boundary conditions, and also using the spectral GF for comparison. We find that the RSE Born approximation requires less basis states to reach a required accuracy than the spectral GF and unlike the spectral GF is convergent outside the system.

I calculate three types of GF in this section, an analytic GF, the GF of Eq. (32) and the GF of Eq. ( 35). From these it is possible to use the formula derived in Ref. [4,6] for normal incident and waveguide systems for the transmission T (k, z ′ ),

T (k, z ′ ) = |2kG(z ′ , -a; k)| 2 . ( 38
)
The analytic GF is found by solving Maxwell's wave equation in 1D with a source of plane waves while making use of Maxwell's boundary conditions.

The procedure used to select the basis of RSs for the RSE Born approximation calculation is analogous to that described in Ref. 7 for the RSE perturbation theory. Namely, I choose the basis of RSs such that all RSs with |k n | < k max (N ) using a maximum wave vector k max (N ) chosen to select N RSs.

From Fig. 1 we can see that unlike the standard Born approximation the RSE Born approximation is valid over an arbitrarily wide range of k depending only on the basis size N used. Furthermore we see that as the basis size increases the RSE Born approximation converges to the exact solution. The absolute error in the RSE Born approximation is approximately reduced by an order of magnitude each time the basis size is doubled. Absolute errors of 10 -7 -10 -4 are seen in the k range shown for basis size N = 401.

From Fig. 2 we can see that unlike the GF calculated with the spectral Eq. (32) the RSE Born approximation is stable over an arbitrarily wide range of z ′ , where z ′ is the coordinate of the point of transmission to, depending only on the basis size N used. The transmission calculated via the spectral GF is diverging with distance of the point of transmission from the slab, this suggests that outside the system the RSE spectral GF is not converging or is divergent. Furthermore we see that the RSE Born approximation requires fewer resonant states than the spectral GF method in order to produce a required absolute error, at all values of z ′ . Although these points were first noted by Ge et al. [2] they were using the unstable normalisation leading to an incorrect GF and so the results upon which they based their conclusions are not reliable.

VI. SUMMARY

In this work we have seen the Born approximation mathematically rigorously extended to include terms which take into account the resonances of the scattering potential using the exact same method as [2] except with correctly normalised modes. Further I have made comparisons in 1D between scattering calculated with the spectral GF and the scattering calculated using the RSE Born approximation. I have demonstrated that once the correct normalisation is used in the RSE Born approximation convergences towards the exact solution is obtained. I have found that the RSE Born approximation for finding the full GF outside of the system is superior to the other spectral GF method considered in terms of convergence and accuracy when the correct normalisation of the RSs is used.

It is demonstrated in this paper that the 1D RSE Born approximation can be used in conjuncture with the RSE perturbation theory (to generate the normalised eigenmodes of planar systems with arbitrary dielectric profile) [3,4,6,12] to offer a possible alternative to the scattering matrix method of Ref. [17]. In fact, given the superior efficiency of the RSE perturbation theory in comparison with FDTD and FEM for weak perturbations demonstrated in Ref. [7] it is likely that the RSE coupled with the RSE Born approximation will be an incredibly powerful scattering theory for weak scatterers.

I have now derived an analogous theory for general wave equations [12].

where

S na = E n (r) • ∆σ(r)E a (r)dr , (B5)
which can be solved for the eigen-modes E µ and eigenvalues k µ of the perturbed problem. For examples of fitting dispersion linear in wavelength to the dispersion of real materials for the purposes of RSE perturbation theory please see my Ref. [11] where a linear dispersive RSE is presented in terms of a generalised eigen-value problem.

The perturbation to εkµ can also be non-dispersive without resorting to generalised eigen-value problems, as treated in my Ref. [7]. To elaborate further on this point consider the problem of the non-dispersive perturbation ∆ε(r)

∇ × ∇ × E µ (r) = k 2 µ εkµ (r) + ∆ε(r) E µ (r) . (B6)
Again εkµ is dispersive as in Eq. (B1). Eq. (B6) is solved by [7] a

δ na k a + V na 2 √ k n √ k a c aµ = 1 k µ c nµ , (B7)
where

V na = E n (r) • ∆ε(r)E a (r)dr (B8) and b nµ √ k n = c nµ .
Please note that it is very important to be consistent with the signs of √ k b in the matrix elements of Eq. (B7).

Using the linear eigen-value approach outlined here it might be possible to treat an unperturbed Drude-Lorentz gold sphere with a non-dispersive shell, and perturb away the non-dispersive shell leaving in its place biological particles to be sensed as a perturbation. All perturbations must be within the boundaries of the unperturbed system due to convergence of the GF, see Fig. 2.

For a discussion of the eigen-functions of Maxwell's equations in spherical coordinates please see [21].

Appendix C: Kristensen normalisation

In order for the normalisation of Kristensen et al to be correct it must be consistent with my Eq. ( 6), specifically the surface term S RSE in Eq. ( 6) must be mathematically equivalent with Kristensen's surface term S KS . Hence it should be that S RSE = S KS , where from [3] we have,

S RSE = + 1 2k 2 n SR dS E n • ∂ ∂r r ∂E n ∂r -r ∂E n ∂r 2
, (C1) and from Eq. ( 7) we have

S KS = lim V →∞ i 2k n SV E 2 n (r)dS , (C2)
However considering the RSE Born approximation in 3D, specifically to ensure outgoing BCs Eq. ( 17) in particular driven by (convoluted with) a current vanishing proportional to (k

-k n ) as k → k n so E(r) → E n (r), we know that lim r→∞ E n (r) = f (θ, φ) e iknr r , (C3)
where r = (r, θ, φ) in spherical polar coordinates and f (θ, φ) ∝ A n (rk n ), then substituting Eq. (C3) into Eq. (C1) and Eq. (C2) and equating S RSE and S KS gives,

lim r→∞ S RSE = lim r→∞ S KS = ie 2iknr 2k n r 2 SV f 2 (θ, φ)dS , (C4)
a logically valid statement, therefore, S RSE = S KS when r → ∞ and so the normalisation of Kristensen et al is not wrong as it is stated. In the RSE perturbation theory letting r → ∞ in the normalisation of perturbed modes introduces huge errors because of the blow up of the RS mode fields far from the system causing blow up of error. By Eq. (C4), as r grows one is essentially subtracting an exponentially growing surface term from an exponentially growing volume term to get the constant 1 + δ kn,0 for normalisation, this leads to large numerical errors for low-Q (leaky) modes [13]. An inherent source of instability is remaining dependence of f (θ, φ) on r due to the use of finite r.

In 1D Kristensen et al normalisation is actually correct for any finite r that includes the system inhomogeneity [3].

The remaining problems with the Kristensen et al normalisation is that it is missing k = 0 modes, therefore it is incomplete, and hence incorrect. Also it does not have the conditions on εk which should be the same as for my normalisation. That the RSs can be written in the form of Eq. (C3) aids the solution of the inverse scattering problem [12].

As an aside, since

f (θ, φ) = k 2 n 4π A n (rk n ) , (C5)
it is theoretically possible to make calculations of the potential from the emission (decay) via fast inverse Fourier transform methods upon the set of A n (rk n ) especially if the potentials of interest are rotating about a fixed axis so we know their orientation to some extent such as occurs for decaying magnetic nuclei as part of a nonmagnetic crystalline compound placed inside a NMR (nuclear-magnetic-resonance) machine. Because k n are discrete values these inverse Fourier methods might have to be used self-consistently in conjuncture with the RSE perturbation theory and the values of k n . This is a highly speculative aside and might be a possible topic for future research.

As another aside, close to a sharp resonance k ≈ k n scattering from the potential is dominated by a single resonance and so the scattered E-field E scattered is approximately lim r→∞ E scattered (r, k) ≈ CA n (rk) e ikr r , (C6) again A n (rk) can be partially inverse Fourier transformed with respect to angle to find information about the internal structure of the potential. C is some constant. This argument assumed elastic scattering, which is a valid assumption even for such things as neutronnucleus scattering provided that the neutron energies are high enough, at low energies inelastic scattering causes deviations from the RSE Born approximation model, these deviations in scattering caused by inelasticity give the fission or absorption cross-sections. An RSE for Schrödinger's equation is given in [12]. For 2D systems, by following similar arguments as here we arrive at (in the notation of [12])

lim ρ→∞ E n (ṙ) = -ω 2 n Q √ ρπ A n ( rk n )e iknρ , (

FIG. 1 :

 1 FIG. 1: (Color online)(a) Light transmission through the slab, Eq. (38). (b) Absolute error in the transmission calculated using the analytic form of T (k, a) as comparison for the numerical values from the RSE Born approximation with N = 51, 101, 201, 401 as labelled. For further comparison the standard Born approximation is also included.

FIG. 2 :

 2 FIG. 2: Absolute error in transmission calculated using the analytic form of T (k, z ′ ), Eq. (38), between z = -a and z = z ′ as comparison for the RSE Born approximation and the spectral GF at fixed ka = 15. N = 201, 401 as labelled.

  C7)and the arguments with regards to normalisation in this Appendix C still hold except that now 1 + δ kn,0 =

					A	E n •	∂(ω 2 εω ) ∂(ω 2 ) ω=ωn	E n dṙ			(C8)
	+	R 2k 2 n	0	2π	dθ E n •	∂E n ∂ρ	+ ρE n •	∂ 2 E n ∂ρ 2 -ρ	∂E n ∂ρ	2	ρ=R	.

Appendix A: Derivation of alternative Green's function and completeness

In order to simplify the RSE Born approximation and develop Eq. ( 6) we require an appropriate spectral form of the GF which is different from the one already proven in the literature. To obtain this correct form I start with the GF valid inside the scatterer only, which I derived in Ref. [5,12]

Substituting Eq. (A1) in

since throughout the derivation in this appendix we are considering the limit where k → ∞ at which εk (r) = ε(r), i.e. the system is non-dispersive at high frequencies. Convoluting Eq. (A3) with arbitrary finite functions and assuming the series are convergent we see that since k → ∞ we have the sum rule,

Combining Eq. (A1) and Eq. (A4) yields Ĝk (r,

Combining Eq. (A3) and Eq. (A4) leads to the closure relation

which expresses the completeness of the RSs, so that any function can be written as a superposition of RSs. If in the perturbed system some of the series are not convergent or are instead conditionally convergent then we will not arrive at the sum rule and completeness, in which case I expect that the RSE Born approximation will still give convergence to the exact solution but only if a valid spectral Green's function is used, such as Eq. (A1).

Appendix B: RSE for dispersive systems

Due to the problems with non-convergence of Schur factorisation for the generalised eigen-value problem of perturbing nano-spheres dispersively, the RSE in Ref. [11] might tends to fail for non-symmetric perturbation when more than typically 500 basis states are used. This is an estimate based on the un-reported RSE failures for half and quarter sphere perturbations using the generalised eigen-value problem form of the RSE, tests which I carried out for Ref. [7]. Therefore it is necessary to add linear dispersion through a second stage perturbation, a perturbation to the possibly complex conductivity [11].

To make this perturbation consider the problem of a perturbation to the conductivity -i∆σ(r

εkµ could have in principle any dispersion for which the eigen-modes can be normalised, and which becomes nondispersive in the limit of high frequency in order to make the sum rule for the GF. In this Appendices Greek index letters denote perturbed modes and British (English) lower case index letters denote unperturbed modes.

Since

where Ĝkµ (r, r ′ ) is given by Eq. (A5) and by Eq. (A6)

where in Eq. (B3) E n and k n correspond to the unperturbed modes of Eq. ( 5), then following the derivation method of Ref. [8,9] 2b nµ k µ = a (iS na + 2δ na k a ) b aµ , (B4)