Bin Picking Robot

Abstract

The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes a1, . . , an in (0, 1]. Using uniform sampling, which selects a random element from the input list each time, we develop a randomized O( n(log n)(log log n)

Ǫ )) Time (1+Ǫ)-

approximation scheme for the bin packing problem. We show that every randomized algorithm

Pn

i=1 ai ) time to give an (1 + ǫ)-approximation. For

Each Function S(N) : N →N, Define P

(s(n)) to be the set of all bin packing problems with the sum of item sizes equal to s(n). For a constant b ∈(0, 1), every problem in P

Ǫ )O( 1

ǫ )) time (1 + ǫ)-approximation for an arbitrary constant ǫ. On the other hand, there is no o(n1−b) time (1 + ǫ)-approximation scheme for the bin packing

Problems In P

(nb) for some constant ǫ > 0.

(Nb) Is Np-Hard For Every

b ∈(0, 1]. This implies a dense sublinear time hierarchy of approximation schemes for a class of NP-hard problems, which are derived from the bin packing problem. We also show a randomized streaming approximation scheme for the bin packing problem such that it needs only constant updating time and constant space, and outputs an (1 + ǫ)-approximation in ( 1

Ǫ ) Time. Let

S(δ)-bin packing be the class of bin packing problems with each input item of size at least δ. constant time approximation scheme, and a constant time and space sliding window streaming approximation scheme, where δ is a positive constant.

Ntroduction

The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes a1, . . , an in (0, 1]. It is a classical NP-hard problem and has been widely studied. The bin packing problem has many applications in the engineering and information sciences.

Some

approximation algorithm has been developed for bin packing problem: for examples, the first fit, best fit, sum-of-squares, or Gilmore-Gomory cuts [2, 8, 7, 16, 15]. The first linear time approximation scheme is shown in . Recently, a sublinear time O(√n) with weighted sampling and a sublinear time O(n1/3) with a combination of weighted and uniform samplings were shown for bin packing problem .

We study the bin packing problem in randomized offline sublinear time model, randomized streaming model, and randomized sliding window streaming model. We also study the bin packing problem that has input item sizes to be random numbers in [0, 1]. Sublinear time algorithms have been found for many computational problems, such as checking polygon intersections , estimating the cost of a minimum spanning tree [6, 9, 10], finding geometric separators , and property testing [22, 17], etc.

Early research on streaming algorithms dealt with simple statistics of the input data streams, such as the median , the number of distinct elements , or frequency moments . Streaming algorithm is becoming more and more important due to the development of internet, which brings a lot of applications. There are many streaming algorithms that have been proposed from the areas of computational theory, database, and networking, etc.

Due to the important role of bin packing problem in the development of algorithm design and its application in many other fields, it is essential to study the bin packing problem in these natural models. Our offline approximation scheme is based on the uniform sampling, which selects a ran- dom element from the input list each time. Our first approach is to approximate the bin packing problem with a small number of samples under uniform sampling. We identify that the complexity of approximation for the bin packing problem inversely depends on the sum of the sizes of input Using uniform sampling, we develop a randomized O( n(log n)(log log n)

Ǫ )) Time (1 + Ǫ)-

approximation scheme for the bin packing problem. We show that every randomized algorithm with

Pn

i=1 ai ) time to give an (1 + ǫ)-approximation. Based on an adaptive random sampling method developed in this paper, our algorithm automatically detects an approximation to the weights of summation of the input items in time O( n(log n)(log log n)

) Time, And

then yields an (1 + ǫ)-approximation. For each function s(n) : N →N, define P(s(n)) to be the set of all bin packing problems with the sum of item sizes equal to s(n). For a constant b ∈(0, 1), every problem in P(nb) has an

Ǫ)O( 1

ǫ )) time (1 + ǫ)-approximation for an arbitrary constant ǫ. On the other hand, there is no o(n1−b) time (1 + ǫ)-approximation scheme for the bin packing problems in P(nb) for some constant ǫ > 0. We show that P(nb) is NP-hard for every b ∈(0, 1]. This implies a dense sublinear time hierarchy of approximation schemes for a class of NP-hard problems that are derived from bin packing problem. We also show a randomized single pass streaming approximation scheme for the bin packing problem such that it needs only constant updating time and constant space, and outputs an (1 + ǫ)-approximation in ( 1

Ǫ)O( 1

example of NP-hard problem that has a constant time approximation scheme, and a constant time and space sliding window single pass streaming approximation scheme. The streaming algorithms in this paper for bin packing problem only approximate the minimum be changed at different moment. This has no contradiction with the existing lower bound [4, 19] that no approximation scheme exists for online algorithm that does not change bins of already packed A more general model of bin packing is studied in this paper. Given a list of items in (0, 1], allocate them to several kinds of bins with variant sizes and weights. We want to minimize the total

Costs Pk

i=1 uiwi, where ui is the number of bins of size si and cost wi. In section 2, we give a description of computational models used in this paper. A brief description of our methods are also presented. In section 3, we show an adaptive random sampling method for the bin packing problem. In section 6, we present randomized algorithms and their lower bound for offline bin packing problem. In section 8, we show a streaming approximation scheme for bin packing problem. In section 9, we show a sliding window streaming approximation scheme for bin packing problem with each input item of size at least a positive constant δ. The main result of this paper is stated in Theorem 10.

Odels Of Computation And Overview Of Methods

Algorithms for bin packing problem in this paper are under four models, which are deterministic, randomized, streaming, and sliding windows streaming models. Definition 1.

• A bin packing is an allocation of the input items of sizes a1, . . , an in (0, 1] to bins of size 1. We want to minimize the total number of bins. We often use Opt(L) to denote the least number bins for packing items in L.

• Assume that c and η are constants in (0, 1), and k is a constant integer. There are k kinds of bins of different sizes. If c ≤si ≤1, and η ≤wi ≤1 for all i = 1, 2, . . , k, then we call the k kinds of bins to be (c, η, k)-related, where wi and si are the cost and size of the i-th kind of bin, respectively.

• A bin packing with (c, η, k)-related bins is to allocate the input items a1, . . , an in (0, 1] to (c, η, k)-related bins. We want to minimize the total costs Pk

I=1 Uiwi, Where Ui Is The Number

of bins of cost wi. We often use Optc,η,k(L) to denote the least cost for packing items in L with (c, η, k)-related bins. It is easy to see Opt(L) = Opt1,1,1(L). • For a positive constant δ, a S(δ)-bin packing problem is the bin packing problem with all input items at least δ.

• For a nondecreasing function f(n) : N →N, a P(f(n))-bin packing problem is the bin packing problem with all input items a1, . . , an satisfying Pn i=1 ai = f(n).

Deterministic Model: The bin packing problem under the deterministic model has been well studied. We give a generalized version of bin packing problem that allows multiple sizes of bins to pack them. It is called as bin packing with (c, η, k) related bins in Definition 1. It is presented in Section 5.

Randomized Models: Our main model of computation is based on the uniform random sam- pling. We give the definitions for both uniform and weighted random samplings below. Definition 2. Assume that a1, . . , an is an input list of items in (0, 1] for a bin packing problem.

• A uniform sampling selects an element a from the input list with Pr[a = ai] = 1 n for i = 1, . . , n. • A weighted sampling selects an element a from the input list with Pr[a = ai] =

I=1 Ai For

i = 1, . . , n. We feel that the uniform sampling is more practical to implement than weighted sampling. In this paper, our offline randomized algorithms are based on uniform sampling. The weighted sampling was used in . The description of our offline algorithm with uniform random sampling is given in Section 6.

Streaming Computation: A data stream is an ordered sequence of data items p1, p2, . . , pn. Here, n denotes the number of data points in the stream. A streaming algorithm is an algorithm that computes some function over a data stream and has the following properties: 1. The input data are accessed in the sequential order of the data stream. 2. The order of the data items in the stream is not controlled by the algorithm. Our algorithm for this model is presented in Section 8.

Sliding Window Model: In the sliding window streaming model, there is a window size n for Bin Packing with Random Inputs: We study the bin packing problem such that the input is a series of sizes that are random numbers in [0, 1]. It has a constant time approximation scheme and will be presented in Section 9.1.

Overview Of Our Method

We develop algorithms for the bin packing problem under offline uniform random sampling model, the streaming computation model, and sliding window streaming model (only for S(δ)-bin packing with a positive constant δ). The brief ideas are given below.

Sublinear Time Algorithm For Offline Bin Packing

Since the sum of input item sizes is not a part of input, it needs O(n) time to compute its exact value, and it’s unlikely to be approximated via one round random sampling in a sublinear time. We first approximate the sum of sizes of items through a multi-phase adaptive random sampling.

the items from the input are partitioned into intervals [π1, π0], (π2, π1] . . , (πi+1, πi], . such that π0 = 1, π1 = ϕ, and πi+1 = πi/(1 + γ) for i = 2, . .. We approximate the number of items in each interval (πi+1, πi] via uniform random sampling. Those intervals with very a small number of items will be dropped. This does not affect much of the ratio of approximation. One of worst cases is

That All Small Items Are Of Size

n2 and all large size items are of size 1. In this case, we need to

N

ai=1 1) number of items to approximate the number of 1s. This makes the total time

Pn

i=1 ai ). Packing the items of large size is adapted the method in , which uses a linear programming method to pack the set of all large items, and fills small items into those bins with large items to waste only a small piece of space for each bin. Then the small items are put into bins O(n) time. Thus, the O(n) time algorithm is a part of our algorithm for the case Pn i=1 ai = O(1).

Streaming Algorithm For Bin Packing

We apply the above approximation scheme to construct a single pass streaming algorithm for bin packing problem. A crucial step is to sample some random elements among those input items of size at least δ, which is set according to ǫ. The weights of small items are added to a variable s1. After packing large items of size at least δ, we pack small items into those bins so that each bin does not waste more than δ space while there is small items unpacked.

2.1.3. Sliding Window Streaming Algorithm for S(δ)-Bin Packing Our sliding window single pass streaming algorithm deals with the bin packing problem that all input items are of size at least a constant δ. Let n be the size of sliding window instead of the total

The Bin Packing. After Receiving Every N

k items, a new session is started to approximate the bin packing. The approximation ratio is guaranteed via ignoring at most n

Large Size At Least Δ, Ignoring N

k items only affect a small ratio of approximation. 2.1.4.

Hernoffbounds

The analysis of our randomized algorithm often use the well known Chernoffbounds, which are described below. All proofs of this paper are self-contained except the following famous theorems in probability theory and the existence of a polynomial time algorithm for linear programming.

Theorem 3 (). Let X1, . . , Xn be n independent random 0-1 variables, where Xi takes 1 with

Iµ

. We follow the proof of Theorem 3 to make the following versions (Theorem 5, Theorem 4, and Corollary 6) of Chernoffbound for our algorithm analysis.

Theorem 4. Let X1, . . , Xn be n independent random 0-1 variables, where Xi takes 1 with prob- ability at least p for i = 1, . , n.

Pr(X < (1 −Δ)Pn) < E−1

2 δ2pn. Theorem 5. Let X1, . . , Xn be n independent random 0-1 variables, where Xi takes 1 with prob- ability at most p for i = 1, . , n. Let X = Pn

Eδ

