text:
# Project Euler Problem 530: sum of sum of greatest common divisors

Here is a description of Project Euler problem 530:

Every divisor $d$ of a number $n$ has a complementary divisor $n/d$.

Let $f(n)$ be the sum of the greatest common divisor of $d$ and $n/d$ over all positive divisors $d$ of $n$, that is $\displaystyle f(n)=\sum_{d/n}\gcd\left(d, \frac{n}{d}\right)$.

Let $F$ be the summatory function of $f$, that is $\displaystyle F(k) = \sum_{n=1}^{k}f(n)$.

You are given that $F(10)=32$ and $F(1000)=12776$.

Find $F(10^{15})$.

My solution for Euler Problem 530 is as follows:

import java.math.BigInteger;

public class problem530 {

public static void main(String[] args) {

double start = System.nanoTime();

BigInteger result = BigInteger.ZERO;
BigInteger one = BigInteger.ONE;

for (long i = 1; i <= 1000; i++){
if ( i == 1) {
}
if (PrimeTest.testLong(i) == true) {
}
else if (i != 1 && PrimeTest.testLong(i) == false) {
for(long j = 1; j*2 <= i; j++) {
if (i%j == 0) {
long sub = i / j;
}
}
}
}

System.out.println(result);

double duration = (System.nanoTime() - start)/1000000000;

System.out.println("Your code took " + duration + " seconds to execute.");

}
}

