Streaming algorithm

This is the process of data streaming with less memory.

x∈R^n

This is high dimensional vector.

You update it.

xi←xi+v

You have O(n) space, and the whole stream is O(m).

You compress the data by streaming.

A=(1±ε)B

(1-ε)B≦A≦(1＋ε)B

∴

σi,j = ±1, E[σi,j] = 0

Zeta transform

This is Inclusion-Exclusion.

Then, this is the Zeta transform.

Moreover, this is the inversion.

You prove this.

At first, you use the Zeta transform.

You put the inversion.

You remove the gray area.

You divide S and R.

This is Inclusion-Exclusion.

You got f(R).

Therefore, the Zeta transform is feasible.

Exponential Divide and Conquer

OPT(U,s,t) is the length of s and t, and you choose the cheapest.

You split the path into two halves in all possible ways. This is called Exponential Divide and Conquer.

m is an intermediate point.

｜S｜=｜｜U｜/2｜+1

T∪S=U

T∩S=m

n is nodes.

∴

ε>0

The exponential space is huge.

Minimum-cost flow problem

In a flow network, you need to choose the cheapest path.

This is the directed graph.

G=(V,E)

(u,v)∈E

This is the edge.

c(u,v)>0 (c is the capacity)
f(u,v)≧0 (f is the flow)
a(u,v) is the cost of the path.

The cost of sending this flow is f(u,v)*a(u,v).

You choose the cheapest.

This is the total cost of the flow over all edges.

f(u,v)≦c(u,v)

Then, you think the maximum cardinality matching in G that has minimum cost.

G=(A∪B,E)

G'=(V'=A∪B,E'=E)

The capacity of all the new edges is 1 and their costs is 0.

Link-cut Trees

Blocking flows make a tree because of O(logU). However, this is dynamic trees, so you can delete and insert nodes. There is no direction basically.

This is the algorithm.

initially, makeTree() n times
while(true):
v = findRoot(s)
if (v == t)
//(z,parent(z)) is a min capacity edge with weight x
(z,x) = findMin(s)
subtract(s,x)
cut(z)
delete(z,parent(z)) from the level graph
continue
else
//try to advance
if v has an outgoing edge to some w in L:
link((v,w),capacity(v,w))
else
if (v == s): break
else for every child y of v
cut(y)
delete(y,v) from L

The cost of splaying nodes is O(logU). The total number of preferred child changes is O(m logU).

Blocking flows

It is very hard to find your marriage partner in computer science. In modern society, the marriage means more complicated. Your partner may be animals. You have free choices. I don't care about that.

There is a path between S and T. This is the vector to find your partner. You choose the shortest way.

A blocking flow expand the administrative path with at least the one arc. Moreover, the max flow algorithm is to find the blocking flows.

Life is hard, so you can't go straight always. You need O(m) times to find blocking flows, so the running time of this max flow algorithm is O(mn).

U is the maximum capacity of an edge, and O(mn) is the expanded work. Therefore, the total running time of max flow for scaling blocking flows is O(mn log U).

The minimum fractional set cover problem

You hedge your marriage partner in computer science. You can use dating apps in your smart phones recently, so AI may decide your marriage life soon.

m is the cost vector which is yes or no.

F={S1,S2,・・・,Sm}

This is the Linear probing , so you concentrate on your favorite partner.

p is the hedge which is the vector.

p(S) is the total weight of elements in S.

This is the covering problems, so you search for the optimization by expanding.

L is the maximization of p(S).

(1-ε) is approximation algorithm for maximization.

This is feasible, so there is the possibility for your marriage life.

Stable Matching

This is the marriage problem, so it must be better than insects morally. However, this is computer science, so it is quite mechanical. In this algorithm, everybody must be married. Everybody may hate you, but you are included in this circle. Therefore, everybody has the partner. This is idealistic, but it is just gaming.

They are singles. (1,2,3,4) are males. (a,b,c,d) are females. Male(1) prefers female(a) the most, and Male(2) prefers female(c) the most. This is the competition, so you downgrade your preference like (3:a,b,d,c).

You minimize it for stable matching.

min{n,k}

n is the total number of males, and k is the total number of females.

(1,a) (2,c) (3,b) (4,d)

Everybody is happy mathematically, although male(4) likes female(c) and female(a). Patience is necessary sometimes.

This is not stable. (3,d) and (4,d) are conflict. They may fight each other, although d isn't their favorite woman. They may abandon the marriage. Male(4) chooses female(b) for stable matching, but his life may be the nightmare.

Offspring

We often read arguing about the gender gap on the web. Women have the power politically in these days, but you are just like insects in computer science. In developed countries, there are more women. They have many opportunities. They may have children, or they may pursue the business success. Some men enjoy their single lives. However, some sociologists often insist that the increasing population is necessary for the economic stability. It is criticized that women are not the machine for reproduction, but we are still in the animal instinct mathematically.

There is the free choice to have opposite gender partners. This is chaotic. You call it natural greedy heuristic in computer science.

G=(V,E), V={x1,x2,x3・・・}, E= φ

V is the population, and E is the edge. Men1 has three partners, and women6 has two.

Am is the average of opposite gender partners for men.

Aw is the average of opposite gender partners for women.

∴

Am/Aw=｜Vw｜/｜Vm｜>1

The symmetry is broken in the developed country. This is NP hard, but you have offspring like insects.

You just follow the statistics except for Japanese and German.

Robertson Walker Metric

General Relativity and gravity describe the universe with the large scale, and it is homogeneous and isotropic.

Prime numbers also move the same pattern.

This is called Robertson Walker Metric.

X=a(t)x, Y=a(t)y, Z=a(t)z

t is time.

∴　

dS^2=X^2+Y^2+Z^2

Then you describe a 3D space of constant curvature.

The Hoyle-Narlikar theory of gravitation

Pascal’s triangle is symmetric, and prime numbers are fractal.

You need time to find all numbers even in quantum computers.

Then we talk about gravity.

The universe expands infinitely, but it is finite because of masses. They have the same sign.

a and b are particles over the world lines. G is the green function which satisfies the wave equation.

G* must be symmetric.

rst is retarded, and adv is advanced.

It cannot be satisfied for any models of the universe, so it can’t contain an infinite amount of matter.

φ=-κρ (ρ>0)

ρ is the density. φ is infinite and the same sign. Infinity destroys the Newton theory, so it expands the universe but it is also retarded.