(1+δ)(1+δ) . Define g(δ) = max(g1(δ), g2(δ)). We note that g1(δ) and g2(δ) are always strictly less than 1 for all δ > 0. It is trivial for g1(δ). For g2(δ), this can be verified by checking that the function f(x) = (1 + x) ln(1 + x) −x is increasing and f(0) = 0.

This is because f ′(x) = ln(1 + x) which is strictly greater than 0 for all x > 0. Corollary 6 (). Let X1, . . , Xn be n independent random 0-1 variables and X = Pn i=1 Xi.

i. If Xi takes 1 with probability at most p for i = 1, . . , n, then for any 1

Pn + Ǫn) < E−1

3 nǫ2. ii. If Xi takes 1 with probability at least p for i = 1, . . , n, then for any ǫ > 0, Pr(X < pn−ǫn) <

E−1

2 nǫ2. A well known fact in probability theory is the inequality Pr(E1 ∪E2 . . ∪Em) ≤Pr(E1) + Pr(E2) + . + Pr(Em), where E1, E2, . , Em are m events that may not be independent. In the analysis of our randomized algorithm, there are multiple events such that the failure from any of them may fail the entire algorithm. We often characterize the failure probability of each of those events, and use the above inequality to show that the whole algorithm has a small chance to fail after showing that each of them has a small chance to fail.

Adaptive Random Sampling For Bin Packing

In this section, we develop an adaptive random sampling method to get the rough information for a list of items for the bin packing problem. We show a randomized algorithm to approximate the

Pn

i=1 ai )(log n) log log n)) time. This is the core step of our randomized algorithm, and is also or main technical contribution. Definition 7.

• For each interval I and a list of items S, define C(I, S) to be the number of items of S in I. • For ϕ, δ, and γ in (0, 1), a (ϕ, δ, γ)-partition for (0, 1] divides the interval (0, 1] into intervals I1 = [π1, π0], I2 = (π2, π1], I3 = (π3, π2], . . , Ik = (0, πk−1] such that π0 = 1, π1 = ϕ, πi = πi−1(1 −δ) for i = 2, . , k −1, and πk−1 is the first element πk−1 ≤

Γ

n2 . • For a set A, |A| is the number of elements in A. For a list S of items, |S| is the number of items in S.

Lemma 8. For parameters ϕ, δ, and γ in (0, 1), a (ϕ, δ, γ)-partition for (0, 1] has the number of

Proof:

The number of intervals k is the least integer with δ(1 −δ)k ≤(1 −δ)k ≤

Γδ

. We need to approximate the number of large items, the total sum of the sizes of items, and the Approximate-Intervals(.) below gives the estimation for the number of items in each Ij if interval Ij has a number items to be large enough. Otherwise, those items in Ij can be ignored without affecting much of the approximation ratio. We have an adaptive way to do random samplings in a series of phases. Phase t + 1 doubles the number of random samples of phase t (mt+1 = 2mt). For each phase, if an interval Ij shows sufficient number of items from the random samples, the number of items C(Ij, S) in Ij can be sufficiently approximated by ˆC(Ij, S). Thus, ˆC(Ij, S)πj also gives an approximation for the sum of the sizes of items in Ij. The sum appw = P

J ˆC(Ij, S)Πj For Those

intervals Ij with large number of samples gives an approximation for the total sum Pn

I=1 Ai Of Items

in the input list. Let mt denote the number of random samples in phase t. In the early stages,

I=1 Ai And Appw Is Close To The Sum Pn

i=1 ai of all items from the input list. This indicates that the number of random samples is sufficient for approximation algorithm. For those intervals with small number of samples, their items only need small fraction of bins to be packed.

This

process is terminated when ignoring all those intervals with none or small number of samples does not affect much of the accuracy of approximation. The algorithm gives up the process of random sampling when mt surpasses n, and switches to use a deterministic way to access the input list, which happens when the total sum of the sizes of input items is O(1). The lengthy analysis is caused by the multi-phases adaptive random samplings. We show two examples below.

Example 1: The input is a list of items such that there are three items of size 1, and the rest n −3 items are of size 0.1 for a large integer n. Assume that ǫ is a positive constant to control the accuracy of approximation. After sampling a constant 100

Number Of Items, We Observe All Samples

equal to 0.1 (with high probability). Thus, there are less than ǫn

Items Of Size Other Than 0.1 With

high probability by Chernoffbounds. We derive the approximate sum of total item sizes is 0.1n,

And Output 0.1(1+Ǫ)N

for the number bins for packing the input items, where the denominator 0.9 is based on the consideration that some bins for packing items of size 0.1 may waste up to 0.1 space. Although, there are small number of items of size 1, just ignoring those items of size 1 loses only a small accuracy of approximation. Therefore, the random sampling stops after sampling only O( 1

Ǫ)

Example 2: The input is a list of items such that there are three items are of size 1, and the

Rest N −3 Items Are Of Size

n2 for a large integer n. The number of random samples is doubled from one phase to next phase. After sampling n0.9 items, in which there is no large items of size 1 with high probability, we still feel that those items of large size will greatly affect the total number bins.

We have to continue use more random samples. Eventually, the number of random samples mt is more than n. Thus, we switch to use a deterministic O(n) time algorithm to compute the number Algorithm Approximate-Intervals(ϕ, δ, γ, θ, α, P, n, S) Input: a parameter ϕ ∈(0, 1), a small parameter θ ∈(0, 1), a failure probability upper bound α, a (ϕ, δ, γ) partition P = I1 ∪. . ∪Ik for (0, 1] with δ, γ ∈(0, 1), an integer n, a list S of n items a1, . , an in (0, 1]. Parameters ϕ, δ, γ, θ, and α do not depend on the number of items n.

Phase 0:

2. Let z := ξ0 log log n, where ξ0 is a parameter such that 8(k + 1)(log n)g(θ)z/2 < α for all large n.

Ξ0

(1−θ)c2c3 . 4. Let m0 := z.

Phase T:

Sample mt random items ai1, . . , aimt from the input list S. 9. Let dj := |{j : aij ∈Ij and 1 ≤j ≤mt}| for j = 1, 2, . ., k.

N

mt dj to approximate C(Ij, S). 13. else let ˆC(Ij, S) := 0.

C0Mt

and mt < n then enter Phase t + 1. 16.

Output Appw, App′

w and ˆC(I1, S) (the approximate number of items of size at least ϕ). 21. End of Phase t.

End Of Algorithm

Lemma 9 uses several parameters ϕ, δ, γ, α and θ that will be determined by the approximation ratio for the the bin packing problem. If the approximation ratio is fixed, they all become constants. Lemma 9. Assume that ϕ, δ, γ, α and θ are parameters in (0, 1), and those parameters do not depend on the number of items n.. Then there exists a randomized algorithm described in Approximate- Intervals(.) such that given a list S of items of size a1, . . , an in the range (0, 1] and a (ϕ, δ, γ)- partition for (0, 1], with probability at most α, at least one of the following statements is false after

Executing The Algorithm:

1. For each Ij with ˆC(Ij, S) > 0, C(Ij, S)(1 −θ) ≤ˆC(Ij, S) ≤C(Ij, S)(1 + θ);

Pn

i=1 ai , n)(log n) log log n) time. In particular, the complexity of

Pn

i=1 ai , n)(log n) log log n) if ϕ, δ, γ, α and θ are constants in (0, 1). Lemma 9 implies that with probability at least 1 −α, all statements 1 to 5 are true. Due to the technical reason described at the end of section 2.1.2, we estimate the failure probability instead of the success probability.

Proof:

Let ξ0, c0, c2, c3, c4, and c5 be parameters defined as those in the algorithm Approximate- Intervals(.). We use the uniform random sampling to approximate the number of items in each interval Ij in the (ϕ, δ, γ)-partition.

Claim 9.1. Let Q1 be the probability that the following statement is false: (i) For each interval Ij with dj ≥z, (1 −θ)C(Ij, S) ≤ˆC(Ij, S) ≤(1 + θ)C(Ij, S). Then for each phase in the algorithm, Q1 ≤(k + 1) · g(θ)

N

. An element of S in Ij is sampled (by an uniform sampling) with

Z

2mt . For each interval Ij with dj ≥z, we discuss two cases. • Case 1. p′ ≥pj. In this case, dj ≥z ≥2p′mt ≥2pjmt. Note that dj is the number of elements in interval Ij among mt random samples ai1, . . , aimt from S. By Theorem 5 (with θ = 1), with probability at most P1 = g2(1)p′mt ≤g2(1)z/2 ≤g(1)z/2, there are at least 2pjmt samples are in from interval Ij.

• Case 2. p′ < pj. By Theorem 5, we have Pr[dj > (1 + θ)pjmt] ≤g2(θ)pjmt ≤g2(θ)p′mt ≤g2(θ)

Z

2 . By Theorem 4, we have Pr[dj ≤(1 −θ)pjmt] ≤g1(θ)pjmt ≤g1(θ)p′mt = g1(θ)

Z

2 . For each interval Ij with dj ≥z and (1−θ)pjmt ≤dj ≤(1+θ)pjmt, we have (1−θ)C(Ij, S) ≤ ˆC(Ij, S) ≤(1 + θ)C(Ij, S) by line 12 in Approximate-Intervals(.).

There are k = (log n) intervals I1, . . , Ik. Therefore, with probability at most P2 = k·g(θ)

, The

following is false: For each interval Ij with dj ≥z, (1−θ)C(Ij, S) ≤ˆC(Ij, S) ≤(1+θ)C(Ij, S). By the analysis of Case 1 and Case 2, we have Q1 ≤P1 + P2 ≤(k + 1) · g(θ)

I=1 Ai

. Then right after executing Phase t in Approximate- Intervals(.), with probability at most Q2 = 2kg(θ)ξ0 log log n, the following statement is false:

I=1 Ai, A). (1 −Θ)C(Ij, S) ≤ˆC(Ij, S) ≤(1 +

θ)C(Ij, S); and B). dj ≥z.

N

. An element of S in Ij is sampled with probability pj. By

Theorem 5 And Theorem 4, We Have

Pr[dj < (1 −θ)pjmt] ≤g1(θ)pjmt ≤g1(θ)c2c3c5 log log n ≤g(θ)ξ0 log log n.

(1)

Pr[dj > (1 + θ)pjmt] ≤g2(θ)pjmt ≤g2(θ)c2c3c5 log log n ≤g(θ)ξ0 log log n.

(2)

Therefore, with probability at most 2kg(θ)ξ0 log log n, the following statement is false:

Pn

i=1 ai, (1 −θ)C(Ij, S) ≤ˆC(Ij, S) ≤(1 + θ)C(Ij, S).

≥

ξ0 log log n = z. Claim 9.3. The total sum of the sizes of items in those Ijs with C(Ij, S) < c3

Proof:

By definition 7, we have aj = ϕ(1 −δ)j−1 for j = 1, . . , k −1. We have that

Pn

i=1 ai, the sum of sizes of items in Ij is at most

Pn

i=1 ai. The total sum of the sizes of items in those Ijs with C(Ij, S) < c3

I=1 Ai) + Γ

n. Claim 9.4. Assume that at the end of phase t, for each Ij with ˆC(Ij, S) > 0, C(Ij, S)(1 −θ) ≤ ˆC(Ij, S) ≤C(Ij, S)(1 + θ); and dj ≥z if C(Ij, S) ≥c3

Appw ≤(1 + Θ)(Pn

i=1 ai) at the end of phase t.