I have PrimeTest and GCD written in libraries. The code works (it returns the correct answer for the test cases). It takes unimaginably long to get the answer for $F(10^{15})$ though (essentially, I won't get the answer). I'm looking for ways to optimise it.

At this link, @alan wrote something there about a sieve (presumably in C++?) which I don't quite understand. Does anyone have any ideas for optimisation?

• I perform GCD operations using the Eulerian algorithm.
• Prime Testing is performed for:

n = 1; n*n <= (number being tested); n++

To give an idea of how long this code takes to execute:

• It ran F(10)=32 in 0.008 seconds.
• It ran F(1000)=12766 in 0.019 seconds.
• It ran F(100,000)=2907546 in 29.724 seconds.

This was the optimisation suggested in another post on codereview.

It seems to me that the alternative summation suggested there is wrong! F(10) would give you 22, not 32. I'm not sure how the alternative summation was derived.

• If you do double duration = (System.nanoTime()- start)/1000000000;, and removing the end statement it will be more accurate. Dec 24, 2015 at 2:42
• @piepi You're absolutely right. Thanks for that! Any ideas on the rest of it?
– Thev
Dec 24, 2015 at 2:42
• @TheveshTheva Figuring out! Dec 24, 2015 at 2:45
• @TheveshTheva So, as you have further mentioned about the Sieve, I asked [that question](codereview.stackexchange.com/questions/114627/extending-sieve-of-eratosthenes-beyond-a-billion-follow-up) a few days ago. I still haven't found a way to extend it beyond 10^9. I will be waiting to know how it can be used to test primes. Dec 24, 2015 at 2:55
• Welcome to Code Review! I have rolled back the last edit. Please see what you may and may not do after receiving answers. Dec 24, 2015 at 3:43

Special Cases and Branching

if (prime(i) == true) {
// ...
}
else if (prime(i) == false) {
// ...
}

This ends up with you checking composite numbers for primality twice! Once in each branch! The second part could have just been else. Additionally, explicitly checking for == true is an anti-pattern. Prefer:

if (prime(i)) {
// ...
} else {
// ...
}

That said, why is being prime a special case? Your non-prime logic would've worked just fine on primes too! And for 1! So just drop all the branches completely and simply iterate.

Need a better algorithm

10^15 is simply too big to brute force the answer. Even dropping all the unnecessary extra work you're doing is likely insufficient. You'll have to try to come up with some optimal substructure this problem has so that you can use dynamic programming.

• Thanks for that! I removed the code which checks for primality twice. The reason why being prime is a special case is that prime numbers only have themselves and 1 as divisors, and the GCD to add in both those cases is 1. I tried running the code with all branches dropped and it ran slower. :/ With primality testing was 4 seconds faster for case F(100,000).
– Thev
Dec 24, 2015 at 3:31

I don't usually use java, but as to the algorithm, to make the suggestion of the real optimization work, you need to consider 2 things.

First, if you want to calculate F(10), this algorithm will go from d=1 to 3 in the first loop. Then from 1 to n*d <= 10. However, with this solution you are doing the gcd of (2,5) but never doing the one for (5,2).

To solve this, you could just add the gcd result*2. However, in special cases like (1,1),(2,2),(3,3) you only want to add it once because they are square numbers. So you need to add gcd*1 if d == n, and gcd*2 if d != n

This gets us to the second consideration. Problem with this is that we will do gcd*2 for (1,2) but then we will do gcd*2 with (2,1) so we will add some cases 4 times instead of 2 as we wanted.

The fix for this is pretty easy, instead of going from n=1 to nd <=k, go from n=d to nd <= k. Why? Because if n < d, we have already passed over those pairs before ((2,1) pair was already seen when d=1 and n=2)

To make all this more clear, here is a short python implementation: (I used d as x and n as y)

def solve(n):
solution = 0
for x in xrange(1,int(math.sqrt(n))+1): # from 1 to sqrt(n)
y = x # to avoid repetitions, from x to x*y <= n
while x*y<=n :
solution+= gcd(x,y)*(2 if x != y else 1) # this adds gcd*1 if x ==y and gcd*2 if x != y
y+=1
print solution

This runs pretty fast as we are not even doing prime checks (which would be faster with a sieve, but not necessary with this solution). Python is pretty slow so it would take a lot to solve 10^15, but you could try to code it in java and check the speed improvement

In python for n = 500000, it takes a bit less than 2 seconds. I did try the same in java, but it seems to take 2.8 seconds for n = 500000, even slower than python. Might be because I had never used BigInteger before, so there might be some improvements to make, here is the code:

    double start = System.nanoTime();

BigInteger n = new BigInteger("500000");

BigInteger x = BigInteger.ONE;

BigInteger solution = BigInteger.ZERO;

while(x.multiply(x).compareTo(n) != 1){

BigInteger y = x;

while(y.multiply(x).compareTo(n) != 1){

BigInteger gc = gcd(x,y);

if(x.compareTo(y) == 0){
}else{

}

}

}

double duration = (System.nanoTime() - start)/1000000000;

System.out.println(solution);
System.out.println("Your code took " + duration + " seconds to execute.");

For further optimizations, you could memorize some gcd calls as we are clearly repeating a lot of them

• You're absolutely right! I adapted your ideas as follows: (see edit in my post). It definitely compiles faster than the previous version! However, still can't go up to F(10^15) unfortunately.
– Thev
Dec 25, 2015 at 3:06
• @TheveshTheva yeah, even with a O(n) solution it would take over 200 hours to solve, so there must be a way to solve it in O(sqrt(n)), not sure how Dec 25, 2015 at 19:16


text:
The trip for the C++ Now 2018 conference in Aspen, Colorado has ended! I gave 2 lightning talks and my talk about sol2, and I think it went pretty well!

Aspen, Colorado is an absolutely gorgeous area. When I first got there, it felt like I was taking a vacation! Of course, a vacation might have had me getting a little more sleep than I ended up catching that week, but every night staying up until 12 or 1 AM in the morning talking about C++, techniques, experiences and ideas was entirely well worth it. It is rare I get to geek out in person… and I got to do a whole week of it in beautiful Aspen!

Volunteering for a conference was a lot of fun! You had to attend a talk at every single track, help move food and clean up, and manage a few conference tasks like registration and guide people at the beginning of the conference. All in all much of it was done ahead of time and I was just gluing together some of the pieces other people had prepared to make things easier. We also got to test run the new website-based, schedule-based digital timers for C++Now 2018, which in my opinion were an immense success!

## Listening: initializer_lists and Unicode and more!

My favorite talk was Jason Turner (@lefticus)’s “Initializer Lists are Broken, Let’s Fix Them”, albeit I hesitate to term it your usual lecture-style talk! It was more of a guided, interactive performance exploration of initializer_list, what it means, and ways to improve the design. Jason has some pretty fantastic slide tech, too, making Compiler Explorer pop up at a single click on his slides! It was really engaging and demonstrated some practical implications for API designers who were looking for both speed and API design tradeoffs. I am more or less intensely interested in exactly this design space, so the talk was immensely practical for me!

Another great two-part talk was Zach Laine’s about Boost.Text, which was both a great overview and a wonderful deep-dive into designing a practical API that can handle Unicode. Seeing the design choices he made and tackled in getting a full collation-handling, grapheme-identifying, normalization-using text processing library was very interesting, plus all the interesting things about human languages that come with trying to make it all work out properly in code. The world is an amazingly complex place, and Text is just one area where you see all the complexities and not-so-clean but entirely rational ways in which human beings communicate with one another. I hope get some of his work in hand and start benchmarking it against other solutions in the same space.

Bob Steagall’s talk in the same space also went through these subjects, but from the perspective of performing blazing fast utf8 decoding! You can read some of his experience and about his talk at Bob’s Trip Report.

## Speaking: sol2, Lightning, and More!

On Thursday, I gave my talk about sol2. The slides are here, which in and of themselves I think turned out very nicely. It’s a bit unfortunate that usertypes were relegated to a demo but there’s more than enough documentation and examples in sol2 for someone to steep themselves into it if they really liked it.

I think my talk was received well. Someone in the audience actually used sol2 as well, which really made it hit home that I was developing a library that was supposed to be usable for other people. It really had reinvigorated me to have that level of responsibility and ownership over some code, and that my care of it affects the performance and ability for many, many applications.

Plus, it’s really awesome when someone as amazing as Odin Holmes tells me that I did a good job and that he likes my talk!

I did not get a chance to publish my updated benchmarks at my talk, so as a follow-up I’ll be placing my updated benchmarking numbers in sol2’s documentation and in a new blog post soon!

I gave 2 additional lightning talks while I was there too. One was about std::embed, a way to lift a resource into a compile-time view. I gave it as a bit of a cheesy limerick, and then made comments about it afterwards! Most people seem to really like the idea, but we will see how it goes in the C++ Standards Committee.

The other was a less technical and more personal talk about the idea of where I belong.

## “We Are Glad You Are Here”

There are a lot of criteria people have for feeling like they belong. It usually boils down to feeling like there’s a community that you can tap into and share with and be a productive member of. It also comes from not feeling like you are being pushed out for reasons which are either beyond your control or have nothing to do with the core of your character. I never really felt like I had a community I could tap into, for various reasons. I talked a little bit about that, and the response was overwhelming.

From a nerd who grew up in a Hippie Commune to the son of an immigrating Polish family who spoke very little English, the story seemed to resonate with many people. I was a bit sad that so many people felt alone, but extremely encouraged that my experience was not just a “People of Color” feeling or a singular thing. There is a shared experience when you are smart and bright in a way that is not expected of you. And the overwhelming end goal is simple: it is going to be okay, so long as you do not give up that thing that helps shape who you are for the sake of fitting an expectation other people have of you.

I am elated that C++Now was the place I ended up from pursuing my unique interests, drive and goals. It was my first C++ conference and I felt incredibly welcome. My skin color was not an issue: I was judged as a human being, student, and upon the merits of my work alone.

These are the kinds of places I live for; the preconceived notions and ideas of what I might be capable of because what I look like were left at the door, and I was viewed as the individual I signed up to be. I am first a Student, a Volunteer, a presenter and a software developer who is immensely interested in learning, growing and ultimately sharing what I had learned, accomplished, and experienced. I never had to think that I was being judged first for being dark-skinned above all else, and that was liberating.

I cannot wait to go to another C++ conference and dive into that kind of atmosphere again! But for now, my goal is to go to the next C++ Standards Committee meeting and champion my std::embed paper.

Until next time! ♥

Const West is Const Best!

format: plain


text:
# Finite abelian group of size p-1

#### sid_galt

Suppose we have two finite abelian groups $$G,G^{\prime}$$ of size $$n=pq$$, $$p,q$$ being primes. $$G$$ is cyclic.

Both $$G,G^{\prime}$$ have subgroups $$H,H^{\prime}$$, both of size $$q$$. The factor groups $$G/H,\ G^{\prime}/H^{\prime}$$ are cyclic and since they are of equal size, they are isomorphic. Are $$G,G^{\prime}$$ also isomorphic?

Edit: The title is wrong. p-1 has nothing to do with this problem. Sorry about that.

Last edited:
Related Linear and Abstract Algebra News on Phys.org

#### ThirstyDog

I don't think the groups G and G' are required to be isomorphic. You have already defined G so consider
$$G' = <a,b|a^{p}=b^{q}=e>$$
where e is the identity. This should be a suitable counter example -try working through it.

If I am wrong about it being a counter example then this should prove that G and G' are required to be isomorphic as there are only two non-isomorphic groups of order pq with p and q being prime.

Hope this helps.

EDIT: sorry for that earlier post

Let p > q. Now, if q does not divide p-1 then any group of order p*q must be cyclic. (This is a result which can be proved easily with sylow's theorems)
A simple example are groups of order 15 = 5*3.

If on the other hand, q does divide p-1 then this group must be non-abelian. (The proof for this is a bit involved, but it can be found in some text book like herstein).

Now since, you have already stated that G is cyclic. This implies q does not divide p-1. Then G must be cyclic and so must be G'. Hence they must be isomorphic.

Suppose p = q. In this case, its really difficult to say anything, because G' has two possible structures:
1. a cyclic group of order p^2.
2. a group isomorphic to C_p x C_p. (C_p is the cyclic group of order p)

I'll try to find the references containing the proofs for the results I have stated above and post them later, but I hope this was useful.

Last edited:

#### matt grime

Homework Helper
Thirsty dog, the group you defined for G' is infinite: it is the free product of C_p and C_q.

Do you know an structure theorems for finite abelian groups? Are you supposed to assume that p and q are distinct primes?

#### ThirstyDog

Hey Matt,

I forgot to say Abelian... I am guessing you realised this by your next comment.

I was under the impression that any finite Abelian group is expressible as the Cartesian products of a finite number of cyclic groups whose orders are prime powers.

I think that if p and q are distinct then the cyclic group of order pq is isomorphic to the Cartesian of cyclic groups of order p and q. If p and q are equal then no such isomorphism exist.

This says in terms of the original question G and G' are definitely isomorphic if p is distinct from q. But if p=q then G and G' are not always isomorphic. Ancient_Nomad has pointed this out.

#### PhysicalAnomaly

Intuitively, I would guess that H,H' are isomorphic => G,G' are isomorphic...

#### ThirstyDog

Consider
$$C_{4} = <c|c^{4}=e> \mbox{ and } C_{2}\times C_{2} = <a,b|a^{2}=b^{2}=e,ab=ba>$$
These are clearly not isomorphic as the first has an element of order 4 while the latter does not.

We can choose the subgroups
$$H = <c^{2}> \mbox{ and } H' = <a>$$
Thus H and H' are isomorphic. Also
$$C_{4}/H \cong C_{2} \cong C_{2}\times C_{2}/H'$$

This shows that just because an two Abelian groups can have isomorphic subgroups and their quotients are also isomorphic doesn't imply the original groups are.

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving


text:
# For which $n$ is $\frac{n!}{4}$ equal to $\left\lfloor \sqrt{\frac{n!}{4}}\right\rfloor\left(\left\lfloor\sqrt{\frac{n!}{4}}\right\rfloor + 1\right)$?

For how many values of $$n$$, is $$\frac{n!}{4}$$ equal to $$\left\lfloor \sqrt{\frac{n!}{4}}\right\rfloor\left(\left\lfloor\sqrt{\frac{n!}{4}}\right\rfloor + 1\right)$$?

Further more, is there a way to approximate (or maybe even find the precise answer to) $$\left\lfloor \sqrt{\frac{n!}{4}}\right\rfloor\left(\left\lfloor\sqrt{\frac{n!}{4}}\right\rfloor + 1\right)$$? I tried approximating $$n!$$ but had no luck.

• Google "Brocard's problem". It works for $n= 4,5,$ and $7$, it is conjectured those are the only such values. If you accept the proof of the abc conjecture then it is known that there are only finitely many such values of $n$. – Nate Jun 7 '19 at 21:12
Let $$x=\sqrt{\frac{n!}{4}}$$. $$x^2 = \lfloor x\rfloor \cdot (\lfloor x\rfloor + 1)$$ $$x^2 + \frac14 = (\lfloor x\rfloor + \frac12)^2$$ $$-\frac12 + \sqrt{x^2+ \frac14} = \lfloor x\rfloor$$ $$-1 + \sqrt{n!+ 1} = 2\lfloor x\rfloor \in 2\mathbb N$$ So we get a necessary condition $$\exists m\in\mathbb N : n! + 1 = (2m+1)^2$$ It's easy to see that it is also a sufficient condition, because $$\sqrt{n!} < \sqrt{n! + 1} < \sqrt{n!} + 1$$ $$\sqrt{n!} < 2m+1 < \sqrt{n!} + 1$$ $$m < \sqrt{\frac{n!}{4}} < m + \frac12$$ so $$\lfloor \sqrt{\frac{n!}{4}}\rfloor = m$$. For low $$n$$, $$n=4$$ and $$n=5$$ satisfy this condition, but I have no proof there is no more solutions.


text:
# All Questions

6 views

### Must the coordinates of a polynomial iteration have about the same size?

The following statements seem plausible (not to say intuitively obvious), but I do not know how to prove them. I would like to know whether these or similar problems have been considered anywhere. ...
12 views

### Can infinte dimensional algebras be smooth?

Is it possible for an infinte dimensional algebra to be smooth? That is can an infinte dimensinal algebra have finite global dimension? For example is the polynomial ring $R[x_n]_{n \in \mathbb{N}}$ ...
24 views

### Tensor products [on hold]

I'm currently trying to teach myself about tensors but I'm having some trouble with understanding what's going on. I've managed to come to a basic understanding of the ranks of tensors, rank n ...
45 views

### Are the asymptotics of A003238 known?

Sequence A003238 of the OEIS counts rooted trees with $n$ vertices in which vertices at the same level have the same degree.'' The sequence, $a$, begins 1, 1, 2, 3, 5, 6, 10, 11, 16, ... and it is ...
28 views

### Internal logic of the topos of simplicial sets

I am looking for a closed statement (i.e. not depending on any parameter objects) which is true in the internal logic of the topos of simplicial sets, but is not an intuitionistic tautology. Ideally, ...
22 views

### Characterizations of the GOE/GUE family of distributions

For a random symmetric matrix of size $n\times n$, with entries drawn from a Gaussian Ensemble, the joint probability of eigenvalues can be written as: ...
106 views

### Undergraduate Mathematics Research [migrated]

I am currently an undergraduate junior. I have taken most of the standard undergraduate math courses and a few introductory graduate courses (measure theory, algebraic topology, complex analysis, ...
51 views

### Trapping a convex body by a finite set of points

In $\mathbb{R}^n$, let $K$ be a convex body and $T$ a finite set of points disjoint from the interior of $K$. Say that $T$ traps $K$ if there is no continuous motion of $K$ carrying $K$ arbitrarily ...
68 views

### trick question: how to construct the centre of a given circle? [on hold]

This is a trick question I heard from a high-school teacher today: find the origin of a given circle. You can use any mathematically correct tool and method. Give me the shortest, the most elegant or ...
22 views

18 views

### Smallest distribution of points with genuinely different clusterings

An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...
19 views

### integral involving nth order incomplete gamma function [on hold]

\begin{eqnarray} \int_0^{\infty}\,x^{k+r+\xi-1 }\,e^{-\lambda ^{-k}\,x^k}\, \left( \Gamma\left(1+\frac{\xi }{k},\,x^k \lambda ^{-k}\right)\right)^n\,{\rm d} x\,. \end{eqnarray}
44 views

### The largest size of a boolean subgraph (a hypercube) of a given graph

Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...
89 views

### Chow ring of two varieties

Suppose we are given two smooth projective varieties $X$ and $Y$. Maybe this is elementary but what is the Chow ring $CH(X\times Y)$ in terms of $CH(X)$ and $CH(Y)$?
81 views

### Direct image of an ideal sheaf along a blow-up

Suppose that $I\subseteq\mathbb{C}[x_0,\ldots,x_n]$ is a saturated homogeneous ideal. Let $\mathcal{I}\subseteq\mathcal{O}_{\mathbb{P}^n}$ denote the corresponding coherent ideal sheaf, and then let ...
112 views

### Number of representations of an integer as an (arbitrary) sum of products

If $n$ is a positive integer, let $r(n)$ denote the number of representations of $n$ as a sum of products of pairs of positive integers. (Here, the order of the terms in the sum does not matter, but ...
67 views

### endomorphisms of the Jacobian of a curve

Let $C$ be a smooth, projective curve over the complex numbers and let $J(C)$ be its Jacobian. The Torelli theorem relates the automorphisms of $C$ to the automorphisms of $J(C)$. Precisely, ...
11 views

381 views

### “Paradoxes” in $\mathbb{R}^n$

One may think of this question as a duplicate of this one. I see it more like an extension. The "inscribed sphere paradox" discussed in the aforementioned question states that if you inscribe a ...
118 views

### real algebraic geometry software?

Does anyone have suggestions/experience for any software packages to study real algebraic varieties (for example, counting connected components of hypersurfaces, figuring out the topological type of ...
408 views

### Graph Theory is the slum of Topology (?) [on hold]

(Edited in accordance with suggestions in comments.) I remember once I read a quote that sounded like "graph theory is the slum of topology" (please approximate). I can not find it on the web, and I ...
16 views

### Homotopy with non piece-wise linear boundary

in the middle of a long proof I encounter the following problem. Let $E$ be a closed and convex set in $\mathbb R^n$ such that for all $\vec x\in E$ it holds that $\sum_ix_i=1$. (We can understand ...

15 30 50 per page


text:
# Equation Simplification in Mathematica

I wonder if the following equation could be further simplified by Mathematica. There are $22$ Integrals involved and many of them are in the range $y_l$ and $y_u$. I would guess that at least those terms could be collected in the same integral. I used the command FullSimplify but the result is the same with the input. Are there some more clever ways to simplify such type of equations?

(2*(1 - \[Epsilon]0)^2*Integrate[((Sqrt[f1[y]*l[yu]] - Sqrt[f0[y]*l[yl]
*l[yu]])*(-Sqrt[f1[y]*l[yl]] + Sqrt[f0[y]*l[yl]*l[yu]]))/(-Sqrt[l[yl]] +
Sqrt[l[yu]])^2, {y, yl, yu}] - 2*(Integrate[(Sqrt[f0[y]]*(-Sqrt[f1[y]*l[yl]] +
Sqrt[f0[y]*l[yl]*l[yu]]))/(-Sqrt[l[yl]] + Sqrt[l[yu]]), {y, yl, yu}] +
Integrate[f0[y], {y, -Infinity, yl}]*Sqrt[l[yl]])*(Integrate[(Sqrt[f0[y]]*
(Sqrt[f1[y]*l[yu]] - Sqrt[f0[y]*l[yl]*l[yu]]))/(-Sqrt[l[yl]] + Sqrt[l[yu]]),
{y, yl, yu}] + Integrate[f0[y], {y, yu, Infinity}]*Sqrt[l[yu]]) -
Sqrt[(-2*(1 - \[Epsilon]0)^2*Integrate[((Sqrt[f1[y]*l[yu]] -
Sqrt[f0[y]*l[yl]*l[yu]])*(-Sqrt[f1[y]*l[yl]] +
Sqrt[f0[y]*l[yl]*l[yu]]))/(-Sqrt[l[yl]] + Sqrt[l[yu]])^2, {y, yl, yu}] +
2*(Integrate[(Sqrt[f0[y]]*(-Sqrt[f1[y]*l[yl]] +
Sqrt[f0[y]*l[yl]*l[yu]]))/(-Sqrt[l[yl]] + Sqrt[l[yu]]), {y, yl, yu}] +
Integrate[f0[y], {y, -Infinity, yl}]*Sqrt[l[yl]])*(Integrate[(Sqrt[f0[y]]*
(Sqrt[f1[y]*l[yu]] - Sqrt[f0[y]*l[yl]*l[yu]]))/(-Sqrt[l[yl]] +
Sqrt[l[yu]]), {y, yl, yu}] + Integrate[f0[y], {y, yu, Infinity}]*
Sqrt[l[yu]]))^2 - 4*((Integrate[(Sqrt[f0[y]]*(-Sqrt[f1[y]*l[yl]] +
Sqrt[f0[y]*l[yl]*l[yu]]))/(-Sqrt[l[yl]] + Sqrt[l[yu]]), {y, yl, yu}] +
Integrate[f0[y], {y, -Infinity, yl}]*Sqrt[l[yl]])^2 -
(1 -\[Epsilon]0)^2*(Integrate[(Sqrt[f0[y]]*(-Sqrt[f1[y]*l[yl]] +
Sqrt[f0[y]*l[yl]*l[yu]])^2)/(-Sqrt[l[yl]] + Sqrt[l[yu]])^2, {y, yl, yu}] +
Integrate[f0[y], {y, -Infinity, yl}]*l[yl]))*((Integrate[(Sqrt[f0[y]]*
(Sqrt[f1[y]*l[yu]] - Sqrt[f0[y]*l[yl]*l[yu]]))/(-Sqrt[l[yl]] +
Sqrt[l[yu]]), {y, yl, yu}] + Integrate[f0[y], {y, yu, Infinity}]*
Sqrt[l[yu]])^2 - (1 - \[Epsilon]0)^2*(Integrate[(Sqrt[f1[y]*l[yu]] -
Sqrt[f0[y]*l[yl]*l[yu]])^2/(-Sqrt[l[yl]] + Sqrt[l[yu]])^2, {y, yl, yu}] +
Integrate[f0[y], {y, yu, Infinity}]*l[yu]))])/(2*((Integrate[(Sqrt[f0[y]]*
(Sqrt[f1[y]*l[yu]] - Sqrt[f0[y]*l[yl]*l[yu]]))/(-Sqrt[l[yl]] + Sqrt[l[yu]]),
{y, yl, yu}] + Integrate[f0[y], {y, yu, Infinity}]*Sqrt[l[yu]])^2 -
(1 - \[Epsilon]0)^2*(Integrate[(Sqrt[f1[y]*l[yu]] -
Sqrt[f0[y]*l[yl]*l[yu]])^2/(-Sqrt[l[yl]] + Sqrt[l[yu]])^2, {y, yl, yu}]
+Integrate[f0[y], {y, yu, Infinity}]*l[yu])))
• How about trying two of them first? If that works, then go to three... – bill s Feb 28 '14 at 2:18
• @bills thanks for the comment. There are $22$ but they are not in the form of simple summations. Sometimes multiplications and some times in the phranthesis etc. Please have a look at it via printing the equations. Seemed complicated to deal one by one to me. – Seyhmus Güngören Feb 28 '14 at 2:20
• There is a quite dirty four letters word for this kind of thing. It's called "work" – Dr. belisarius Feb 28 '14 at 3:08
• @belisarius lets dont call it as dirty. It is usually what we usually do.. This formula is also a result of such long series of dirty algebra by hand. Then I had to give it to mathematica, because i had to find the roots of a polynomial of degree $2$. The result is as above. Now which is dirtier? trying to write these equations back to papers and try to reduce by hand or try to find a way in mathematica so that a simplification can be done. I think both) – Seyhmus Güngören Feb 28 '14 at 11:56
• To be or not to be ...:) – Dr. belisarius Feb 28 '14 at 12:16

Let's say your expression is expr. Then you can parse this this way, first let's take a look at a structure of the expr, in order to do this we can create a list of substititutions. Of course we are doing this because we have seen that there are common terms involving integrals:

(subs = With[{set = Cases[expr, _Integrate, ∞] // DeleteDuplicates},
Table[set[[i]] :> Evaluate@int[i], {i, Length@set}]]

) // Grid[{#}\[Transpose], Alignment -> Right, BaseStyle -> {18}] &

expr /. subs

If you take a closer look you can see that there are no terms that could be collected inside common integral.

Even if there would be it can be tough according to Why aren't these additions of integrals and summations equal?

So as you can see FullSimplify is not enough to do this. (in the case where it can be done) Distributing Integrate is quite easy and is shown in the linked answer. If you want to gather terms to the common Integrate you can try with the following pattern:

5 Integrate[f[x], {x, x1, x2}] - 2 Integrate[g[x], {x, x1, x2}] //. (
con1_. Integrate[a_, {x_, l__}] + con2_. Integrate[b_, {x_, l__}]) :>
Integrate[con1 a + con2 b, {x, l}] /; D[con1, x] == 0 && D[con2, x] == 0

• thank you very much for the answer. – Seyhmus Güngören Apr 23 '14 at 21:33
• @SeyhmusGüngören That's great you find it useful :) Good luck! – Kuba Apr 23 '14 at 21:35


text:
# The Closed disc $D$ is a manifold with boundary

It is obvious geometrically, but how one proves with a few words, analytically, the statement above?Additionally, if one has a smaller open disc $D_\epsilon$ of radius $\epsilon$ centered at a point of $D$, how to conclude that $D-D_\epsilon$ is still a manifol with boundary $\partial D \cup\partial D_\epsilon$?

-
Three words: Inverse Cayley transform. –  t.b. May 20 '12 at 18:07
Generally the subspaces of Euclidean space which are "obviously" manifolds with boundary locally have the form $f(x_1, \ldots, x_n) \leq C$ (or perhaps they are finite intersections of such objects). For these spaces there are variations on the implicit function theorem which do all the work for you, similarly to the way the ordinary implicit function theorem tells you when $f(x_1, \ldots, x_n) = C$ is a closed submanifold. If I can find a reference I'll post this as an answer. –  Paul Siegel May 20 '12 at 19:58
@t.b If I am right, inverse cayley transform is a boundary chart when we see the disc as a complex manifold, but if we want to prove just the real case? –  Jr. May 21 '12 at 2:24
@PaulSiegel What do you mean by "a closed manifold"? –  Jr. May 21 '12 at 2:25
If you just write out the formulas for the real and imaginary components of the inverse Cayley transform then you get diffeomorphisms between small open subsets of the disk and small open subsets of the closed upper half plane. The complex structure isn't relevant here. –  Paul Siegel May 26 '12 at 17:53


text:
## CryptoDB

### Julio López

#### Publications

Year
Venue
Title
2019
JOFC
In this work, we retake an old idea that Koblitz presented in his landmark paper (Koblitz, in: Proceedings of CRYPTO 1991. LNCS, vol 576, Springer, Berlin, pp 279–287, 1991 ), where he suggested the possibility of defining anomalous elliptic curves over the base field ${\mathbb {F}}_4$ F 4 . We present a careful implementation of the base and quadratic field arithmetic required for computing the scalar multiplication operation in such curves. We also introduce two ordinary Koblitz-like elliptic curves defined over ${\mathbb {F}}_4$ F 4 that are equipped with efficient endomorphisms. To the best of our knowledge, these endomorphisms have not been reported before. In order to achieve a fast reduction procedure, we adopted a redundant trinomial strategy that embeds elements of the field ${\mathbb {F}}_{4^{m}},$ F 4 m , with m a prime number, into a ring of higher order defined by an almost irreducible trinomial. We also suggest a number of techniques that allow us to take full advantage of the native vector instructions of high-end microprocessors. Our software library achieves the fastest timings reported for the computation of the timing-protected scalar multiplication on Koblitz curves, and competitive timings with respect to the speed records established recently in the computation of the scalar multiplication over binary and prime fields.
2017
CHES
The PRESENT block cipher was one of the first hardware-oriented proposals for implementation in extremely resource-constrained environments. Its design is based on 4-bit S-boxes and a 64-bit permutation, a far from optimal choice to achieve good performance in software. As a result, most software implementations require large lookup tables in order to meet efficiency goals. In this paper, we describe a new portable and efficient software implementation of PRESENT, fully protected against timing attacks. Our implementation uses a novel decomposition of the permutation layer, and bitsliced computation of the S-boxes using optimized Boolean formulas, not requiring lookup tables. The implementations are evaluated in embedded ARM CPUs ranging from microcontrollers to full-featured processors equipped with vector instructions. Timings for our software implementation show a significant performance improvement compared to the numbers from the FELICS benchmarking framework. In particular, encrypting 128 bits using CTR mode takes about 2100 cycles on a Cortex-M3, improving on the best Assembly implementation in FELICS by a factor of 8. Additionally, we present the fastest masked implementation of PRESENT for protection against timing and other side-channel attacks in the scenario we consider, improving on related work by 15%. Hence, we conclude that PRESENT can be remarkably efficient in software if implemented with our techniques, and even compete with a software implementation of AES in terms of latency while offering a much smaller code footprint.
2016
CHES
2013
CHES
2011
EUROCRYPT
2011
CHES
2000
CHES
1999
CHES

CHES 2022
CHES 2021
CHES 2020


text:
Propagation of analyticity of solutions to the Cauchy problem for Kirchhoff type equations
Journées équations aux dérivées partielles (2000), article no. 8, 14 p.

We shall give the local in time existence of the solutions in Gevrey classes to the Cauchy problem for Kirhhoff equations of $p$-laplacian type and investigate the propagation of analyticity of solutions for real analytic deta. When $p=2$, his equation as the global real analytic solution for the real analytic initial data.

@article{JEDP_2000____A8_0,
author = {Kajitani, Kunihiko},
title = {Propagation of analyticity of solutions to the Cauchy problem for Kirchhoff type equations},
journal = {Journ\'ees \'equations aux d\'eriv\'ees partielles},
publisher = {Universit\'e de Nantes},
year = {2000},
zbl = {01808698},
language = {en},
url = {http://www.numdam.org/item/JEDP_2000____A8_0}
}

Kajitani, Kunihiko. Propagation of analyticity of solutions to the Cauchy problem for Kirchhoff type equations. Journées équations aux dérivées partielles (2000), article  no. 8, 14 p. http://www.numdam.org/item/JEDP_2000____A8_0/

[1] Alinhac, S. & Métivier, G. Propagation de L'analyticité des solutions de systèmes hyperboliques non-linéaires. Inv. Math. vol.75 (1984), 189-203. | MR 86f:35010 | Zbl 0545.35063

[2] S. Bernstein, Sur une classe d'équations fonctionnelles aux dérivèes partielles, Izv. Akad. Nauk SSSR, Ser. Mat. v.4, 1940, 17-26. | JFM 66.0471.01 | MR 2,102a | Zbl 0026.01901

[3] K. Kajitani, Local solution of Cauchy problem for nonlinear hyperbolic systems in Gevrey class, Hokkaido Math. J. v.12, 1983, 434-460. | MR 86a:35096

[4] Kajitani K. The Cauchy problem for nonlinear hyperbolic systems, Bull. Sci. Math. v.110, 1986, 3-48. | MR 87k:35156 | Zbl 0657.35082

[5] Kajitani K. & Yamaguti K. Propagation of analyticity of solutions to the Cauchy problem for nonlinear symmetrizable systems, Ann. Scuola Norm. Sup. Pisa vol. 28, 1999, 471-487. | Numdam | MR 2001c:35140 | Zbl 0940.35128

[6] Kajitani K. On the Cauchy problem for Kirchhoff equations of p-Laplacian type, Proceeding of Colloque of P.D.E. in memory of Jean Leray, 1999, Sweden.

[7] Lax, P.D. Nonlinear hyperbilic equations, Comm. Pure Appl. Math. vol. 6 (1953), 231-258. | MR 15,36a | Zbl 0050.31705

[8] Mizohata, S. Analyticity of solutions of hyperbolic systems with analytic coefficients, Comm. Pure Appl. Math. vol. 14 (1961), 547-559. | MR 24 #A2755 | Zbl 0105.07203

[9] S.I. Pohozaev, On a class of quasilinear hyperbolic equations, Math. USSR. Sb. v.96, 1975, 152-166. | MR 51 #6167 | Zbl 0328.35060


text:
# machine learning – How to chose the probability distribution and its parameters in maximum likelihood estimation

I’m reading the book “Mathematics for Machine Learning”, it’s a free book that you can find here. So I’m reading section 8.3 of the book which explains the `maximum likelihood estimation` (or MLE).
This is my understanding of how MLE works in machine learning:

Say we have a dataset of vectors $$(x_1, x_2, …, x_n)$$, we also have corresponding labels $$(y_1, y_2, …, y_n)$$ which are real numbers, finally we have a model with parameters $$theta$$. Now MLE is a way to find the best parameters $$theta$$ for the model, so that model would map $$x_n$$ to $$hat{y}_n$$ and $$hat{y}_n$$ is as close to $$y_n$$ as possible.

For each $$x_n$$ and $$y_n$$ we have a probability distribution $$p(y_n|x_n,theta)$$. Basically it estimates how likely our model with parameters $$theta$$ will output $$y_n$$ when we feed it $$x_n$$ (and the bigger the probability the better).

We then take a logarithm of each of the estimated probabilities and sum up all the logarithms, like this:
$$sum_{n=1}^Nlog{p(y_n|x_n,theta)}$$

The bigger this sum the better our model with parameters $$theta$$ explains the data, so we have to maximize the sum.

What I don’t understand is how do we chose the probability distribution $$p(y_n|x_n,theta)$$ and its parameters? In the book there is an Example 8.4, where they chose the probability distribution to be Gaussian distribution with zero mean, $$epsilon_n sim mathcal{N}(0,,sigma^{2})$$. They then assume that the linear model $$x_n^Ttheta$$ is used for prediction, so:
$$p(y_n|x_n,theta) = mathcal{N}(y_n|x_n^Ttheta,,sigma^{2})$$
and I don’t understand why they replaced zero mean with $$x_n^Ttheta$$, also where do we get covariance $$sigma^{2}$$?

So this is my question, how do we chose the probability distribution and it’s parameters? In the example above the distribution is Gaussian but it could be any other distribution from those that exist and different distributions have different types and numbers of parameters. Also as I understood each $$x_n$$ and $$y_n$$ have its own probability distribution $$p(y_n|x_n,theta)$$ which even more complicates the problem.

I would really appreciate your help. Also note that I’m just learning the math for machine learning and not very skilled. If you need any additional info please ask in the comments.

Thanks!


text:
Friday
December 13, 2013

# Homework Help: CHEM

Posted by aPRIL on Tuesday, June 5, 2012 at 8:58am.

4.69 of S is reaction with oxygen calculate the volume of SO2 in mL formed at 33 degrees C and 1.14 atm

• CHEM - DrBob222, Tuesday, June 5, 2012 at 2:00pm

Write the equation and balance it.
Convert 4.69g S to mols. mols = grams/molar mass.
Convert mols S to mols SO2 by using the coefficients in the balanced equation.
Then use PV = nRT to convert mols to volume(in liters) and convert that to mL.

Related Questions

math word problems - The sum of two numbers is 69. The second is 9 more than 4 ...
math word problems - The sum of two numbers is 69. The second is 9 more than 4 ...
chem - Check the correct statements for the above reaction. Choose at least one...
College Chem - 4. Write the balanced equation for CH4+Cl2„_CH2Cl2+HCl6. For the ...
Dr.Bob222 Chem - I believe that you are correct because you have more experience...
chem - if a car produces 81g of {\rm CO_2}, how many grams of {\rm O_2} are used...
Chem - Use the reaction that occurs when magnesium burns in oxygen to show how a...
math - if matt buy's a cola at $1.69,gets a refill 3 time, for cost of$.45 each...
Chemistry - The following reaction has the following standard thermodynamic ...
Chemistry - The following reaction has the following standard thermodynamic ...

Search
Members


text:
Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+
 Title Keywords Abstract Author All
Search Results: 1 - 10 of 100 matches for " "
 Page 1 /100 Display every page 5 10 20 Item
 Maguaré , 1986, Abstract: Rese a informe de investigación "etnohistoria de las caucherías del Putumayo" de Roberto Pineda Camacho / "Arqueología de rescate- proyecto carbonífero de el cerrejón -zona norte"- area de el palmar" / Arqueología de rescate- proyecto carbonífero de el cerrejon-1984 zona central - áreas de patilla y el paredón" / VASCO LUIS GUILLERMO. Jaibanás. Los Verdaderos Hombres, Biblioteca Banco Popular. Textos Universitarios, Bogotá, 1985.
 Mathematics , 2011, Abstract: Let $G$ be a simple graph with $n$ vertices and let $\mu_1 \geqslant \mu_2 \geqslant...\geqslant \mu_{n - 1} \geqslant \mu_n = 0$ be the eigenvalues of its Laplacian matrix. The Laplacian Estrada index of a graph $G$ is defined as $LEE (G) = \sum\limits_{i = 1}^n e^{\mu_i}$. Using the recent connection between Estrada index of a line graph and Laplacian Estrada index, we prove that the path $P_n$ has minimal, while the star $S_n$ has maximal $LEE$ among trees on $n$ vertices. In addition, we find the unique tree with the second maximal Laplacian Estrada index.
 Güng？r ADilek Journal of Inequalities and Applications , 2010, Abstract: We first define a new Laplacian spectrum based on Estrada index, namely, Laplacian Estrada-like invariant, LEEL, and two new Estrada index-like quantities, denoted by S and , respectively, that are generalized versions of the Estrada index. After that, we obtain some lower and upper bounds for LEEL, S, and .
 Yilun Shang Mathematics , 2014, Abstract: Suppose $G$ is a simple graph on $n$ vertices. The $D$-eigenvalues $\mu_1,\mu_2,\cdots,\mu_n$ of $G$ are the eigenvalues of its distance matrix. The distance Estrada index of $G$ is defined as $DEE(G)=\sum_{i=1}^ne^{\mu_i}$. In this paper, we establish new lower and upper bounds for $DEE(G)$ in terms of the Wiener index $W(G)$. We also compute the distance Estrada index for some concrete graphs including the buckminsterfullerene $C_{60}$.
 Applicable Analysis and Discrete Mathematics , 2009, DOI: 10.2298/aadm0902371z Abstract: Let $G$ be a graph with $n$ vertices and let $mu_1,mu_2,ldots,mu_n$ be its Laplacian eigenvalues. In some recent works aquantity called Laplacian Estrada index was considered, defined as$LEE(G)=sumlimits_{i=1}^n e^{mu_i}$,. We now establish somefurther properties of $LEE$, mainly upper and lower bounds interms of the number of vertices, number of edges, and the firstZagreb index.
 A. Dilek Güngör Journal of Inequalities and Applications , 2010, DOI: 10.1155/2010/904196 Abstract: We first define a new Laplacian spectrum based on Estrada index, namely, Laplacian Estrada-like invariant, LEEL, and two new Estrada index-like quantities, denoted by S and EEX, respectively, that are generalized versions of the Estrada index. After that, we obtain some lower and upper bounds for LEEL, S, and EEX.
 Mathematics , 2012, Abstract: The D-eigenvalues {\mu}_1,{\mu}_2,...,{\mu}_{n} of a connected graph G are the eigenvalues of its distance matrix. The distance Estrada index of G is defined in [15] as DEE=DEE(G)=\Sigma_{i=1}^n e^{{\mu}_{i}} In this paper, we give better lower bounds for the distance Estrada index of any connected graph as well as some relations between DEE(G) and the distance energy.
 Applicable Analysis and Discrete Mathematics , 2009, DOI: 10.2298/aadm0901147l Abstract: Let $G$ be a graph of order $n$. Let $lambda_{1}, lambda_{2},ldots, lambda_{n}$ be the eigenvalues of the adjacency matrix of$G$, and let $mu_{1}, mu_{2}, ldots, mu_{n}$ be the eigenvaluesof the Laplacian matrix of $G$. Much studied Estrada index of thegraph $G$ is defined as $EE=EE(G)=sumlimits^{n}_{i=1}e^{lambda_{i}}$. We define and investigate the Laplacian Estrada index of the graph $G$, $LEE=LEE(G)=sumlimits^{n}_{i=1}e^{(mu_{i}-frac{2m}{n})}$. Bounds for $LEE$ are obtained, as well as some relations between $LEE$ and graph Laplacian energy.
 Journal of the Serbian Chemical Society , 2007, Abstract: The Estrada index EE is a recently proposed molecular structure-descriptor, used in the modeling of certain features of the 3D structure of organic molecules, in particular of the degree of folding of proteins and other long-chain biopolymers. The Estrada index is computed from the spectrum of the molecular graph. Therefore, finding its relation with the spectral radius r (= the greatest graph eigenvalue) is of interest, especially because the structure-dependency of r is relatively well understood. In this work, the basic characteristics of the relation between EE and r, which turned out to be much more complicated than initially anticipated, was determined.
 Identidades , 2011, Abstract: Rese a de Alejandro Grimson (2011): Los límites de la cultura. Críticas de las teorías de la identidad, Buenos Aires, Siglo XXI, 266 págs.
 Page 1 /100 Display every page 5 10 20 Item


text:
# A General Framework for Multi-level Subsetwise Graph Sparsifiers

Given an undirected weighted graph $G(V,E)$, a subsetwise sparsifier over a terminal set $T\subset V$ is a subgraph $G'$ having a certain structure which connects the terminals. Examples are Steiner trees (minimal-weight trees spanning $T$) and subsetwise spanners (subgraphs $G'(V',E')$ such that for given $\alpha,\beta\geq1$, $d_{G'}(u,v)\leq \alpha d_{G}(u,v)+\beta$ for $u,v\in T$). Multi-level subsetwise sparsifiers are generalizations in which terminal vertices require different levels or grades of service. This paper gives a flexible approximation algorithm for several multi-level subsetwise sparsifier problems, including multi-level graph spanners, Steiner trees, and $k$--connected subgraphs. The algorithm relies on computing an approximation to the single level instance of the problem% and an efficient approach to obtain a multi-level solution. For the subsetwise spanner problem, there are few existing approximation algorithms for even a single level; consequently we give a new polynomial time algorithm for computing a subsetwise spanner for a single level. Specifically, we show that for $k\in\N$, $\eps>0$, and $T\subset V$, there is a subsetwise $(2k-1)(1+\eps)$--spanner with total weight $O(|T|^\frac1kW(\ST(G,T)))$, where $W(\ST(G,T))$ is the weight of the Steiner tree of $G$ over the subset $T$. This is the first algorithm and corresponding weight guarantee for a multiplicative subsetwise spanner for nonplanar graphs. We also generalize a result of Klein to give a constant approximation to the multi-level subsetwise spanner problem for planar graphs. Additionally, we give a polynomial-size ILP for optimally computing pairwise spanners of arbitrary distortion (beyond linear distortion functions), and provide experiments to illustrate the performance of our algorithms.

## Authors

• 12 publications
• 15 publications
• 3 publications
• 38 publications
• 10 publications
• 10 publications
• ### Approximation algorithms and an integer program for multi-level graph spanners

Given a weighted graph G(V,E) and t > 1, a subgraph H is a t--spanner of...
04/01/2019 ∙ by Reyan Ahmed, et al. ∙ 0

• ### Computing Vertex-Weighted Multi-Level Steiner Trees

In the classical vertex-weighted Steiner tree problem (VST), one is give...
11/28/2018 ∙ by Faryad Darabi Sahneh, et al. ∙ 0

• ### Kruskal-based approximation algorithm for the multi-level Steiner tree problem

We study the multi-level Steiner tree problem: a generalization of the S...
02/15/2020 ∙ by Reyan Ahmed, et al. ∙ 0

• ### Multi-level Weighted Additive Spanners

Given a graph G = (V,E), a subgraph H is an additive +β spanner if _H(u,...
02/11/2021 ∙ by Reyan Ahmed, et al. ∙ 0

• ### Multi-Level Steiner Trees

In the classical Steiner tree problem, one is given an undirected, conne...
04/08/2018 ∙ by Reyan Ahmed, et al. ∙ 0

• ### Minimum Weight Pairwise Distance Preservers

In this paper, we study the Minimum Weight Pairwise Distance Preservers ...
07/15/2020 ∙ by Mojtaba Abdolmaleki, et al. ∙ 0

• ### Balanced Crown Decomposition for Connectivity Constraints

We introduce the balanced crown decomposition that captures the structur...
11/09/2020 ∙ by Katrin Casel, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

Graph sparsifiers and sketches have become a fundamental object of study due to the breadth of applications which benefit from them and the power that such techniques have for data compression, computational speedup, network routing, and many other tasks [liu2018graph]. Some canonical examples of graph sparsifiers are spanners [doi:10.1002/jgt.3190130114], spectral sparsifiers [spielman2011spectral], spanning trees, and Steiner trees [Karp1972]. Sparsifier constructions attempt to delete as much edge weight from the graph as possible while maintaining certain properties of the underlying graph; for instance, spanners are subgraphs which approximately preserve the shortest path distances in the initial graph, whereas spectral sparsifiers maintain the properties of the graph Laplacian matrix and are useful in fast solvers for linear systems [spielman2014nearly].

Multi-level graph representations have been increasingly utilized, as many networks contain within them a notion of priority of nodes. Indeed, displaying a map of a road network with varying detail based on zoom level is an instance where vertices (intersections) are given priority based on the size of the roads. Alternatively, following a natural disaster, a city might designate priorities for rebuilding infrastructure to connect buildings; buildings with higher priority will be connected first, for example the city will first ensure that routes from major hubs to hospitals are repaired. Multi-level variants of the Steiner tree problem and the multiplicative spanner problem were studied in [MLST2018] and [MLGS_arx], respectively.

In this paper, we give some general and flexible algorithms for finding certain types of graph sparsifiers for multi-level graphs (which may also be cast as grade-of-service problems). The class of sparsifiers includes many variants of Steiner trees and spanners, among others. In the spanner case, the algorithms presented here necessitate a solution to the subsetwise spanner problem in which one seeks to find a subgraph in which distances between certain prescribed vertices are preserved up to some small distortion factor. Specifically, given a distortion function satisfying (typically for ), and a subset , a subsetwise spanner of is a subgraph such that for all , where denotes the length of the shortest - path in

. We describe a compact integer linear program (ILP) formulation to this problem, and also give a novel and simple polynomial time approximation algorithm and prove corresponding bounds on the weight of multiplicative subsetwise spanners (Theorems

3.1 and 3.1); such bounds have thus far not been considered in the literature. These weight bounds are both in terms of the optimal solution to the problem and of the weight of the Steiner tree over the given subset. In particular, for , , and , we obtain a subsetwise –spanner (i.e. and ) with weight times the weight of the Steiner tree over (which is the minimum-weight tree spanning the vertices ). In the subsetwise spanner case, this is a stronger notion of lightness than previous spanner guarantees in terms of the weight of the minimal spanning tree of the graph. Moreover, this weight bound is for arbitrary graphs, whereas the only previous bound of this type was for planar graphs [Klein06].

We also provide numerical experiments to illustrate our algorithms in the appendix, and show the effect on the single level subroutines used in our main algorithm.

### 1.1 Problem Statement

First, we quantify the kinds of sparsifiers that our algorithms are flexible enough to handle. In what follows, graphs will be weighted, connected, and undirected. We say that is an admissible graph sparsifier of over terminals provided is a connected subgraph of and . We typically assume that has some sort of structure, such as it is a tree, or it approximately maintains distances between terminals. Moreover, we assume that for a given type of sparsifier, there exists a merging operation such that if terminals are not disjoint, and are admissible sparsifiers of over and , respectively, then is an admissible sparsifier of over . The multi-level sparsifier problem under consideration is as follows.

###### Problem 1 (Multi-level Admissible Graph Sparsifier (MLAGS) Problem)).

Given a weighted, connected, undirected graph , a nested sequence of terminals , and an edge cost function for each level , (typically is a function of and ), compute a minimum-cost sequence of admissible sparsifiers where is an admissible sparsifier (of the same type) for over . The cost of a solution is defined to be

 COST(Gℓ,…,G1)=ℓ∑i=1∑e∈Eic(e).

There is an equivalent formulation of this problem in terms of grades of service; see [MLGS_arx] for a full explanation.

### 1.2 Examples

One example of an admissible sparsifier over a set of terminals is a Steiner tree. A Steiner tree of over is a subtree of  that spans , possibly including other vertices, and is denoted . The classical Steiner tree problem (ST) is to find a minimum-weight edge set that spans all terminals. ST is one of Karp’s initial NP–hard problems [Karp1972], is APX–hard [Bern1989], and cannot be approximated within a factor of unless P = NP [Chlebnik2008]. The edge-weighted ST problem admits a simple 2-approximation [Gilbert1968] by computing a minimum spanning tree on the metric closure111Given , the metric closure of is the complete graph , where edge weights are equal to the lengths of shortest paths in . of . The LP–based approximation algorithm of Byrka et al. [Byrka2013] guarantees a ratio of . Several other variants of the ST problem on graphs are admissible sparsifiers including –dense ST, prize-collecting ST, and bottleneck ST. Details about these ST problem variants can be found in the online compendium and references therein [hauptmann2013compendium].

Another example of admissible sparsifier is a –connected subgraph [laekhanukit2011improved], in which (similar to the ST problem) a set of terminal vertices are given, and the goal is to find the minimum weight subgraph such that each pair of the terminals is connected with at least vertex disjoint paths.

Another example of an admissible sparsifier is the pairwise spanner with arbitrary distortion. Multiplicative spanners, initially introduced by Peleg and Schäffer [doi:10.1002/jgt.3190130114] are subgraphs which approximately preserve distances up to a multiplicative factor, i.e., for all . The most general type of spanner is the pairwise spanner, where one is given a set of pairs , and a distortion function satisfying , and one attempts to find the subgraph of smallest weight or minimal number of edges such that

 dG′(u,v)≤f(dG(u,v)),(u,v)∈P.

Any subgraph satisfying this condition is called a pairwise spanner of with distortion , or a subsetwise –spanner for short. Common distortion functions are (multiplicative spanners), (additive spanners), or (linear, or (–spanners). In the case that , we simply use the term spanner, whereas if , for some , then we use the term subsetwise spanner.

The merging operator is sparsifier specific. For example, in case of spanners and –connected subgraphs, it would simply be the union of the subgraphs, while for Steiner trees it would be to take the union and prune edges to enforce the tree structure.

Note that spectral sparsifiers are not admissible since they are not subgraphs as edges can be added to obtain a spectral sparsifier of a graph.

### 1.3 Related Work

There are several results known about multi-level or grade-of-service Steiner tree problems for weighted graphs. Balakrishnan et al. [Balakrishnan1994] give a –approximation algorithm for the 2–level network design problem with proportional edge costs where . Charikar et al. [Charikar2004ToN] describe a simple –approximation for the Quality-of-Service (QoS) Multicast Tree problem with proportional edge costs (termed the rate model), which was later improved to by randomized doubling. Karpinski et al. [Karpinski2005] use an iterative contraction scheme to obtain a -approximation. Ahmed et al. [MLST2018] have further improved the approximation ratio to , by combining top-down and bottom-up strategies.

Among the few discussions of multi-level graph spanners is [MLGS_arx], where level-dependent approximation guarantees are given assuming a single level subsetwise spanner oracle. However, it would be a significant improvement if approximation algorithms for subsetwise spanners were used instead of an oracle in [MLGS_arx]. Coppersmith et al. [coppersmith2006sparse] study the subsetwise distance preserver problem (the case ) and show that given an undirected weighted graph and a subset of size , one can construct a linear size preserver in polynomial time. Cygan et al. [Cygan13] give polynomial time algorithms to compute subsetwise and pairwise additive spanners for unweighted graphs and show that there exists an additive pairwise spanner of size with additive stretch. They also show how to construct size subsetwise additive 2–spanners. Abboud et al. [Abboud16] improved that result by showing how to construct size subsetwise additive 2–spanners. Kavitha [Kavitha2017] shows that there is a polynomial time algorithm which constructs subsetwise spanners of size and for additive stretch 4 and 6, respectively. Bodwin et al. [Bodwin:2016:BDP:2884435.2884496] give an upper bound on the size of subsetwise spanners with polynomial additive stretch factor. To the authors’ knowledge, there are no existing guarantees for multiplicative subsetwise spanners except those of Klein [Klein06] who gives a polynomial time algorithm that computes a subsetwise multiplicative spanner of an edge weighted planar graph for a constant stretch factor with constant approximation ratio.

Hardness of approximation of multi-level spanners follows from the single level case. Peleg and Schäffer [doi:10.1002/jgt.3190130114] show that determining if there exists a –spanner of with or fewer edges is NP–complete. Further, it is NP–hard to approximate the (unweighted) –spanner problem for to within a factor of even when restricted to bipartite graphs [Kortsarz2001].

## 2 A General Rounding Up Approach

Here, we give a very general and flexible extension of the rounding approach of Charikar et al. [1288137] for designing Steiner trees, which we apply to compute approximate solutions to the MLAGS problem based on solving the problem at a subset of levels. Furthermore, we also consider a more general cost model compared to [MLGS_arx] and [MLST2018] for multi-level design. We assume the cost of an edge on a given level can be decomposed as for all , where is a cost scaling function. That is, the cost scales uniformly over edges for a given level. Hence our cost model is more general than the case considered in [MLGS_arx] where as is an arbitrary non-decreasing function.

Additionally, consider a rounding up function, or “level quantizer,”

 q:{1,…,ℓ}→Q={i1=1,…,im}⊂{1,…,ℓ},

which satisfies . Suppose also that there exists a positive constant

 g(q(i))≤Ag(i),i=1,…,ℓ, (1)

and there exists a constant such that if appears on level , then

 k∑j=1g(ij)w(e)≤Bg(ik)w(e). (2)

The latter can also be written as .

Our general rounding up algorithm for computing a MLAGS is as follows. For each , compute an admissible sparsifier over terminals , and let be the subgraphs returned. Then for we will set as follows:

 Gi=⎛⎜ ⎜ ⎜⎝⨁j>ij∈QHj⎞⎟ ⎟ ⎟⎠⊕Hk (3)

where is defined as the largest element in less than or equal to . In other words, the graph on level is the merging (in the sense of the operator ) of all computed sparsifiers on higher levels, as well as the computed sparsifier . For example, if and , then , , and . The rounding up approach of Charikar et al. [1288137] is a special case where .

Given a graph , terminal sets , a level cost function , and a rounding function with rounding set which satisfies conditions (1) and (2), Algorithm 1 yields an –approximation to the MLAGS problem, where .

###### Proof.

By assumption (1), if we consider to be the optimal solution to the rounded MLAGS problem where edges are assigned levels instead of , then an edge costs at most times what it would have in the optimal solution for the unrounded MLAGS problem. By summing over , this implies that , where OPT is the cost of the optimal solution to the full MLAGS problem.

Again consider the optimal solution to the rounded problem with cost . Given any edge in this solution, if its level is , then we may replace the edge with edges on levels . The total cost of these edges is then

 k∑j=1g(aj)w(e)≤Bg(ak)w(e)=Bcak(e)

by (2). At each rounded level, Algorithm 1 computes an –approximation to the optimal subsetwise spanner; it follows that the spanner returned by the algorithm has cost no worse than which is at most from the previous analysis, and the proof is complete. ∎

Note that the proof of Theorem 2 is independent on the type of sparsifier desired, and hence the algorithm is quite flexible. A similar approach was used to approximate minimum-cost multi-level Steiner trees in [MLST2018], but the above analysis shows this approach also works for spanners and –connected subgraphs, for example.

Now we can compute the approximation guarantee given . Let denote the cost of a minimum sparsifier of over . As , we have . Then the following holds ( is the cost of the output of Algorithm 1 for a given ).

For any set , we have , where .

###### Proof.

This follows from the merging bound; note that the edges of the subgraph appear on all levels. The edges from the subgraph appear on levels, namely 1, 2, …, . ∎

Then applying Lemma 2 for a particular , we have

 R(Q)OPT≤∑mk=1g(ik+1−1)MIN% ik∑ℓi=1MINi,

where we have used the observation that Therefore, the right-hand side of the above inequality provides a approximation guarantee assuming knowledge of . We can also find a generic bound by looking at the worst case scenario for . Without loss of generality, we may assume that , so that . Since is an increasing function, the worst case of level costs will be of the form and for some . Therefore, the general approximation guarantee (regardless of costs of the subset sparsifiers of each level) is

 minh∑hk=1g(ik+1−1)ih

### 2.1 Examples

A natural example is to take , i.e., a linear cost growth along levels. Following Charikar et al. [1288137], we may take . In this case, using an oracle to compute the subsetwise spanner at each level yields a –approximation to the MLAGS problem for a multiplicative –spanner. The same approximation holds in this case for multi-level Steiner trees [MLST2018]. Indeed, , whence we may choose , and if edge gets its rate rounded to , then

 k∑j=1ijw(e)=k∑j=12jw(e)≤2⋅2jw(e)=2c(e),

whence , thus yielding a 4–approximation. This yields the following corollary improves on Theorems 1 and 3 in [MLGS_arx], as the approximation ratio is independent of the number of levels. Let . If an oracle which computes the optimal subsetwise multiplicative –spanner of over terminals is used in Algorithm 1, and , then Algorithm 1 produces a –approximation to the optimal multi-level graph spanner problem. Note that the use of an oracle such as the ILP given in Appendix A is costly; this issue will be addressed in Section 3.

It is of interest to note that choosing for some other base does not improve the approximation ratio. In this case, one can show that , and is approximately , and thus the approximation ratio is which is minimized when .

Using a coarser quantizer instead yields a worse approximation. Consider the coarsest quantizer which sets for all and , with as before. In this case, , and , which means that the best one can do is an –approximation. This approach corresponds to the Bottom Up approach described in [MLGS_arx].

If no rounding is done (i.e., ), then one computes a sparsifier at each level and merges them together according to the operation going down the levels. This can be considered a Top Down approach to the problem, and yields an upper bound on the approximation ratio of .

### 2.2 Composite Algorithm

One way to find a good approximation algorithm is to run Algorithm 1 for all subsets containing 1, and then choosing the multi-level sparsifier with the smallest cost. This requires sparsifier computations followed by finding the minimum over solutions. Consequently, this method is costly to implement; however, it provides the lowest cost and the best guarantees possible using single-level solvers. We call this the composite algorithm.

We can find the approximation guarantee of the composite algorithm using the following linear program (LP):

Find subject to

 t
 ℓ∑i=1MINi=1,MINℓ≤…≤MIN1

This optimization problem suggested above is similar to that in [MLST2018]. In particular, for linear costs () and , the solution returned by the composite algorithm has cost no worse than assuming an oracle that computes sparsifiers optimally. This approach uses sparsifier computations, and computes the minimum over candidate solutions.

### 2.3 Computing the Best Rounding Set Q

Suppose having computed all single-level solutions, we are interested to find what

would provide the least multi-level solution. We formulate this as a minimization problem. Define binary variables

such that and otherwise. For example if and , and .

Given a vector

, the choice of from the following ILP minimizes , where is the th smallest element of and .

 minℓ∑i=1ℓ+1∑j=i+1g(j−1)θijyi subject to ∑j>iθij ≤1,∑ikθkj k∈{2,…,ℓ} ∑1
###### Proof.

Using the indicator variables, the objective function can be expressed as
because and the other ’s are zero. In the above formulation, the first constraint indicates that for every given or , at most one is equal to one. The second constraint indicates that for a given , if for some , then there is also a such that . In other words, the result determines a proper choice of levels by ensuring continuity of intervals. The last constraints guarantees that . ∎

## 3 Metric Closure Multi-level Spanners

Observe that when the admissible sparsifier is a subsetwise spanner, the composite algorithm proposed above necessitates having a good algorithm for computing a subsetwise spanner on a single level with a given distortion. Unfortunately, there are precious few algorithms that provably approximate the subsetwise spanner problem. In this section, the cost at each level is assumed to be .

[Metric Closure] Given a graph and a set of terminals , the metric closure of over is defined as the complete weighted graph on vertices with the weight of edge given by .

Here, we give a new and simple algorithm for computing a subsetwise spanner with general distortion function . We will use an –spanner subroutine in this algorithm which must work for weighted graphs. Note that most spanner algorithms for weighted graphs are usually of the multiplicative type.

### 3.1 Metric Closure Subsetwise Spanners

Algorithm 3 describes a subsetwise spanner construction; later we will generalize this to multi-level spanners in Algorithm 4, but even for the case of a single level this provides a novel approximation for a subsetwise spanner.

Note that the spanner obtained in the second step can come from any known algorithm which computes a spanner for a weighted graph, which adds an element of flexibility. This also allows us to obtain some new results on the weight of multiplicative subsetwise spanners.

It is known (see [Alstrup2017]) that if is a positive integer, then one can construct a –spanner for a given graph (over all vertices, not a subset), in time, which has weight , where is a minimum spanning tree of . Using this in the second stage of the Algorithm 3, we can conclude the following.

Let , , , and be given. Using the spanner construction of [Alstrup2017] as a subroutine, Algorithm 3 yields a subsetwise –spanner of in time with total weight . Moreover,

###### Proof.

Let be the metric closure of over , and let be the minimum weight subsetwise –spanner for , where is any distortion function. Note that must contain a tree, , which spans , whence

 W(G∗)≥W(G∗0)≥W(ST(G,T)) (4)

by definition of Steiner trees. From the approximation result for Steiner trees (see [bang2004]) we have

 W(MST(~G))≤2W(ST(G,T)). (5)

It follows that . Now, using the results of [Alstrup2017] for the special case where and , we can construct a –spanner of which satisfies

 W(~G′)=O(|T|1k)W(MST(~G)). (6)

Combining these we have the desired estimate

 W(~G′)≤O(|T|1k)W(G′)=O(|T|1k)OPT.

Finally, follows from (5). ∎

Both bounds given in Theorem 3.1 are interesting for different reasons. The first stated bound shows that Algorithm 4 yields an –approximation to the optimal solution. The second bound gives a better notion of lightness of a subsetwise spanner. When , the minimal spanning tree and the Steiner tree over are the same, and hence lightness bounds for spanners in this case are stated in terms of the weight of . However, for it is not generally true that , but by definition the Steiner tree has smaller weight. Thus, this notion of lightness for subsetwise spanners stated in terms of the weight of the Steiner tree is more natural. Klein [Klein06] uses this notion of lightness for subsetwise spanners of planar graphs, but the results presented here are the first for general graphs.

The following gives a precise (as opposed to asymptotic) bound for a subsetwise spanner by utilizing the greedy algorithm of Althöfer et al. [Alth90].

Let , , and be given. Using the greedy spanner algorithm as a subroutine, Algorithm 3 yields a subsetwise –spanner of in time with total weight . Moreover, .

###### Proof.

The greedy algorithm takes time, and the rest is similar to the proof of previous theorem. ∎

Note that in the greedy spanner algorithm of Althöfer et al. [Alth90], the minimum spanning tree is a subgraph of the solution. However, the optimal Steiner tree might not necessarily be a subset of the final solution. Nevertheless, the produced subset spanner will include a Steiner tree with cost at most twice the optimal one.

### 3.2 Multi-level Metric Closure Spanner

Here, we propose the multi-level version of the spanner in Algorithm 4. Note this is different than using Algorithm 3 as a subroutine in Algorithm 1.

Here we provide a general bound which is also tight in certain cases and can be derived easily.

Given a graph and terminals , and a multiplicative stretch factor (so the distortion is ), let be the total cost of the multilevel –spanner of Algorithm 4. Then Moreover, if then

###### Proof.

The bounds follow from the fact that and . ∎

Now, we show that the bound is tight for the case . Consider a graph with terminal sets such that there is a unique shortest path of length between any pairs of terminals. Assume that we do not have any other vertex in beyond the ones appearing on these shortest paths. The diameter of is clearly and we need shortest paths to be copied across all levels. Therefore, we end up with the cost for the multilevel spanner.

## 4 Polynomial Time Approximation Algorithms

Solving a single level ILP takes much less time than solving a multi-level ILP, especially as the number of levels increases. This fact was one of the motivations behind the rounding algorithm. If a single level ILP is used as an oracle subroutine as in Corollary 2.1 then a constant approximation ratio is obtained, but at the expense of the subroutine being exponential time.

It is natural to consider what happens when the subsetwise spanner Algorithm 3 is used as the approximation algorithm in Algorithm 1. By Theorem 3.1, Algorithm 3 is a –approximation on any single level, and hence combining this with Theorem 2, we find that Algorithm 1 yields an –approximation to the multi-level graph spanner problem with stretch factor for all levels.

If the input graph is planar then instead of using Algorithm 3 we can use the algorithm provided by Klein [Klein06] to compute a subsetwise spanner for the set of levels we get from the rounding up algorithm. The polynomial time algorithm in [Klein06] has constant approximation ratio, assuming that the stretch factor is constant. Hence, we have the following Corollary.

Let be a weighted planar graph with terminals, . Let be a constant, and suppose the level cost function is . Then there exists polynomial time, constant approximation (independent of the number of levels) for the optimal multi-level -spanner problem.

For additive spanners there exists algorithms to compute subsetwise spanner of size , and for additive stretch 2, 4 and 6, respectively [Abboud16, Kavitha2017]. If we use these algorithms in Algorithm 1 to compute subsetwise spanners for different levels, then we have the following Corollary.

Let be an unweighted graph with exponentially decreasing terminals, such that . Then there exists polynomial time algorithms to compute multi-level graph spanners with additive stretch 2, 4 and 6, of size , , and , respectively.

## 5 Experimental results

To evaluate the performance of different variants of Algorithm 1 we use several experiments. This requires optimal single-level solvers for Algorithm 1, which we obtain using an ILP formulation of the problem; see Appendix A. We generate graphs using the Erdős–Rényi random graph model [erdos1959random]; more details for the experiment are in Appendix B.

We then consider the multiplicative graph spanner version of the MLAGS problem, and analyze the effect of using an ILP vs. the metric closure subsetwise spanner Algorithm 3 for the single level approximation therein. Figure 1 shows the impact of different parameters (number of vertices , number of levels , and stretch factors ) using box plots for the two approaches corresponding to 3 trials for each parameter. In general, the performance of both variants decreases as the number of levels and stretch factor increases. It is notable that the metric closure approximation algorithm yields very similar results to those from ILP solver.

In the Appendix, we consider three variants for the rounding set: , which we call bottom-up (BU), , which we call top-down (TD), and the optimal , which we call (CMP). Varying the size of the input graph, number of levels, and stretch factor , we test the performance of Algorithm 1. If the ILP is used in the single level solver, we call these oracle TD, BU, and CMP, and otherwise we call them the metric closure TD, BU, and CMP solutions.

Figures are shown in Appendix B, and we only summarize the results here. Generally, both the runtime and the approximation ratio for the multi-level graph spanner problem increase as the size of the parameter increases for the oracle TD, BU, and CMP algorithms. We cannot compute the exact solution for large graphs, but the metric closure variant scales well. Thus for large graphs the estimation of the approximation ratio is given to be , for example. In this case, the runtime increases with larger input graphs, but interestingly increasing the number of levels and stretch factors does not have a strong impact on the performance.

## 6 Conclusions and Future Work

We have given a general framework for solving multi-level graph sparsification problems utilizing single level approximation algorithms as a subroutine. When an oracle is used afor the single level instances, our algorithm can yield a constant approximation to the optimal multi-level solution that is independent of the number of levels. Using the metric closure subsetwise spanner algorithm as a subroutine for the multi-level spanner algorithm, we derive an approximation algorithm which depends on the size of the terminal set but not the number of levels. It would be natural to look for multi-level algorithms that do not rely on single level instances of the problem but build the solution simultaneously on all levels.

Additionally, we gave a new algorithm for finding subsetwise spanners of weighted graphs via the metric closure over the subset, and gave novel weight bounds in the case of multiplicative spanners. It would be worthwhile to explore new approximation algorithms for the subsetwise spanner problem, which would strengthen the results in this paper.

## Appendix A Integer Programming Formulation for Pairwise Spanners

Here we describe an ILP solver which gives a minimum cost solution to the pairwise spanner problem with arbitrary distortion function . This may be used as an oracle subroutine in Algorithm 1.

Sigurd and Zachariasen [sigrd04] give an integer linear programming (ILP) formulation for the minimum cost pairwise –spanner problem, where individual paths are decision variables (hence the ILP has exponentially many parameters in terms of the number of edges). In [MLGS_arx], a compact flow-based formulation for the minimum-cost pairwise –spanner problem using variables and constraints is given; however, it turns out that the ILP is valid for generic distortion functions. Let be the subset of vertex pairs on which distances are desired to be preserved, and let be any function satisfying for all (note the function need not be continuous). Let if is included in the spanner, and otherwise. Given , let be the bidirection graph of obtained by replacing every edge with two directed edges and each of weight (thus ). Given , and an unordered pair of vertices , define indicator variables by if edge is included in the selected path in the spanner , and 0 otherwise. Let and denote the set of incoming and outgoing edges from , respectively.

Next we select a total order of all vertices so that the path constraints (9)–(10) are well-defined. In (8)–(12) we assume in the total order, so spanner paths are from to . The ILP is as follows.

 \allowdisplaybreaksMinimize∑e∈Ew(e)xe % subject to (7) ∑(i,j)∈¯Exuv(i,j)ce ≤f(dG(u,v)) ∀(u,v)∈P,u

Ordering the edges induces binary variables, or variables in the full spanner problem where . Note that if and are connected by multiple paths in of length , we need only set for edges along some path. The following is the main theorem for this ILP.

Given a graph , a subset , and any distortion function which satisfies for all , the solution to the ILP given by (7)–(12) is an optimally light (or sparse if is undirected) pairwise spanner for with distortion .

###### Proof.

Let denote an optimal pairwise spanner of with distortion , and let OPT denote the cost of (number of edges or total weight if is unweighted or weighted, respectively). Let denote the minimum cost of the objective function in the ILP (7). First we notice that from the minimum cost spanner , a solution to the ILP can be constructed as follows: for each edge , set . Then for each unordered pair with , compute a shortest path from to in , and set for each edge along this path, and if is not on .

As each shortest path necessarily has cost at most , constraint (8) is satisfied. Constraints (9)–(10) are satisfied as is a simple path. Constraint (11) also holds as cannot traverse the same edge twice in opposite directions. In particular, every edge in appears on some shortest path; otherwise, removing such an edge yields a pairwise spanner of lower cost. Hence .

Conversely, an optimal solution to the ILP induces a feasible pairwise spanner with distortion . Indeed, consider an unordered pair with , and the set of decision variables satisfying . By (9) and (10), these edges form a simple path from to . The sum of the weights of these edges is at most by (8). Then by (11), the chosen edges corresponding to appear in the spanner, which is induced by the set of edges with . Hence .

Combining the above observations, we see that , and the proof is complete. ∎

In the multiplicative spanner case, the number of ILP variables can be significantly reduced (see [MLGS_arx] for more details). These reductions are somewhat specific to multiplicative spanners, and so it would be interesting to determine if other simplifications are possible for more general distortion.

Note that the distortion does not have to be continuous, which allows for tremendous flexibility in the types of pairwise spanners the above ILP can produce.

## Appendix B Experiments

### b.1 Setup

We use the Erdős–Rényi [erdos1959random] model to generate random graphs. Given a number of vertices,

, and probability

, the model assigns an edge to any given pair of vertices with probability . An instance of with is connected with high probability for  [erdos1959random]). For our experiments we allow to range from 5 to 300, and set .

For experimentation, we consider only the multiplicative graph spanner version of the MLAGS problem, hence we abbreviate this as MLGS; for similar experimental results on multi-level Steiner trees, see [MLST2018]. An instance of the MLGS problem is characterized by four parameters: the graph generator, the number of vertices , the number of levels , and stretch factor . As there is randomness involved, we generated 3 instances for every choice of parameters (e.g., ER, , , ).

We generated MLGS instances with 1 to 6 levels (), where terminals are selected on each level by randomly sampling vertices on level so that the size of the terminal sets decreases linearly. As the terminal sets are nested, can be selected by sampling from (or from if ). We used four different stretch factors in our experiments, . Edge weights are randomly selected from .

### b.2 Algorithms and outputs

We implemented several variants of Algorithm 1, which yield different results based on the rounding set as well as the single level approximation algorithm. In our experiment we used three setups for : bottom-up (BU) in which , top-down (TD) in which , and composite (CMP) which selects the optimal set of levels as in Section 2. We used Python 3.5, and utilized the same high-performance computer for all experiments (Lenovo NeXtScale nx360 M5 system with 400 nodes). When using an oracle for single levels in Algorithm 1, we use the ILP formulation provided in Appendix A using CPLEX 12.6.2.

For each instance of the MLGS problem, we compute the costs of the MLSG returned using the BU, TD, CMP approaches, and also compute the minimum cost MLGS using the ILP in Appendix A. For the first set of experiments, we use the ILP as an oracle to find the minimum weight spanner for each level; in this case we refer to the results as Oracle BU, TD, and CMP. In the second set of experiments, we use the metric closure subsetwise spanner Algorithm 3

as the single level subroutine, which we refer to as Metric Closure BU, TD, and CMP. We show the performance ratio for each heuristic in the

–axis (defined as the heuristic cost divided by OPT), and how the ratio depends on the input parameters (number of vertices , number of levels , and stretch factors ).

Finally, we discuss the running time of the algorithms. All box plots show the minimum, interquartile range and maximum, aggregated over all instances using the parameter being compared.

### b.3 Results

Figures 25 show the results of the oracle TD, BU, and CMP. We show the impact of different parameters (number of vertices , number of levels , and stretch factors ) using line plots for the three approaches separately in Figures 2-4. Figure 5 shows the performance of the three variants together in box plots. In Figure 2 we can see that all variants perform better when the size of the vertex set increases. Figure 3 shows that all variants perform worse as the number of levels increases. In Figure 4 we see that in general, performance decreases as the stretch factor increases.

The most time consuming part of the experiment is the execution time of the ILP for solving MLGS instances optimally. Hence, we first show the running times of the exact solution of the MLGS instances in Figure 6 with respect to the number of vertices , number of levels , and stretch factors . For all parameters, the running time tends to increase as the size of the parameter increases. In particular, the running time with stretch factor 4 (Fig. 6, right) was much worse. We can reduce the size of the ILP by removing some constraints based on different techniques discussed in [MLGS_arx]. However, these size reduction techniques are less effective as the stretch factor increases. We show the running times of computing oracle bottom-up, top-down and composite solutions in Figure 7. Notice that, although the running time of composite should be worse, sometimes top down takes more time. The reason is that we have an additional edge-pruning step after computing subsetwise spanner. In top down, every level has this pruning step, which is causing additional computation time and affecting the runtime especially when the graph is large.

The ILP is too computationally expensive for larger input sizes and this is where the heurstic can be particularly useful. We now consider a similar experiment using the metric closure algorithm to compute subsetwise spanners, as described in Section 3. We show the impact of different parameters in Figures 810. Figure 11 shows the performance of the three algorithms together in box plots. We can see that the heuristics perform very well in practice.

Our final experiments test the heuristic performance on a set of larger graphs. We generated the graphs using the Erdős–Rényi model, with . We evaluated more levels () with stretch factors . Here, the ratio is determined by dividing the BU, TD and CMP cost by (as computing the optimal MLGS would be too time consuming). Figure 12 shows the performance of the bottom-up, top-down and composite algorithms with respect to and . Figure 13 shows the aggregated running times per instance, which significantly worsen as increases. The results indicate that while running times increase with larger input graphs, the number of levels and the stretch factors seem to have little impact on performance. Notably when the metric closure algorithm is used in place of the ILP for the single level solver (Fig. 13), the running times decrease for larger stretch factors.


text:
# Math Help - proof involving least common multiple

1. ## proof involving least common multiple

For every choice of non zero integers a,b,c, the integer lcm[a,c] divides
the integer lcm[a,b] * lcm[b,c] / b.

I was thinking of letting a=p/q, b=r/s, c=t/u. Then, somehow, the integer lcm[a,b] * lcm[b,c] / b will factor out an lcm[a,c], but I am not sure how to prove it that way.

2. I thought about it, and this is what I got so far:

lcm[a,b] = ab/(a,b), and so on.

(a,c)=ax+cy
(a,b)=ax+by
(b,c)=bx+cy

(a,b)(b,c)=(ax+by)(bx+cy)=(abx^2 + acxy+ b^2 xy + bcy^2)
I am not sure how to factor a ax+cy out of that...

3. Let $p_1,...,p_n$ be the set of primes which divide either one of $a,b \mbox{ or } c$. Write

$a=p_1^{\alpha_1}\hdots p_n^{\alpha_n}$

$b=p_1^{\beta_1}\hdots p_n^{\beta_n}$

$c=p_1^{\gamma_1}\hdots p_n^{\gamma_n}$

be the canonical factorizations of $a,b,c$, where some of the exponents may be 0. Then, letting $M(x,y)=\mbox{max }\{x,y\}$,

$\mbox{lcm }(a,b)=p_1^{M(\alpha_1,\beta_1)}\hdots p_n^{M(\alpha_n,\beta_n)}$

$\mbox{lcm }(b,c)=p_1^{M(\gamma_1,\beta_1)}\hdots p_n^{M(\gamma_n,\beta_n)}$

and hence

$\frac{\mbox{lcm }(a,b)\mbox{lcm }(b,c)}{b}=p_1^{M(\alpha_1,\beta_1)+M(\gamma_1,\be ta_1)-\beta_1}\hdots p_n^{M(\alpha_n,\beta_n)+M(\gamma_n,\beta_n)-\beta_n}$

Now you just need to show that, for every $1 \leq j \leq n$, we have $M(\alpha_j,\beta_j)+M(\gamma_j,\beta_j)-\beta_j\geq M(\alpha_j,\gamma_j)$. Hint : consider separately the case where $M(\alpha_j,\gamma_j)=\alpha_j$ and the case where $M(\alpha_j,\gamma_j)=\gamma_j$.

4. Thanks.

Shouldn't the two cases be $M(\alpha_j,\gamma_j)=\alpha_j$ and $M(\alpha_j,\gamma_j)=\gamma_j$?

If so, would this be ok?
If $M(\alpha_j,\gamma_j)=\alpha_j$, then $\alpha_j \geq \gamma_j$
If $\beta_j \geq \alpha_j$, then we have $\beta_j + \beta_j - \beta_j \geq \alpha_j$, which is true.
If $\beta_j \leq \alpha_j$, then we have $\alpha_j + M(\gamma_j,\beta_j) - \beta_j \geq \alpha_j$, which is true because then $M(\gamma_j,\beta_j) \geq \beta_j$

If $M(\alpha_j,\gamma_j)=\gamma_j$, then $\alpha_j \leq \gamma_j$
If $\beta_j \geq \gamma_j$, then we have $\beta_j + \beta_j - \beta_j \geq \gamma_j$, which is true.
If $\beta_j \leq \gamma_j$, then we have $\gamma_j + M(\alpha_j,\beta_j) - \beta_j \geq \gamma_j$, which is true because then $M(\alpha_j,\beta_j) \geq \beta_j$

5. Flawless! Good job.

There may be a shorter way... but when you have proofs with greatest common divisors and least common multiples, a guaranteed path to success is to translate the identity you wish to prove as a statement about the canonical factorization of the numbers involved. It might be hard work but it always takes you where you want to go - just be careful choosing a good notation so you don't hit a brick wall.

I corrected my post above - thanks for the heads up

6. I know this is done, but I just wanted to point something out that could help in the future ...

This was written down:
(a,c)=ax+cy
(a,b)=ax+by
(b,c)=bx+cy

But we can not assume that all the x and y are the same ... that's the bit that could help in the future ... make sure you distinguish your variables:

Another way to prove this is:

definition of lcm[a,b]=d is the d is the smallest integer such that a|d and b|d
let [a,b] = d, [a,c] = e, and [b,c] = f
since b|d and b|f, let bx=d and by=f

We are trying to show that [a,c]|[a,b][b,c]/b ... in other words, e|df/b

df/b = bxf/b = xf and since c|f, c|df/b
df/b = dby/b = dy and since a|d, a|df/b

So a|df/b and c|df/b ... so df/b is a common multiple of a and c ... can you show that the [a,c] divides this common multiple?


text:
## Bernoulli

• Bernoulli
• Volume 13, Number 2 (2007), 473-491.

### Estimation of the memory parameter of the infinite-source Poisson process

#### Abstract

Long-range dependence induced by heavy tails is a widely reported feature of internet traffic. Long-range dependence can be defined as the regular variation of the variance of the integrated process, and half the index of regular variation is then referred to as the Hurst index. The infinite-source Poisson process (a particular case of which is the $M/G/∞$ queue) is a simple and popular model with this property, when the tail of the service time distribution is regularly varying. The Hurst index of the infinite-source Poisson process is then related to the index of regular variation of the service times. In this paper, we present a wavelet-based estimator of the Hurst index of this process, when it is observed either continuously or discretely over an increasing time interval. Our estimator is shown to be consistent and robust to some form of non-stationarity. Its rate of convergence is investigated.

#### Article information

Source
Bernoulli, Volume 13, Number 2 (2007), 473-491.

Dates
First available in Project Euclid: 18 May 2007

https://projecteuclid.org/euclid.bj/1179498757

Digital Object Identifier
doi:10.3150/07-BEJ5123

Mathematical Reviews number (MathSciNet)
MR2331260

Zentralblatt MATH identifier
1127.62070

#### Citation

Faÿ, Gilles; Roueff, François; Soulier, Philippe. Estimation of the memory parameter of the infinite-source Poisson process. Bernoulli 13 (2007), no. 2, 473--491. doi:10.3150/07-BEJ5123. https://projecteuclid.org/euclid.bj/1179498757

#### References

• Barakat, C., Thiran, P., Iannaccone, G., Diot, C. and Owezarski, P. (2002). A flow-based model for internet backbone traffic. In, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurement, pp. 35–47. New York: ACM Press.
• Cohen, A. (2003)., Numerical Analysis of Wavelet Methods. Amsterdam: North-Holland.
• Duffield, N.G., Lund, C. and Thorup, M. (2002). Properties and prediction of flow statistics from sampled packet streams. In, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurement, pp. 159–171. New York, ACM Press.
• Fa\"y, G., Roueff, F. and Soulier, P. (2005). Estimation of the memory parameter of the infinite source Poisson process., arXiv:math.ST/0509371v2.
• Hall, P. and Welsh, A.H. (1984). Best attainable rates of convergence for estimates of regular variation., Ann. Statist. 3 1079–1084.
• Künsch, H.R. (1987). Statistical aspects of self-similar processes. In Yu.A. Prohorov and V.V. Sazonov (eds), Proceedings of the First World Congres of the Bernoulli Society, Vol. 1, pp. 67–74. Utrecht: VNU Science Press.
• Maulik, K., Resnick, S. and Rootzén, H. (2002). Asymptotic independence and a network traffic model., J. Appl. Probab. 39 671–699.
• Meyer, Y. (1992)., Wavelets and Operators. Cambridge: Cambridge University Press.
• Mikosch, T., Resnick, S., Rootzén, H. and Stegeman, A. (2002). Is network traffic approximated by stable Lévy motion or fractional Brownian motion?, Ann. Appl. Probab. 12 23–68.
• Parulekar, M. and Makowski, A.M. (1997). M/G/infinity input processes: A versatile class of models for network traffic. In, Proceedings of INFOCOM '97, pp. 419–426. Los Alamitos, CA: IEEE Computer Society Press.
• Resnick, S. (1987)., Extreme Values, Regular Variation and Point Processes. New York: Springer-Verlag.
• Resnick, S. and Rootzén, H. (2000). Self-similar communication models and very heavy tails., Ann. Appl. Probab. 10 753–778.
• Wornell, G.A. and Oppenheim, A.V. (1992). Wavelet-based representations for a class of self-similar signals with application to fractal modulation., IEEE Trans. Inform. Theory 38 785–800.


text:
# Emission spectrum wavelengths.

1. Nov 21, 2013

### P.Bo

Something that bugged me when doing this lab. Standard little glass vials of gas, toss it in a 5kV potential make pretty color, look through diffraction grating see the individual wavelengths that are the finger prints of the element.

My question however are all wavelengths equally represented? I'm presuming that there's a rather large number of gas atoms even in a thin glass tube, but for something like hydrogen where the Balmer series has 4 colors, are there an equal number of photons represented at each color when you take the average of the "large" number of transitions occurring? Or are some colors more likely than others?

I'm trying to get my finger on the pulse of the truth behind why some colors look brighter, my initial thought is that our eye sensitivity to certain wavelengths is the sole factor in determining brightness, but now I'm wondering if some colors simply get more photons emitted on average than others.

2. Nov 21, 2013

### TumblingDice

Each line is created by photons emitted by electrons dropping from higher energy levels to lower levels. Contributions to specific lines will depend on the electron levels during the measurement.

The relative brightness of the lines will depend on the distribution of the energy levels of the electrons emitting photons. In the case of your hot gas emission, the amount of energy you introduce to the cloud is what raises the electrons to higher levels, after which they drop and emit photons of discrete energy levels (frequency) based on the starting and ending energy levels. I imagine you could alter the representation of a measurement by adjusting the amount of energy you introduce or the length of time you spread it over.

Brightness of lines also varies with the abundance of atoms. So atomic emission spectra like this can be used to not only determine the presence of a gas, but also information to help determine the density and temperature.

3. Nov 22, 2013

### P.Bo

Yes but what I'm asking for, using Balmer as an example, if you put in enough energy to raise electrons to n=5, is there anything ratio or percentage change that the electron will drop directly to n=2 or go through a n=4 or 3 before dropping to 2.

Basically, there are 4 visible colors with hydrogen. If you have N particles in the gas, will you get N/4 photons of each color per emission? Or are some transitions more likely than others?

4. Nov 22, 2013

### Bill_K

Some are more likely than others. The line intensities derive from the "oscillator strengths". Allowed transitions are electric dipole transitions, in which going from one state |n, , m> to another state |n', ', m'>, the selection rules are m = m' and = ' ± 1.

What remains is to calculate the off-diagonal matrix elements of r, that is <n'|r|n> and square it. Thus it's an integral over a power of r and the product of two Laguerre polynomials.

You can get the results in closed form (it's rather complicated!) or look the values up in a table. The details can be found for example in Bethe and Salpeter, "QM of One and Two Electron Systems" p 262.

Last edited: Nov 22, 2013
5. Nov 22, 2013

### Staff: Mentor

That's actually $\Delta m \equiv m- m' = 0, \pm1$.

6. Nov 22, 2013

### Bill_K

Thanks, you're right!