I blog about algorithm and theory related stuff…
I try to get sublime text’s markdown syntax highlighter to work with markdown + latex. (thus support even more of pandoc flavored markdown.)
Here is the current code. https://gist.github.com/Mgccl/195ce33124f384a2f4e4
I’m doing research on ways to compute maximum flow over a unit capacity undirected graph with a subset T of vertices having unit capacity in O(n^{2.5}) time.
So far.
If T is an empty set, then there exist an algorithm to solve the problem in O(n^{2.5}) time (in fact O(n^{2.375}) is possible) (see the introduction in Ran Duan: Breaking the O(n^{2.5}) Time Barrier for Undirected Unit-Capacity Maximum Flow. SODA 2013: 1171-1179 for a survey of such results)
If T is the entire set of vertices, then we can also solve it in O(n^{2.5}) time (and this also works for directed graphs). See this paper. https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/network%20flow%20and%20testing.pdf
but when T is just some arbitrary subset, no known algorithm takes O(n^{2.5}) time. Combine the techniques in 1 and 2, one can up with an algorithm that runs in O(n^{2.5}) time if any one of the following is true
n-|T| = O(n^{¾}).
number of edges between vertices in |T| = O(n^{1.5}).
Each component of V\T is constant size.
I’m working on checking if one can use link/cut tree to create a generalization of finger tree.
Finger tree maintains a sequence of elements in a monoid(or one can consider a rooted path with each vertex weighted by a monoid element), and we can do many operations really fast. One can split the sequence, concat the sequence and find the sum of a sequence(so, the weight from the root to the end vertex). Note this allow us to find sum of a subsequence by split at appropriate positions and take the sum of the resulting middle sequence.
From what I read, one might want to generalize it to work on a rooted tree instead of a rooted path. We still maintain the nice property the path from the root to any vertex is unique. link/cut tree seems to do the trick as a underlying data structure. The question is more about the semantics. What would be a way to define split,concat,sum so when it is restricted to a rooted path, we get the finger tree behavior, and it’s actually useful for something else…
I guess the idea is to have this CAPTCHA during sign up or shows up once per k actions where k is relatively large? Otherwise participation becomes a chore…
If the solution provided by the user gets stored, then one can use this to find all the interesting ways to solve the same problem.
I’m trying to figure out if there is some deterministic algorithm for this problem. Initially I thought this would be known, but seems like it is not as trivial.