Dj≥Z ˆC(Ij, S)Πj ≤(1 + Θ) Pn

i=1 ai. For each interval Ij with j̸ = k and j > 1, we have C(Ij, S)πj ≥(1 −δ) P

Ai∈Ij Ai By The Definition

of (ϕ, δ, γ)-partition. It is easy to see that C(I1, S)π1 ≥ϕ P

−2Γ

n ). Claim 9.5. With probability at most Q5 = (k + 1) · (log n)g(θ)

B. If Pn

i=1 ai ≥4, then the algorithm stops before mt > 2c4c5n log log n

F Pn

i=1 ai ≤4, then it stops before or at phase t in which the condition mt ≥n first becomes true.

Proof:

By Claim 9.1, with probability at most (k + 1) · g(θ)

, The Statement I Of Claim 9.1 Is

false for a fixed m. The number of phases is at most log n since mt is double at each phase. With

Z

2 , the statement i of Claim 9.1 is false for each phase t with mt ≤n. Assume that statement i of Claim 9.1 is true for all phases t with mt ≤n.

Since (1 + Θ) <

2c2c0 (by line 3 in Approximate-Intervals(.)), we have

C0Mt

. Statement B. The variable mt is doubled in each new phase. Assume that the algorithm enters

C0M

, which makes the condition at line 15 in Approximate- Intervals(.) be false. Thus, the algorithm stops at some stage t with mt ≤2c4c5n log log n

By The Setting

at line 15 in Approximate-Intervals(.). Statement C. It follows from statement A and the setting in line 15 of the algorithm.

Pn

i=1 ai , n)(log n) log log n).

Pn

i=1 ai , n)(log n) log log n) if ϕ, δ, γ, α and θ are constants in (0, 1).

Proof:

By the setting in line 3 in Approximate-Intervals(.), we have

Ξ0(1 + Δ)

(1 −θ)δ4 . In order to satisfy the condition 8(k+1)(log n)g(θ)z/2 < α for all large n at line 2 in Approximate-

Ntervals(.), We Can Let Ξ0 =

log g(θ). Since mt is doubled every phase, the total number of phases is at most log n. The computational time complexity in statement 5 of the algorithm follows from Claim 9.5.

As mt is doubled each new phase in Approximate-Intervals(.), the number of phases is at most log n. With probability at most (log n)(Q1 + Q2) + Q5 ≤α (by line 2 in Approximate-Intervals(.)), at least one of the statements (i) in Claim 9.1, (ii) in Claim 9.2, A, B, C in Claim 9.5 is false.

Assume that the statements (i) in Claim 9.1, (ii) in Claim 9.2, A, B, and C in Claim 9.5 are all true. For an interval Ij, ˆC(Ij, S) > 0 if and only if dj ≥z by lines 10 to 13 in Approximate-Intervals(.).

Therefore, statement 1 of the lemma follows from Claim 9.1. If Approximate-Intervals(.) stops at mt < n, then mt ≥2c2c5n log log n

Pn

i=1 ai, we have dj ≥z, which implies ˆC(Ij, S) > 0. Statement 2 of Lemma 9 follows from Claim 9.3 and statement (ii) of Claim 9.2. Statement 3 follows from Claim 9.4. The condition of Statement 4 implies n ≥4. Statement 4 follows from Statement 3. Statement 5 for the running time follows from Claim 9.6.

Thus, with probability at most α, at least one of the statements 1 to 5 is false. 4.

Ain Results

We list the main results that we achieve in this paper.

The Proof Of Theorem 10 Is Shown In

Section 6.3. Theorem 10 (Main). Approximate-Bin-Packing(.) is a randomized approximation scheme for the bin packing problem such that given an arbitrary τ ∈(0, 1) and a list of items S = a1, . . , an in (0, 1] for the bin packing problem, it gives an approximation app with Opt(S) ≤app ≤(1 + τ)Opt(S) + 1

Τ )) Time With Probability At Least 3

4. We show a lower bound for those bin packing problems with bounded sum of sizes Pn

I=1 Ai. The

lower bound always matches the upper bound. Theorem 11. Assume f(n) is a nondecreasing unbounded function from N to N with f(n) = o(n). Every randomized (2−ǫ) approximation algorithm for bin packing problems in P(f(n)) needs Ω(

F(N))

time, where ǫ is an arbitrary small constant in (0, 1).

Proof:

Since f(n) is unbounded, assume n is large enough such that (f(n) + 2)(2 −ǫ) < 2(f(n) −2).

(4)

The first list contains m = 2(f(n) −2)) elements of size 1

+

2(f(n)−2)) + 1 = f(n). Therefore, the first list is a bin packing problem is in P(f(n)). The second list contains n −f(n) elements of size γ and the rest f(n) items are of size equal to

F(N)

= o(1). We have f(n)(1 −τ) + (n −f(n))γ = f(n). The second list is also a bin packing problem is in P(f(n)). Both γ and τ are small. Packing the first list needs at least 2(f(n)−2) bins. Packing the second list only needs at most f(n) + 2 bins since two bins of size one is enough to pack those items of size τ.

Assume that an algorithm only has computational time o(

F(N)) For Computing (2 −Ǫ)-

approximation for bin packing problems in P(f(n)).

Access At Least One Item Of Size At Least 1

2 in both lists. Therefore, the two lists have the same output for approximation by the same randomized algorithm. For the second list, the output for the number of bins should be at most (f(n) + 2)(2 −ǫ). By inequality (4), it is impossible to pack the first list

Pn

i=1 ai ) time randomized approximation scheme algorithm for the bin packing problem.

Proof:

It follows from Theorem 11. 5.

Generalization Of The Deterministic Algorithm

In this section, we generalize the existing deterministic algorithm to handle the bin packing problem with multiple sizes of bins. The bin packing problem is under a more general version that allows different size of bins with different weights (costs). The results of this section are used as Definition 13.

• For an item y and an integer h, define yh to be h copies of item y. • A type Ti of a bin of size s is represented by (ab1,i

), Which Satisfies Pt

j=1 bj,iai ≤s. A bin of type Ti can pack b1,i items of size a1, . . ,, and bt,i items of size at. We use wTi to represent the weight of a bin of type Ti.

It is easy to see that an optimal bin packing with (c, η, k)-related bins only uses bins with si1 < si2 < . . < sik with wi1 < wi2 < . < wik. The classical bin packing problem only has one kind of bins of size 1. It is the bin packing problem with the (1, 1, 1)-related bins. In the rest of this paper, a bin packing problem without indicating (c, η, k)-related bins means the classical bin packing problem.

Lemma 14. Assume that c, η, and k are constants. Assume that δ is a constant. Given a bin packing problem with (c, η, k)-related bins for B = {an1

Δ )

time algorithm to give a solution (x1, . . , xq) with at most Optc,η,k(B) + Pq

I=1 Wti, Where Xi Is The

number of bins of type Ti, and q is the number of types to pack items of sizes in {a1, . . , am} with

Proof:

Since ai is at least δ, the number of items in each bin is at most 1

Of Types Of Bins Is At Most Km

δ . Let T1, . . , Tq be the all of the possible types of bins to pack the items of size a1, . , am. Let xi be the number of bins with type Ti. We define the linear programming conditions:

, Anm

m } to be packed in (c, η, k) related bins. Output: an approximation for Optc,η,k(B).

Et Xi = ⌈X∗

i ⌉for i = 1, . . , q. Output (x1, . , xq).

End Of Algorithm

With a constant ǫ to control the approximation ratio, we define the following constants for

(10)

Lemma 15. Assume that c, η, and k are positive constants, and ǫ and δ are constants in (0, 1). Assume that the input list is S for bin packing problem with (c, η, k)-related bins and the size of each item in S is at least δ. Let ǫ be a constant in (0, 1). The constants δ, µ, ǫ1, and m are given



. Then there exists an O(n) time algorithm that gives an approximation app with Optc,η,k(S) ≤app ≤(1 + ǫ)Optc,η,k(S) for all large n, where n = |S|.

Proof:

Assume that a1 ≤a2 ≤. . ≤an is the increasing order of all input elements at least δ with n′ = |S≥δ|. Let L0 = a1 ≤a2 ≤. ≤an.

We Partition A1 ≤A2 ≤. . . ≤An Into

A1y1A2y2 . . AmymR such that each Ai has exactly h −1 elements and R has less than h elements. Using algorithm the classical algorithm, we can find the ih-th element yi each in O(n) time.

M. We Show That There Is A Small Difference

between the results of two bin packing problems for L0 and L1. 1) Assume that L0 has a bin packing solution. It can be converted into a solution for L1 via an adaption to that of L0 (see Definition 13) with a small number of additional bins.

Use the lots for the elements between yi and yi+1 in L0 to store the elements of yis, there are at most 2h yis left. Therefore, we only have at most 2h elements left. The number of bins for packing those left items is at most 2h, which cost at most 2h since 1 is the maximal cost of one bin.

2) Assume that L1 has a bin packing solution. It can be converted into a solution for L0 with a small number of additional bins. We use the lots for yi to store the elements between yi−1 and yi. We have at most 2h elements left, which cost at most 2h since 1 is the maximal cost of one bin.

The optimal number bins Optc,η,k(L0) for packing L0 is at least mhδ, which have cost at least

(11)

Let App(L0) be an approximation for L0 and App(L1) be an approximation for L1. We can obtain an (1 + ǫ/2)-approximation App(L1) for packing L1 by Lemma 14. We have that

≤

(1 + ǫ)Optc,η,k(L0). By the analysis at case 2), if App(L1) ≥Optc,η,k(L1), we also have that the cost App(L1) + 2h

(12)

For a bin bi, let l(bi) be the sum of sizes of items packed in it.

Nput: A List L0 := {A1 . . . Am}

Output: an approximation for Optc,η,k(L0).

Steps:

Find the ih-th element yi in L0 for i = 1, . . , m.

Yh

m. Let (x1, . . , xq) :=Pack-Large-Items(1, 1, 1, L1) (see Lemma 14).

Et App(L1) := Pq

i=1 wTixi. Convert App(L1) to App(L0) according to equation (12). Let B = b1, . . , bu be the list of bins used for packing (each bi has l(bi) available).

Output App(L0), and list B of bins.

End Of Algorithm

We note that the list of bins b1, . . , bu with their used space l(bi) for each bin can be computed in O(n) time from the conversion based on (x1, . , xq) for q types T1, . , Tq. Lemma 16 (). Let β be a constant in (0, 1). Then there exists an O(n) time algorithm that gives an approximation app for packing S with Opt(S) ≤app ≤(1 + β)Opt(S) + 1 for all large n.

Proof:

The bin packing problem is the same as the regular bin packing problem that all bins are Assume that the input list is S for bin packing problem. Let S<δ be the items of size less than δ, and S≥δ be the items of size at least δ. Let δ be a constant with δ ≤β 4 .

Algorithm Linear-Time-Packing(N, S)

Input: A list of items S = a1 . . an and its number of items n. Output: an approximation for Opt(S).

Steps:

1. Let App(S≥δ) and the bin list b1, . . , bu be the output from calling Packing(S≥δ) (see Lemma 15).

F L(Bi) ≤1 −Δ

4. Fill items from S<δ into bi until less than δ space left in bi or all items in S<δ are packed. 5.

F There Are Some Items Of Size Less Than Δ Left

6. Then pack them into some bins so that at most one bin having more than δ space used. 7.

Output the total number of bins used.

End Of Algorithm

Assume that an optimal solution of a bin packing problem has two types of bins. Each of the first type contains at least one item of size at least δ, and each of the second type only contain items of size less than δ. Let V1 be the set of first type bins, and V2 be the set of all second type |U| ≤(1 + β)|V1|.

Fill all items into those bins in U so that each bin has less than δ left. Put all of the items less than δ into some extra bins, and at most one of them has more than δ space left. Case 1.

If U can contain all items, we have that |U| ≤(1 + β)|V1| ≤(1 + β)|V1 ∪V2| = (1 + β)Opt(S). Case 2. There is a bin beyond those in U is used. Let U ′ be all bins without more than δ space

Left. We Have That |U ′| ≤|V1∪V2|

(1−δ) ≤(1 + β)|V1 ∪V2| = (1 + β)Opt(S). Therefore, the approximate solution is at most (1 + β)|V1 ∪V2| + 1 = (1 + β)Opt(S) + 1. 6.

Randomized Offline Algorithm

In this section, we present sublinear time approximation schemes in the offline model. 6.1.

Selecting Items From A List

In this section, we show how a randomized algorithm to select some crucial items from a list. Those elements are used for converting the packing large items into linear programming as described in Section 5.

In order to let linear programming have a small number of cases, the ih-th elements are selected for i = 1, 2, . . ., m, where the large items are grouped into m groups with h items each.

The

approximate ih-th elements (for i = 1, . . , m) have similar performance as the exact ih-th elements in the linear programming method. The approximate ih-th elements (for i = 1, . , m) can be obtained the ih-th element among the random samples from large items in the input list. The detail of the algorithm is given at Select-Crucial-Items(.).

For a finite set A, let |A| be the number of elements in A. For a list L of items a1, . . , an, let |L| = n. Definition 17. Assume that L = a1, . , an is the list of real numbers, and x is an integer.

• Define Rank(x, L) in a1, . . , an to be the interval [a, b] such that |{i : ai < x}| = a −1 and |{i : ai ≤x}| = b. Define minRank(x, L) to be a and maxRank(x, L) to be b. • Define Rankδ(x, L) in a1, . , an to be the interval [a, b] such that |{i : ai < x and ai ≥δ}| = a −1 and |{i : ai ≤x and ai ≥δ}| = b. Define minRankδ(x, L) to be a and maxRankδ(x, L) to be b.

• L[s, t] = as, as+1, . . , at for 0 < s ≤t ≤n. Definition 18. Assume that S is a list of items for a bin packing problem and δ is a real number. Define S<δ to be the sublist of the items of size less than δ in S, and S≥δ to be the sublist of the items of size at least δ in S.

(16)

Let the sorted input list is partitioned into K1K2 . . KmR such that |K1| = |K2| = . = |Km| = h, and 0 ≤|R| < h.

Algorithm Select-Crucial-Items(M, Α, Μ, X)

Input: two constants α and µ in (0, 1), an integer parameter m at least 2, and a list X = x1, x2, . . , is a finite list of random elements in A.

Such That 2Me−Γ2U

< α and 3 ≤γu. 3. If v < u or |X| < u, then output ∅and stop the algorithm.

I

m for i = 1, . . , m. 5. Let yi (i = 1, . , m) be the least element xj such that |{t : xt is in X[1, u] and xt ≤xj}| ≥ ⌈piu⌉.

End Of Algorithm

Lemma 19 shows the performance of the algorithm Algorithm Select-Crucial-Items(.). It is a step to convert the step for packing large items into a dynamic programming method. When the input list of items is S, the list A in Lemma 19 is the sublist S≥δ of all items of S with size at least δ, which will be specified in the full algorithm. The random items X is generated from the subset of all random items of sizes at least δ in a set of random items in S.

Lemma 19. Let µ and α be positive constants in (0, 1). Assume that A is an input list of n numbers

Μ

. Then the algorithm Select-Crucial-Items(.) runs in O( m2(log m)2)

)

time such that given a list X of at least c1m2 log m

Random Elements From A, It Generates Elements

y1 ≤. . ≤ym from the input list such that Pr[Rank(yi, A) ∩[ih −µh, ih + µh]] = ∅for at least one i ∈{1, . , m}] ≤α, where c1 = 16c0, and c0 is the constant defined in Select-Crucial-Items(.), and m is an integer at most n.

Proof:

The algorithm probabilistic performance is analyzed with Chernoffbounds. Note that the number of items n in A is not an input of this algorithm. We only use it in the analysis, but not in the algorithm. Without loss of generality, we assume |X| = u, where u is defined in statement 2 in the Algorithm Select-Crucial-Items(.).

We Assume The

number of random items in X is at least u. By the equation (16) and the fact m ≤n, we have

(18)

By statement 1 in Select-Crucial-Items(.) and inequality (17), we have n

N

(by inequality (23)). By Corollary 6, with probability at most

E−Γ2U

3 , we have |{j : xj ∈X[1, u] and xj ≤yi}| to be at least

(27)

Note that the transition from inequality (25) to inequality (26) is due to equation (16)), which

N

(by inequality (27). Note that pi is defined at line 4 in Algorithm Select-Crucial-Items(.). By Lemma 6, with probability at most P1,i = e−γ2u

(37)

Note that i ≤m. The transition from inequality (32) to inequality (33) is due to the condition

Μ . The Transition From

inequality (33) to inequality (34) is because of inequality (19). The transition from inequality (35) to inequality (36) is due to the setting in statement 2 in Select-Crucial-Items(.).

< Α, Rank(Yi, A) ∩[Ih −

µh, ih + µh] = ∅for at least one i ∈{1, . . , m}. 6.2.

Packing Large Items And Small Items

In this section, we show how to pack large items from sampling items in the input list. Then we Lemma 20. Assume that c, η, and k are positive constants, and ǫ and δ are constants in (0, 1) and θ is a constant in [0, 1). Assume that the input list is S for a bin packing problem with (c, η, k)-related bins. The constants δ, µ, ǫ1, and m are given according to equations (8) to (10). Assume that n′

K

, and S′ be a list of items of size less than δ. Assume that we have the

I = 1, 2, . . ., M

• An approximate solution for bin packing with items in B = {y′h′

Related Bins With Cost At Most (1 + Ǫ)Optc,Η,K(B)

Then there Packing-Conversion(.) is an O(1) time algorithm that gives an approximation app with Optc,η,k(S≥δ ∪S′) ≤app ≤(1 + 5ǫ)Optc,η,k(S≥δ ∪S′).

≤. . . ≤A′

n≥δ is the increasing order of all input elements of size at

≤A′

n≥δ into A1y1A2y2 . . AmymR such that each Ai has exactly h −1 elements and R has less

N′

≥δ into A1y1A2y2 . . Am′ym′R′ such that each Ai has exactly h −1 elements and R′ has less than h elements. We have

(66)

The transition from inequality (61) to inequality (66) is due to the fact θn≥δ

≥1 By Inequali-

ties (38) and (40). By inequalities (61) to (66), we have (1 + 3θ)h ≥h′ ≥(1 −2θ)h.

(67)

Inequality (67) also holds if θ = 0.

M ∪S′. We Show That There Is A Small

difference between the results of two bin packing problems for L0 and L1. Claim 20.1. For every solution of cost x with (c, η, k)-related bins for list L0, there is a solution of cost at most x + (10θ + 4µ)mh + 4h for list L1.

Proof:

Assume that L0 has a bin packing solution. It can be converted into a solution for L1 via an adaption to that of L0 with a small number of additional bins. We use the lots for the elements in Ai+1yi+1 in L0 to store the elements of y′

And The Assumption Rankδ(Y′

i, S≥δ) ∩[ih −µh, ih + µh]̸ = ∅for i = 1, 2, . . ., m, there are at most

I

with i ≤m′. Therefore, we only have that the number

(3Θ + 2Μ)(1 + 2Θ)Mh + (2Θm + 2)(1 + 3Θ)H

(by inequality (67) and (48)). The number of bins for packing those left items is at most (3θ +2µ)(1+2θ)mh+(2θm+2)(1+3θ)h. Since 1 is the maximal cost of one bin, the cost for packing the left items at most

≤

(10θ + 4µ)mh + 4h. Claim 20.2. For every solution of cost y with (c, η, k)-related bins for list L1, there is a solution of cost at most y + (µ + 2θ)mh + 2h for list L0.

Proof:

Assume that L1 has a bin packing solution. It can be converted into a solution for L0 with a small number of additional bins.

I

to store the elements in Aiyi. We have at most (µ + 2θ)h elements left for each Aiyi. Totally, we have at most m(µ + 2θ)h + 2h items left. The bins for packing those left items is at most m(µ + 2θ)h + 2h, which cost at most m(µ + 2θ)h + 2h since 1 is the maximal cost of one bin.

(69)

be an approximation for packing L0 by Claim 20.2. We have that

≤

((1 + ǫ)(Optc,η,k(L0) + (10θ + 4µm)mh + 4h) + m(µ + 2θ)h + 2h

≤

(1 + ǫ)(Optc,η,k(L0) + Optc,η,k(L0)(5µmh + 12θmh + 6h

(82)

The list L∗has at most θn≥δ more items than L0. Therefore

≤

Optc,η,k(L0)(1 + ǫ) (by inequality (39)).

(92)

Therefore, we have App(L∗) ≥Optc,η,k(L∗) by inequality (12) and inequality (91). On the other hand, we have App(L∗) = (1+ǫ)App(L0) ≤(1+ǫ)(1+3ǫ)Optc,η,k(L0) ≤(1+ǫ)(1+3ǫ)Optc,η,k(L∗) ≤ (1 + 5ǫ)Optc,η,k(L∗).

Nput: An Integer N′

≥δ is an approximation to |S≥δ| with (1 −θ)|S≥δ| ≤n′

≥Δ ≤(1 + Θ)|S≥Δ|,

and an approximate solution App(L1) for the bin packing with items in L1 = {y′h′

M } ∪S′ In

(c, η, k)-related bins with cost at most (1 + ǫ)Optc,η,k(L1), where L1 = {y′h′

Of Items Such That Rank(Y′

i, S≥δ) ∩[ih −µh, ih + µh]̸ = ∅for i = 1, 2, . . , m, and S′ is a list of items of size less than δ. Output: an approximation for Optc,η,k(L∗), where L∗is defined by equation (41).

Authors:

Peder EZ Larson 1, 2,* , Jenna ML Bernard1, James A Bankson 3, Nikolaj Bøgh 4, Robert A Bok1, Albert P. Chen 5, Charles H Cunningham 6,7, Jeremy Gordon1, Jan-Bernd Hövener 8, Christoffer Laustsen 4, Dirk Mayer 9,10, Mary A McLean11 12, Franz Schilling13, James Slater1, Jean-Luc Vanderheyden5, 14, Cornelius von Morze 15, Daniel B Vigneron1, 2, Duan Xu1, 2, and the HP 13C

94143, Usa.

Denmark. 5 GE Healthcare, Menlo Park, California, USA. 6 Physical Sciences, Sunnybrook Research Institute, Toronto, Ontario, Canada.

8 Section Biomedical Imaging, Molecular Imaging North Competence Center (MOIN CC), Medicine, Baltimore, MD, USA. Cambridge, United Kingdom.

14Jlvmi Consulting Llc, Dousman, Wi, Usa

#See Acknowledgements for a list of all HP 13C MRI Consensus Group Members This work was supported by the ISMRM Hyperpolarized Media MR Study Group, the ISMRM Hyperpolarization Methods & Equipment Study Group, and the Hyperpolarized MRI Technology Resource Center (NIH/NIBIB grant P41EB013598).

Abstract

MRI with hyperpolarized (HP) 13C agents, also known as HP 13C MRI, can measure processes such as localized metabolism that is altered in numerous cancers, liver, heart, kidney diseases, and more. It has been translated into human studies during the past 10 years, with recent rapid growth in studies largely based on increasing availability of hyperpolarized agent preparation methods suitable for use in humans. This paper aims to capture the current successful practices for HP MRI human studies with [1-13C]pyruvate - by far the most commonly used agent, which sits at a key metabolic junction in glycolysis. The paper is divided into four major topic areas: (1) HP 13C-pyruvate preparation, (2) MRI system setup and calibrations, (3) data acquisition and image reconstruction, and (4) data analysis and quantification. In each area, we identified the key components for a successful study, summarized both published studies and current practices, and discuss evidence gaps, strengths, and limitations. This paper is the output of the “HP 13C MRI Consensus Group” as well as the ISMRM Hyperpolarized Media MR and Hyperpolarized Methods & Equipment study groups. It further aims to provide a comprehensive reference for future consensus building as the field continues to advance human studies with this metabolic imaging modality.

Keywords: Hyperpolarized MRI, metabolic imaging, carbon-13, pyruvate, dissolution dynamic

Introduction

MRI with hyperpolarized 13C agents, also known as hyperpolarized (HP) 13C MRI, has shown great potential as a novel imaging modality, particularly for its ability to probe metabolic processes in real time. The first human studies with HP [1-13C]pyruvate were performed in 2011 in prostate cancer patients (1).

Since then, there have been over 60 papers published with imaging results of human subjects from 13 different sites, with applications including prostate cancer, brain tumors, breast cancer, kidney cancer, pancreatic cancer, metastatic disease, liver disease, ischemic heart disease, diabetes and cardiomyopathies. The vast majority of these studies used [1-13C]pyruvate (1–63), where [2-13C]pyruvate (64) and 13C-urea (56) have been demonstrated too.

As clinical HP 13C MRI advances, there is a growing need to build consensus for best practices, which are critical for comparing data across sites, performing multi-site trials,deploying methods to new sites, partnering with vendors, and potentially for obtaining broader regulatory approvals.

In March 2022, we initiated an effort to build consensus within the HP 13C MRI community with this opportunity in mind, and it was greeted with strong enthusiasm. The “HP 13C MRI Consensus Group”, containing over 55 members from 27 sites, identified the area of greatest need and opportunity for consensus building to be HP [1-13C]pyruvate human

●

Pyruvate is the most mature and widely used HP agent and has the most significant translational evidence emphasizing the potential clinical impact.

●

Clinical trials, particularly multi-site trials, have the strongest need for consensus methods to ensure that data can be combined across sites. This work is a Position Paper for which the goal is to describe current successful practices and study methods for HP [1-13C]pyruvate human studies along with justification to support those practices. This is divided into four major topic areas: (1) HP 13C-pyruvate preparation, (2) MRI system setup and calibrations, (3) data acquisition and image reconstruction, and (4) data analysis and quantification (Fig. 1). The current successful practices and study methods include a literature review of published peer-reviewed journal papers showing human HP [1-13C]pyruvate study data, up to September 2022 (1–63), as well as new unpublished information from surveys of HP 13C study sites. Based on this information, we also highlight the evidence gaps, strengths, and limitations of current practices which are summarized at the end of each section.

Figure 1: Illustration of the HP 13C MRI human study process, including the 4 major areas covered in this paper: Hyperpolarized 13C-pyruvate preparation, MRI system setup and calibration, Acquisition and Reconstruction, and Data Analysis and Quantification.

Figure 2: Anatomical targets of HP [1-13C]pyruvate MRI human studies published up to September 2022.

Hyperpolarized 13C-Pyruvate Preparation

This section covers the processes for creating the HP agent, 13C pyruvate, and will include many aspects and considerations that are needed to safely and effectively prepare doses for metabolic imaging studies in human subjects. These include material, personnel, equipment and facility, fluid path preparation, quality control, and release.

It is helpful to understand that the specifications of a dose of 13C pyruvate suitable for in vivo MR HP metabolic imaging were shaped in part by early preclinical studies performed by GE HealthCare summarized in Ref. (65). In short, the safety of the two novel drug components, 13C pyruvate and the electron paramagnetic agent (EPA) AH111501, were demonstrated in those studies. The more precise formulation of the dose suitable for human use was then determined from clinical studies (66) that included two Phase 1 clinical trials in young and elderly healthy volunteers without hyperpolarization of the 13C nuclei and another Phase 1/2a dose escalation and imaging feasibility study with HP 13C pyruvate in 31 prostate cancer patients at the With the exception of the first HP 13C imaging clinical trial, which utilized a prototype device in a cleanroom (1), all HP 13C studies performed in humans to date have utilized the SPINlab polarizer (manufactured by GE HealthCare). Consequently all doses of the HP 13C pyruvate delivered by SPINlab have been produced using the “SPINlab Pharmacy Kit” that serves as the container-closure system for the various drug components (13C pyruvic acid and EPA mixture, dissolution medium, and neutralization and dilution medium) during sample polarization, dissolution and quality control (QC) processes. Thus many aspects of the HP sample preparation considerations discussed below are related to the SPINlab instrument and the consumables designed to be used with it (67).

General Considerations

While more than 860 patients or healthy subjects having been injected with HP 13C pyruvate as of January 2022 without reports of any serious adverse events (68), HP 13C pyruvate injection remains an investigational MR contrast agent and can only be administered by those with Investigational New Drug (IND) exemption from the Food and Drug Administration (FDA) in the USA, a Clinical Trial Application (CTA) in Canada, approval from National Research Ethics Committee Services in the UK, or approval from the relevant local regulatory body. Thus, methods and processes involved to produce a dose should have patient safety as the first priority. Since utilizing dissolution dynamic nuclear polarization (dissolution-DNP) for human use is still a relatively new development, there are no existing published regulatory guidelines specifically for this method.

There are two major production styles that determine how various sites approach the agent preparation. In the US, the most common approach is to rely on a sterilizing filter (“Terminal Sterilization”) to ensure sterility of the final product, akin to PET tracer production, where a starting molecule with a radioisotope is processed using various other ingredients to make the final, desired and injectable contrast agent within a necessarily short amount of time (69). For these sites, sterilization of the components and accessories upstream of this filter are not required, although many of them were manufactured and tested following Good Manufacturing Practice (GMP) or Good Laboratory Practice (GLP) requirements. The filling process is usually performed under an ISO 5 laminar flow hood, but a clean room or an isolator is not required.

This approach is typically accompanied by testing the integrity of the sterilizing filter prior to release of the dose for injection. Typically, post release endotoxin and sterility tests are performed using an aliquot reserved from each released dose.

In the UK and EU, the most common approach is to more-closely follow sterile pharmaceutical compounding guidelines (70), where all components and ingredients are required to be sterile or manufactured under GMP guidelines and are assembled and filled within a clean room environment or an isolator system (“Sterile Preparation”). Typically a batch of Pharmacy Kits for HP 13C pyruvate injection are prepared together. The sterility of the final dose is also ensured by batch validation testing, in addition to the sterility of the ingredients and the sterile compounding process. The endotoxin and sterility testing are performed for the process validation but are not performed for each injected dose.

Some institutions fill and assemble the Pharmacy Kit required for a specific study on the same day or the day prior to polarization, dissolution, and patient administration, but others have also demonstrated the feasibility of preparing a batch of kits, keeping them in a -20ºC freezer and using them over a period of a few months.

Beyond the obvious requirements that the process and the facility has to ultimately produce a dose that is safe to inject into a human, regulatory authorities will also focus on the question “Are you in control of your processes?”. To be in control of your process requires an in-depth and broad understanding of all processes involved in pre, post, and during the production process.

Personnel

It is typical and may be required to have licensed personnel involved in the production process depending on local regulations.Typically a pharmacist, radiopharmacist or other similarly qualified person (QP), in charge of the facility where the Pharmacy Kit filling and preparation is taking place, is responsible for the overall process and the release of the injectable dose.

Qualified cleanroom technicians are often involved in the Pharmacy Kit filling under the supervision of the pharmacist or QP. As is required for pharmaceutical compounding or PET tracer production, training requirements and training records for all personnel need to be maintained and available for audit by the FDA or equivalent.

Equipment And Facility

The facility and all equipment need to have standard operating procedures (SOPs) that describe how equipment is used, maintained, and calibrated to comply with relevant legislation. Currently, almost all the filling of the Pharmacy Kit takes place within a compounding laminar flow hood or isolator (typically ISO 5). At some sites, the filling is conducted within a cleanroom, while at others, it is conducted in a dedicated non-cleanroom space, reflecting differences in cleanroom approach and specifications between regulators worldwide (71). Some equipment or facilities, such as the compounding hood or cleanroom, may require external certified laboratories for testing.

Material Handling

Material handling guidelines (69,70) require SOPs detailing a system to track all of the materials involved in the HP production process for a particular patient dose, similar to current good manufacturing practice (cGMP) requirements for material handling for drug compounding. This includes acceptance standards, storage conditions, amount used in the patient dose for each ingredient and materials used in the assembly of the fluid path and Pharmacy Kit. Currently some users choose to open and inspect and sometimes modify the Pharmacy Kits upon arrival, but some users keep them in the sealed packaging until they are required for dose preparation.

Pharmacy Kit Filling And Assembling

As required by an IND or its equivalent, the preparation of the doses of HP 13C agent are detailed in the Chemistry, Manufacturing, and Control (CMC) section of an applicable regulatory submission; an example of this has been made available (72). It describes the processes of filling the Pharmacy Kit with the different components that make up the final drug product, and of assembling the final kit for either storage or immediate use in the polarizer. Special attention should be given to the laser welding process in order to satisfy installation qualification (IQ) and operational qualification (OQ). Typically, the final developed process is validated by process qualification (PQ) runs, during which 3 or more Pharmacy Kits are filled and used and the final HP 13C products are tested for endotoxin and sterility and to confirm that they meet the dose specifications for injections (usually including pyruvate concentration, residual EPA concentration, pH, liquid state polarization level and dose temperature). The data from 3 consecutive PQ runs are submitted as part of the IND submission (or its equivalent), and are often also reviewed by the Institutional Review Board (IRB) where the studies are conducted.

Quality Control And Dose Release

The quality control (QC) and dose release can be separated into two aspects: one is the QC and release of the filled Pharmacy Kit, and second is the QC and release of the HP 13C agent for injection, after polarization and dissolution. For institutions filling a batch of kits and storing them to use over a period of time, typically the batch can be released based on initial validation, environmental monitoring data from the day of kit production, and if filters are used during preparation of any of the components, filter integrity testing. But in some cases one or more kits are used for validation before the batch of kits are released for future use. For institutions that fill only the kits required for specific studies shortly before the experiment, the filled kits often do not go through separate release tests before they are used.

The quality control of the HP 13C pyruvate solution post dissolution is primarily performed to ensure that the agent meets the dose specifications (Table 1) before it is administered to the subject. These specifications target both safety (pH, residual EPA, temperature) and efficacy (pyruvate concentration, polarization, volume). Typically, the pyruvate concentration, residual EPA concentration, pH, dose temperature, dose volume, and liquid state polarization are measured by the QC accessory associated with the SPINlab polarizer. Some users perform a secondary measurement for one of the parameters, such as pH, using a different instrument or pH paper. For sites that do not go through a separate release testing process for batch filled kits, the integrity of the sterilization assurance filter, a part of the Pharmacy Kit, is typically tested as a part of the dose release. It is also common for these users to preserve an aliquot of the final HP 13C pyruvate solution for post-release endotoxin and sterility testing. This testing cannot be completed fast enough to test an individual dose prior to injection, but this is why other processes such as PQ runs and validation testing are done to minimize the chance a subject could be injected with a contaminated dose.

The Final Dose Release And Injection

should be done under the supervision of a licensed professional, based on local regulations.

Some Key Challenges

Many of the challenges associated with HP 13C pyruvate preparation can be attributed to the conditions required for the dissolution-DNP method of high magnetic field (~3-7 T) and very low temperature (~1 K) during polarization, with pressurized and superheated water necessary for the rapid dissolution event. These extreme conditions are quite challenging for the design of the container-closure and fluid path system. In particular, the cryogenic temperature in the polarizer requires special attention to any moisture or ambient (moist) air introduced into that portion of the fluid path, which can form an ice block at ~1 K. This ice can lead to flow restriction during the dissolution event and reduce the strength of the laser welded bond between the cryovial and its cap. This can ultimately produce failures in the dissolution step, including variations in final pyruvate concentration and pH that may fail to meet QC release criteria as well as fluid path ruptures that provide no available dose and result in polarizer down-time.

The polarization of the HP 13C pyruvate sample decays quickly over the span of a few minutes after dissolution, and thus the process of dissolution, QC for release, and injection should be completed as fast as possible to preserve the high polarization level achieved. Any delays in the preparation process, such as transportation time or equipment malfunction, can significantly reduce the final polarization and result in lower quality imaging data.

Current Practices

A summary of data collected from all sites performing clinical trials with HP 13C-pyruvate is shown in Fig. 3 and Table 1, including the specification of the final dose and how the quality control and release of the final dose are performed. There is a split in the Production Style, described in the General Considerations section above, with 8/13 sites using Sterile Preparation versus 5/13 using Terminal Sterilization. While many of the dose specifications show notable differences in acceptable ranges, all of these variations listed in tables have been successfully and safely been used to perform HP 13C pyruvate studies in humans. Their differences depend on the institutions’ preferences, resources and their particular regulatory situation. There is high similarity in pyruvate ranges, temperature ranges, EPA limits, and volume limits. There is modest variability in pH ranges and large variability in the endotoxin test limit. There is a 3-fold difference in acceptable polarization levels, which are measured to ensure a futile dose is not injected since the polarization is directly proportional to SNR. This reflects the decision by several sites to believe that useful data can be still be obtained with suboptimal polarizations.

Figure 3: Hyperpolarized agent preparation methods reported by sites currently performing HP

In House

Table 1: HP 13C-pyruvate preparation parameters, methods, and dose specifications used for quality control testing and release as well as validation. These were obtained from a survey of all sites performing clinical trials with HP [1-13C]pyruvate. The parameters used for product release are noted in bold text, otherwise these parameters are measured for batch validation or other QC measurements. The endotoxin and sterility testing are performed during process validation of the batch and/or post-injection, and largely depends on the agent production approach.

Summary

The overall safety record of HP 13C-pyruvate has been very strong, and the SPINlab hyperpolarizer has proven to provide high polarizations at human sized doses while meeting numerous QC and release criteria. A weakness remains the failure modes of the SPINlab Phamacy Kits (e.g. ice blocks, path ruptures), which are placed under extreme requirements particularly during dissolution. The preparation process still requires a high degree of expertise.

Therefore, there is a significant need to improve the reliability, robustness, and ease of operation for generating HP 13C-pyruvate doses for human studies. Furthermore, there is a divide between manufacturing and sterile compounding style preparation as well as other site-specific practices, resulting in variations in SOPs and justification required to relevant regulatory bodies. There have also been no comparisons between these approaches. It is also unclear what release criteria and QC parameters are truly required to ensure patient safety.

However, all of the reported methods are acceptable and approved by the appropriate regulatory authorities, and have led to the rapid expansion of successful human studies in recent years.

Mri System Setup And Calibrations

This section covers the MRI system setup, including the imaging system, RF coils, phantoms, and prescan calibration methods.

Imaging System

The main prerequisite for a given MRI scanner to be capable of supporting studies with HP 13C is its “broadband” capability to transmit and receive radiofrequency (RF) signal at the frequency of 13C, which is around 4 times lower than 1H. This does not come as a default on clinical MR devices. The transmit power of the broadband amplifier should also be sufficient to support the intended flip angle and RF pulse shape with the employed transmission RF coil(s) for 13C. Most studies to date use relatively low flip angles (< 90 degrees) for HP 13C in order to preserve polarization for time-resolved imaging. The capability to receive 13C signal on multiple channels is also desirable to increase SNR, as discussed further in the “RF coils” section.

The choice of magnetic field strength is primarily dependent on the metabolites’ frequency separation due to chemical shift dispersion and 1H imaging. High field strengths do not enhance hyperpolarized 13C signal as they do for 1H because the signal strength in a HP experiment relies on manipulating the population of quantum energy states outside of the MRI scanner.

However, the injected HP 13C-pyruvate and its metabolic products have greater frequency separation at higher fields, and it may thus be easier to separate and quantify these resonances at higher fields. This comes at the cost of a reduction in the achievable T2* and often reduced T1. As the initial polarization is independent of the imaging field strength it has been proposed that the increased T2* at 1.5T can potentially be exploited to increase SNR by adapting the acquisition bandwidth or reduce off-resonance imaging effects in cases when the decay of the transverse magnetization is dominated by T2* (73). In practice, 3T has been used in all published human 13C-pyruvate studies surveyed (Supporting Table S1), and comprises the majority of scanners currently in use for human studies (Table 3). A field strength of 3T is well-suited for 1H MRI anatomical reference and correlative imaging.

Stronger and more rapidly slewing magnetic field gradients support more rapid spatial encoding, particularly for metabolite-specific single-shot imaging using echo-planar imaging (EPI) or spiral imaging (See “Acquisition and Reconstruction”). Although the spatial resolution acquired for HP 13C imaging is typically much coarser than for 1H MRI, the factor of ~4 in gyromagnetic ratio leads to the same reduction factor in performance of the gradient system, so 13C experiments are potentially more limited by gradient hardware performance. To date, all human studies have used the commercially-available integrated gradient systems provided in clinical MRI scanners.

Optimization of scanner design has understandably focused on minimization of artifacts in 1H MRI, where devices such as room lights, the gradient amplifiers, and the motors driving the patient bed are checked to ensure that they do not produce RF interference at the 1H frequency, but artifacts may arise at other frequencies. Eddy current compensation is also not always appropriately adjusted for nuclei at other frequencies (74). In order to optimize for 13C, many sites have performed checks on phantoms for RF interference, gradient artifacts, and eddy currents (74), including the use of post-hoc gradient impulse response function characterisation and correction, and some vendors have fixed these issues as well.

Rf Coils

For HP 13C imaging studies in humans, RF coils for both 1H and 13C nuclei are needed, with 1H MRI providing an anatomical reference for registration and optional additional multiparametric MRI readouts. At the Larmor frequency of 13C nuclei, the relative contributions from coil noise compared to sample noise increase compared to 1H (73,75), although sample noise still is likely the dominant contributor for human-sized coils at 32.1MHz - the resonance frequency of 13C nuclei at 3T.

The key requirement for human 13C-pyruvate RF coils are that the coil geometry and sensitive volume must cover the volume of interest in the subject. Table 2 and Figure 4 shows coil configurations that have been used and optimized for applications in different anatomic regions.

Volume resonators are most commonly used for transmit, as they surround the subject to

Provide B1 Transmit Across The Fov (B1

+). While 1H relies on a large birdcage (“body”) coil built into the scanner, 13C transmit coils must be placed inside the bore. This takes up valuable space within the magnet, and also has led to the use of designs with relatively inhomogeneous

B1

+. Many human studies have used Helmholz pair resonators for transmit, including the “clamshell coil”, which has a notably inhomogeneous B1

+ Profile But Has Been Used Because Of

relatively easy integration into the scanner bore. B1

+ Variation Results In Variations In The Flip

angles that control the use of the hyperpolarized magnetization and creates errors in common HP metrics (9,76). The exception are head coils, where birdcage designs with highly

Homogeneous B1

+ can be placed around the head while easily fitting inside the bore. As with 1H MRI, higher SNR can typically be achieved by smaller receive coil elements, such as surface coils or phased arrays, and the majority of 13C receive coils used have layouts similar to 1H phased arrays.

RF coil quality control is important to ensure proper functioning of the coils to provide consistent imaging quality, especially with limited natural abundance 13C signal in vivo. It typically involves 1) a physical integrity check of the coil cables and connectors and 2) phantom SNR tests to check the coil’s performance and to monitor it over time (see Phantoms below). An useful reference for RF coil quality control is outlined in the MRI accreditation program of the American College of Radiology (77) and can be adapted for 13C coils.

Notably, configurations for brain and prostate studies used dual-tuned 1H/13C coil designs, which greatly simplify workflow and registration of 1H and 13C images, as no switching of coils is needed.

(1)

Table 2: RF coil configurations reported for human HP [1-13C]pyruvate studies.

Tx = Transmit

coil, RX = receive coil. The commonly used “clamshell” TX coil is a Helmholz pair design. For 1H RF configurations, all used the Body coil for TX unless otherwise noted, and “repositioned” indicates the 13C coil was removed for 1H imaging. One representative reference is listed for each configuration. The RF coil configurations reported in the reviewed papers are shown in Supporting Table S1.

Figure 4: Examples of RF coil configurations used for human HP [1-13C]pyruvate brain studies. (A,B) 13C Clamshell TX (Helmholz pair) and 2× 4-channel paddle RX arrays. (C) 13C Birdcage volume TX and 32-channel RX array (RX array slides into TX coil). (D) 13C Birdcage volume TX and 24-channel RX array, combined with a 1H 8-channel RX array. Image reproduced with permission from Ref (16).

Phantoms

Since hyperpolarized magnetization is non-renewable, phantoms containing 13C nuclei are important to: 1) test the multi-nuclear capabilities of the imaging system, including all parts of the signal excitation and receive chain; 2) perform calibration measurements before a scan with hyperpolarized nuclei; and 3) perform necessary pre-scan adjustments (see “Prescan Calibration” section). The phantoms currently in use are listed in Table 3. Their composition must provide sufficient 13C signal, with additional considerations of conductivity, stability, chemical shift(s) present, potential for dynamic imaging, and cost. The phantom geometries are typically either compact, in order to be used alongside the subject during a HP scan, or large enough to mimic the inner volume of a RF coil for system testing.

One popular compact design contains enriched 13C-urea at high concentration, typically 8 M, which provides a single resonance, placed inside a small container ~1 mL. The most common recipe mixes 13C-urea in a 90% water/10% glycerol solution, with glycerol used to increase the urea solubility and doping with a Gd-based contrast agent to shorten T1 which increases the potential SNR per unit time. For example, when Dotarem is added at a 3:1000 volume ratio the 13C-urea T1 is around 500 ms and T2 is around 100 ms. However, when testing pulse sequences influenced by T1 and T2, doping should be used carefully. This phantom is suitable for frequency calibration, transmit gain calibration, sequence testing, and as a fiducial marker when placed next to a patient. However, enriched 13C-urea has a relatively high cost compared to natural abundance compounds.

For larger volumes (>100 ml), the phantoms most often used contain undiluted ethylene glycol, glycerol, or dimethyl silicone. These compounds have sufficiently high carbon concentrations to provide sufficient 13C signal even with the 1.1% natural abundance of 13C. These larger phantoms matching the inner volume of an RF coil are useful for coil testing, including transmit

+) And Receive (B1

-) coil profile mapping, as well as to mimic acquisitions using in vivo FOV requirements. In this case, size and conductivity should match the expected subject size in order to mimic coil loading and get a realistic estimation of B1+. Large-volume natural abundance urea phantoms have also been used by some sites, but suffer from higher conductivity compared to biological tissues. Typically, it is easier to increase the conductivity and hence coil loading of the non-conductive phantom by adding NaCl to match physiological loading (16,78).

Dynamic phantoms that aim to mimic metabolite kinetics have also been developed (79–81), and have the potential to more closely mimic the HP experiment, but so far these are not widely used.

Prescan Calibration

Prior to performing an MRI acquisition, the so-called prescan procedure is used to set the shim parameters to maximize B0 homogeneity over the field of view (FOV) or a specific region of interest (ROI), the scanner center frequency (CF), the RF transmit gain, and the receiver gain.

While this calibration procedure is usually automated for 1H, the lack of sufficient natural abundance 13C signal prevents use of automated methods. (Although natural abundance 13C lipid signal has been detected, there are so far no reports on using this signal for prescan.) Table 3 shows current practices across sites.

Maximizing B0 homogeneity is independent of the nucleus and is therefore performed prior to 13C imaging using the 1H water signal and existing shimming tools, such as by a standard automated process (“Auto Shimming”) or using high order shimming routines. Similarly, the 13C CF can be calculated from the 1H CF using a predetermined scaling factor that depends on the target chemical shift (82). Another common approach used is to have a small, high-concentration 13C phantom, e.g. 8M 13C-urea, integrated in the RF coil or placed next to the scan subject (1). The reference frequency can also be based on real-time measurements after the HP injection but prior to imaging (83). Both the CF and B0 shimming are critical when using spectrally-selective RF pulses, as inmetabolite-specific imaging methods, where the desired excitation bandwidths are typically very narrow and frequency offsets can lead to a failure mode that is only apparent after injection.

The calibration of the RF transmit power is typically performed on a small, high-concentration 13C phantom placed near the region of interest during the scan or on a large 13C phantom of similar size and coil loading as the subject, prior to the subject scan. Reference power is often done by sweeping the power in a pulse-acquire sequence (53,62), or the Bloch-Siegert method (52,84). When using a small phantom, the location of the phantom, B1

+ Inhomogeneity As Well

as any shielding effects, e.g., when the phantom is integrated into a coil (1), may degrade the accuracy. Other methods include real-time Bloch-Siegert method measurements after the HP injection (83), and using the stronger natural abundance 23Na signal that is close enough to the 13C resonance frequency to be detected by 13C coils (82).

The receiver gain is predetermined, either systematically based on independent phantom measurements and assuming the dose and polarization of the HP compound is known prior to injection, or based on past HP imaging studies.

Power [Kw]

Phantom(s) - during study Phantom(s) - before study 13C Frequency

8

13C-bicarbonate doped with dimethyl silicone, various

Power [Kw]

Phantom(s) - during study Phantom(s) - before study 13C Frequency

Maximum Values

Table 3: Summary of the imaging systems, phantoms, and prescan procedures used at sites currently performing HP 13C-pyruvate human studies. These were obtained from a survey of all sites performing clinical trials with HP [1-13C]pyruvate. *Previously performed studies with a Siemens 3T Tim Trio. The imaging systems, phantoms, and prescan procedures reported in the reviewed papers are shown in Supporting Table S1.

Summary

Commercially available 3T MRI systems are by far the most commonly used for human HP 13C-pyruvate studies, although a systematic investigation of the impact of B0 has only recently been investigated (73). The multi-nuclear RF transmit and receive chain has proven sufficient for current acquisition strategies, although many sites have observed artifacts due to RF interference, gradient interference, and residual eddy currents when operating at the 13C frequency. A variety of 13C RF coils, tailored for numerous anatomical targets, have been successfully demonstrated, with the main limitation that most transmit coils take up a lot of additional space inside the bore and provide relatively inhomogeneous B1

+ Profiles. The

phantoms used have converged into generally 2 categories - small phantoms containing 13C-enriched compounds that can be used during the study and human-sized phantoms containing compounds with high carbon concentrations but without 13C enrichment that are used to test and calibrate the coils. There are no standardized compositions or geometry, and dynamic phantoms that recapitulate in vivo kinetics would be desirable but are still an emerging area. Prescan calibration procedures were not well defined in most publications, so we surveyed individual sites to determine current practices. Calibration procedures for the B0 field (13C CF and shimming) for most sites take advantage of 1H signal and methods, while methods

For Calibration Of B1

+ is more variable across sites, likely a reflection of remaining challenges in how to perform this calibration. Standardization of both phantoms and calibration procedures would synergistically improve the robustness and reproducibility of HP 13C studies.

Acquisition And Reconstruction

Data acquisition strategies in human HP [1-13C]pyruvate MRI studies must account for multiple chemical shifts, efficiently utilize the non-renewable HP magnetization, and acquire data quickly relative to metabolism and relaxation decay processes. These studies require spectral encoding to separate metabolites, necessitating pulse sequences that efficiently encode up to 5D data (3 spatial + 1 spectral + 1 temporal dimension). RF pulses must efficiently sample without immediately saturating the non-renewable HP magnetization, and sequences must acquire data quickly and be robust to both experimental and physiologic variation (e.g. B1

+ Inhomogeneity,

variation in perfusion) to ensure reproducibility and minimize scan-to-scan variability. This section covers current successful practices for data acquisition in human [1-13C]pyruvate studies, and accompanying 1H imaging, from different anatomic regions, including scan parameters and image reconstruction.

Acquisition And Reconstruction Methods

The acquisition methods used in human [1-13C]pyruvate studies can be classified into 3 categories: 1) MR spectroscopy or MR spectroscopic imaging (“MRS/I”), 2) chemical shift encoding methods, and 3) metabolite-specific imaging (Fig. 5).

Mrs/I Methods Specifically

resolve a spectrum that can be analyzed to extract expected as well as unexpected resonances, making this approach very robust. It was used in many initial studies (1).

Chemical Shift

encoding methods, most commonly the Iterative Decomposition of water and fat with Echo Asymmetry and Least-squares estimation (IDEAL) method, use imaging sequences acquired with multiple TEs and rely on a model-based separation of expected chemical shifts (85).

Metabolite-specific imaging methods use specialized RF pulses that are spatially and spectrally selective to excite individual metabolites which are then typically imaged with fast k-space trajectories such as echo planar imaging (EPI) or spirals (86).

Their Application To Different

organ systems is described below. The image reconstruction methods used in human [1-13C]pyruvate studies have typically been conventional methods (e.g. FFT, non-uniform FFT, or equivalent). The incorporation of accelerated imaging and advanced reconstruction methods including parallel imaging (4,57,87) and compressed sensing (7) has also been applied in human studies for improved spatial resolution, temporal resolution and coverage, but have the potential for additional artifacts as well as SNR losses due to ill-conditioning of the reconstruction (e.g. g-factor).

The Majority Of

published studies do not use accelerated imaging indicating the resolution and coverage achievable without acceleration is currently adequate for successful data collection. Performing coil combination, even with fully sampled data has also been shown to have specific challenges for HP human images: using naive sum-of-squares methods suffer from high noise amplification in the relatively low SNR regime of HP [1-13C]pyruvate (compared to 1H), motivating several HP 13C-specific methods that include data-driven coil sensitivity estimation which have shown obvious improvements over sum-of-squares (11).

More recently denoising techniques have been applied as post-processing of human HP data(41,42,44). The techniques applied are based on spatial-temporal singular value decomposition for unsupervised estimation of signal and noise components. They have shown improvements in apparent SNR in the brain and liver, while care must be taken to choose parameters such as the rank threshold to avoid oversmoothing and overfitting to the estimated signal components.

Prostate Studies

Prostate cancer was the first human application of HP [1-13C]pyruvate (1), and data was acquired with MRS/I methods: 1D dynamic MRS, single-slice 2D dynamic echo-planar spectroscopic imaging (EPSI), and single time point 3D EPSI. Advances in imaging strategies led to the development and application of new acquisition schemes, including undersampled 3D EPSI with compressed-sensing (7), model-based chemical shift encoding methods that use a priori information (47,59), and metabolite-specific EPI (10), all of which can provide volumetric whole-organ coverage and dynamic acquisitions.

The pyruvate bolus arrival in the prostate can vary by ± 10 s between patients, necessitating dynamic imaging to reliably and consistently capture the pyruvate bolus (18). For this reason, all currently ongoing studies acquire dynamic data. While MRS/I, chemical shift encoding, and metabolite-specific imaging can all achieve dynamic imaging, chemical shift encoding and metabolite-specific imaging provide greater dynamic and volumetric coverage (85). For scan prescriptions, the FOV is designed to provide full prostate coverage and typically to match the orientation of the anatomic imaging used for registration. Flip angles used in current studies are constant through time, as quantification with a variable-through-time flip scheme is highly sensitive to bolus timing (8) and errors in the RF transmit (B1 +) field (76).

Heart Studies

Data acquisition methods for 13C imaging in the heart must be designed to meet the demands of significant cardiac motion and blood flow. To cope with the periodic cardiac motion, most human heart studies to date used gating to the diastolic window, the longest cardiac cycle interval, which has reduced motion (2,22,28,30,35,36,38,45,52). The duration of the diastolic window limits the available data sampling time, making cardiac acquisitions the most time-constrained of the HP 13C MRI applications. The most common acquisition approach is metabolite-specific imaging with spiral k-space trajectories (2). Their single-shot imaging capability makes these methods particularly robust to motion effects. Furthermore, spiral k-space trajectories provide rapid k-space coverage and relatively benign flow and motion artifacts. The majority of studies have used 2D multi-slice acquisitions, but 3D encoding has also been used successfully (35).

Brain Studies

For HP 13C MRI of the human brain, the majority of studies have also used 2D (slice selective) acquisitions (10–12,14,16,28,33,40,41,44,51,53,60), with a trend toward volumetric coverage using 2D multi-slice metabolite-specific imaging. 3D metabolite-specific imaging of the whole brain, with phase encoding of the slice direction (34,57), has been shown to provide similar SNR efficiency (88) compared with multislice imaging. A number of studies have employed MRS/I (5,6,29,31–33,50,55) resulting in a spectrum from each voxel, which has the advantage of not requiring a priori information about which peaks to encode. This was important in early brain studies when it was not known which peaks would be detectable. Chemical shift encoding, using a set of images with different echo times and an iterative reconstruction of the individual resonances (i.e. the IDEAL approach (85)), has also been used (12,49,54), with the drawback that coverage in the slice direction was limited due to the time required to acquire multiple echo time images.

Abdomen And Breast Studies

The fundamental approaches to data acquisition and reconstruction in the abdomen and breast are largely similar to the aforementioned applications, but demand attention to particular challenges associated with these anatomic regions, especially relating to respiratory motion.

Although it has been shown that a basic 2D MRSI approach based on phase encoding and FID readout can be successfully applied for HP 13C imaging in breast (15) and kidney (13), major advantages in terms of spatiotemporal resolution and coverage have been realized using tailored approaches based on metabolite-specific imaging (43,62) and chemical shift encoding (43), which have facilitated multi-slice or 3D dynamic acquisitions over large FOVs in the abdomen (4,37,46).

The significant respiratory motion encountered in these regions can directly blur 13C images, and has further favored these rapid acquisition strategies. Motion also degrades B0 homogeneity, which can shift frequency-selective excitation profiles and introduce artifacts into rapid imaging readouts. This makes accurate determination of the acquisition center frequency and shimming essential in these regions which often cover large FOVs. (See “Prescan Calibration” section for more information). In some studies, breath-holding was used to minimize motion effects and enforce frame-to-frame data consistency (42). A pragmatic and reasonably effective approach for dealing with respiratory motion during 13C data acquisition is an initial breath-hold (as long as can be tolerated), followed by free-breathing (46,62).

1H Imaging

Collection of 1H imaging data is essential both for prescribing the 13C acquisition and for interpretation of the resulting 13C data. Multi-planar 1H scouts are acquired prior to 13C acquisition to enable graphical prescription of the 13C imaging region. All human HP 13C-pyruvate imaging studies acquire conventional MRI scans (e.g. T1- and T2-weighted volumes) for anatomic reference, aiming to cover at least the full 13C FOV. Acquiring these anatomic scans as close as possible to the time of 13C imaging (immediately before or after) minimizes potential misregistration between the data sets. Depending on the application, other advanced 1H sequences are also acquired (e.g. diffusion-weighted imaging for cancer imaging).

When contrast-enhanced data is acquired, it is done after 13C imaging, as paramagnetic contrast agents will accelerate 13C relaxation.

Reported Study Parameters

Figures 5 and 6, and Supporting Table S2 shows the reported acquisition study parameters for human HP [1-13C]pyruvate studies published as of September 2022. Figure 5 shows a mixture of MRS/I, metabolite-specific imaging, and chemical shift encoding methods have been successfully used, where spectroscopy-based methods have become less prevalent in recent studies. Figure 6 shows the acquisition timing, including the important start time and interval/temporal resolution, is quite variable across studies.

Figure 5: Acquisition methods used in published HP [1-13C]pyruvate human studies published up to September 2022, classified into: MR spectroscopy and spectroscopy imaging (MRS/I); chemical shift encoding methods, such as IDEAL, that use multiple TEs and model-based reconstructions; and metabolite-specific imaging methods that use spectrally-selective excitation to image a single resonance at a time.

Figure 6: Temporal acquisition characteristics reported in HP [1-13C]pyruvate human studies published up to September 2022. (a) Reported referencing of acquisition start times.

(B)

Acquisition start times reported when using dynamic imaging and when timing was reported relative to the end of the injection. (c) Temporal resolutions. “Not Applicable” indicates dynamic imaging was not used.

Summary

Three general categories of acquisition strategies have been used successfully for human HP 13C-pyruvate studies: MRS/I, model-based chemical shift encoding (e.g. IDEAL) methods, and metabolite-specific imaging methods. These have enabled successful studies in the prostate, heart, brain, abdomen, and breast. Recent studies increasingly have used the imaging-based strategies of metabolite-specific imaging and chemical shift encoding which are the fastest methods, although a heads-to–head comparison between techniques has not been performed.

Metabolite-specific imaging is quite popular because of its speed and compatibility with single-shot imaging, but is sensitive to B0 field variations and thus requires careful calibrations. Nearly all studies surveyed acquired data dynamically, allowing measurement of the bolus and metabolite kinetics. The exact timings and associated flip angles vary quite widely across reported studies, with no consensus yet as to how to choose these parameters. Image reconstruction is typically done directly using Fourier Transform methods, and accelerated imaging strategies are uncommon.

Data Analysis And Quantification

This section covers the analysis of data from human HP [1-13C]pyruvate studies, including modeling and metrics, visualization, as well as considerations for how to store data and metadata. Depending on study design, the analysis may need to give quantitative or semi-quantitative output reflecting a biological process or may just reflect a contrast between different regions of interest for quantitative evaluation.

Metrics

Figure 7: HP [1-13C]pyruvate raw data (A) have typically been quantified using four categories of metrics depending on the acquisition. Data acquired as a single time point are often quantified using normalized metabolite images or metabolite ratios (B). Dynamic data can be quantified using normalized metabolite images or metabolite ratios (B), or with metabolite timings such as time-to-peak (TTP) or pharmacokinetic (PK) models (C). The latter two require the data to be time-resolved. [1-13C]alanine and 13C-bicarbonate are analyzed similarly to [1-13C]lactate but omitted here for display.

Metabolite images are commonly used as summary metrics for HP MRI data, often including some form of normalization as well as summed over time as an area under the time curve (AUC) (17). These are analogous to the visual evaluation that is most used for routine clinical work (89,90). In these metabolite images, we expect that the [1-13C]pyruvate AUC signal is predominantly weighted towards perfusion and uptake, while [1-13C]lactate, [1-13C]alanine and 13C-bicarbonate AUCs represent metabolic conversion. The strength of this approach lies in its simplicity and relatively few underlying assumptions. Limitations to the use of single-metabolite images or AUCs include sensitivity to inhomogeneous coil profiles (57,87,91), the acquisition strategy and acquisition parameters, pyruvate polarization and concentration level, and signal relaxation rates (92). Further, the reader must be careful to interpret all the images in conjunction to better understand the underlying biology; for example, increased [1-13C]lactate in the presence of decreased [1-13C]pyruvate delivery can have a very different meaning compared to increased [1-13C]lactate with increased [1-13C]pyruvate delivery.

In an attempt to address variations in coil sensitivity, polarization level, and pyruvate delivery, AUC images are often computed by normalizing to a specified parameter, such as the maximum pyruvate or average lactate signals, or presented as a ratio such as lactate/pyruvate or divided by “total Carbon” - the sum total of HP 13C signal observed across all metabolites. The AUC ratios between metabolites and pyruvate are proportional to the corresponding forward kinetic rates (81,93), but are not directly comparable to rate constants when magnetization loss rates (e.g. relaxation and losses due to signal excitation) differ between studies. Similarly, the ratios between the produced metabolites (e.g. bicarbonate/lactate) can reflect the balance between downstream metabolic pathways (12,55). Care must be taken to consider how AUC images are calculated and normalized before comparing values between studies.

To further quantify the interpretation, pharmacokinetic (PK) modeling approaches were developed to compute the apparent kinetics of pyruvate-to-metabolite exchange (92,94–99). These yield semi-quantitative to quantitative apparent rate constants, given in s-1. Some models require a vascular input function, while others avoid this requirement (95). PK models can explicitly account for acquisition-specific details such as excitation angle and repetition time, and thus may reduce the effects of these details on quantification. An input-less model, provided in the Hyperpolarized-MRI-Toolbox (https://github.com/LarsonLab/hyperpolarized-mri-toolbox) (100) and thus frequently employed for human data, has been shown to fit well and robustly to prostate and brain data (8,20). PK models are quantitative in nature, arguably provide more relevant biological information (8,20), and appear to be reproducible across sites (51). However, rate constants derived from PK models are still apparent rates, and likely do not reflect a single biological characteristic.

Some additional considerations include whether complex or magnitude data is used, as the noise behaviors will impact the analysis differently. Additionally, cut-off thresholds or other criteria may be used to identify and avoid voxels with insufficient SNR before analysis to improve robustness (20,41).

Regardless of the analysis approach, the underlying biology is not always clearly represented by the data; instead, the metrics may be influenced by perfusion, barrier permeability, intercellular shuttles, enzyme activities, co-substrate concentrations, or combinations thereof, depending on the organ and disease of interest (19,43,94,101–103). This may be addressed by incorporating complementary information. As an example, HP 13C pyruvate data is influenced by perfusion, and thus addition of perfusion MRI could be important for interpretation (98,104,105).

All the methods outlined above have been explored in clinical studies, described in Supporting Table 3 and summarized in Figure 8. As of September 2022, approximately 52% of studies involving human subjects report rate constants derived from a PK model with a few different models reported. A nearly equal fraction (51%) of the studies report AUC ratio values.

Approximately 66% of these studies report metabolite-specific images or AUC values. About 40% report SNR values; this metric is particularly frequent in manuscripts that describe technical developments for clinical HP MRI. Approximately 16% of these studies summarize model-free metrics, and 10% report measurements from a single timepoint. Most studies report a combination of quantities.

Figure 8: Reported metrics used for analysis in HP [1-13C]pyruvate human studies published up to September 2022.

Visualization

A wide variety of approaches have been used for visualizing data from human HP 13C-MRI studies. The challenges and practical considerations are: 1) choosing the appropriate metrics to display, 2) how to encode the parameters (e.g. the colormap), and 3) choosing how to provide anatomical context and other multi-parametric data. The choice of visualization also depends on the goal which could be for diagnostic interpretation, but also quality control, reproducibility among readers and publication.

Metrics

The choice of HP 13C metrics is described in detail above. At this stage in HP 13C development where there is no standardized metric, often a combination of metabolite images and ratios or PK model parameters are shown.

Parameter Encoding

The mapping function chosen should provide an adequate, often quantitative, impression of the parameter mapped. There is a consensus in the visualization field that perceptually uniform maps are best suited to visualize continuous parameters, like the greyscale typically used by radiologists as well as other monochrome (black to blue) and color ranges (fire-type, rainbow-type) (106,107). Multi-color heatmaps have been the most frequently employed method for HP 13C data, while greyscale has infrequently been used but it ensures there is no coloring-based bias as well as facilitating later reuse (Fig. 9a). Among the color schemes employed in the clinical HP 13C literature, fire-type scheme seems to be the most common [similar to “Plasma” or “Inferno” in matplotlib.org]. Next most commonly employed is the rainbow-type scheme [similar to “Rainbow” in matplotlib.org].

Anatomical Context

HP MRI faces the challenge that it does not necessarily depict the anatomical features, similar to PET, and thus requires an anatomical reference. Most often, a grayscale anatomical image is overlaid with a HP colormap (Fig. 9c,d). This approach is very intuitive, but can skew perception as the grey-scale anatomical reference may affect the brightness of the HP data (e.g. signal in the skull). This bias does not occur when showing adjacent maps (Fig. 9a, b). Here, anatomical outlines may help to provide reference (Fig. 9b).

Related Journal Articles & DOI Links

Selected peer-reviewed publications relevant to 12 Lead ECG Acquisition. Click the DOI to access the full paper (may require institutional access).

Why Choose Us?

Bangalore guidance for robotics, Spectre and autonomous systems projects.